BZOJ2683: 简单题_「bzoj2683」简单题_CR1SceNT的博客-程序员秘密

技术标签: CDQ分治  

BZOJ2683传送门
BZOJ1176几乎一样啊
戳这里–>BZOJ1176

然后这个题 应 该? 要开long long 吧。
(日常打错变量名QAQ。。)

【代码】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define N 200005
#define M 800005
#define INF 1<<29
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
   if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,tot,numa;
ll ans[N],szsz[500005];

class Query{
    public:
        int type,x,y,w,id;
    Query(){}
    Query(int tt,int xx,int yy,int ww,int ii){
        type=tt,x=xx,y=yy,w=ww,id=ii;
    }
}Q[M],tmp[M];

bool operator <(Query a,Query b){
    return a.x<b.x||(a.x==b.x&&a.type<b.type);
}

int lowbit(int x){
   return x&-x;}

void Sum_Up(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i)) szsz[i]+=y;
}

ll query(int x){
    ll rtn=0;
    for(int i=x;i;i-=lowbit(i)) rtn+=szsz[i];
    return rtn;
}

void Clear(int x){
    for(int i=x;i<=n&&szsz[i];i+=lowbit(i)) szsz[i]=0;
}

void CDQ(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;CDQ(l,mid);CDQ(mid+1,r);
    int p=l,q=mid+1,o=0;
    while(p<=mid&&q<=r){
        if(Q[p]<Q[q]) {
            if(Q[p].type&1) Sum_Up(Q[p].y,Q[p].w);
            tmp[o++]=Q[p++];
        }
        else {
            if(Q[q].type==2) ans[Q[q].id]+=query(Q[q].y)*Q[q].w;
            tmp[o++]=Q[q++];
        }
    }
    while(p<=mid) tmp[o++]=Q[p++];
    while(q<=r) {
        if(Q[q].type==2) ans[Q[q].id]+=query(Q[q].y)*Q[q].w;
        tmp[o++]=Q[q++];
    }
    for(int i=0;i<o;i++) Clear(tmp[i].y),Q[i+l]=tmp[i];
}

int main()
{
    n=read();
    while(1)
    {
        static int tp,x,y,xx,yy;
        tp=read();if(tp==3) break;
        x=read(),y=read(),xx=read();
        if(tp&1) Q[++tot]=Query(tp,x,y,xx,0);
        else {
            yy=read();numa++;
            Q[++tot]=Query(tp,x-1,y-1,1,numa);Q[++tot]=Query(tp,x-1,yy,-1,numa);
            Q[++tot]=Query(tp,xx,y-1,-1,numa);Q[++tot]=Query(tp,xx,yy,1,numa);
        }
    }
    CDQ(1,tot);
    for(int i=1;i<=numa;i++) printf("%lld\n",ans[i]);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Ep1C_HeReT1c/article/details/72657556

智能推荐

[CEOI2017]Building Bridges_weixin_30677475的博客-程序员秘密

题目斜率优化思博题,不想写了之后就一直\(95\)了,于是靠肮脏的打表就是更新了一下凸壳上二分斜率的写法,非常清爽好写就当是挂个板子了#include&lt;algorithm&gt;#include&lt;iostream&gt;#include&lt;cstring&gt;#include&lt;cstdio&gt;#define re register#defi...

项目管理(PMP)项目进度管理_pmp项目管理_83Dillon的博客-程序员秘密

自由浮动时间:在不影响后续工作的最早开始时间的情况下,活动可以拖延的时间,比如A活动计划9天,但是只需要5天,所以在9天内完成,就不会影响后续活动的开始时间,4天就是自由浮动时间。资源数量:增加资源数量,使其达到最初的两倍,不一定能缩短一半的时间,很有可能因为各种风险,知识传递,学习曲线,额外合作造成持续时间增加。外部依赖关系:是项目活动和非项目活动之间的关系,不在项目的控制范围内。关键路径法的特点:决定了项目的总工期,关键路径所需要的时间最长,浮动时间最少,活动延误可能会导致关键路径变化。

tf.div()除法运算_马鹏森的博客-程序员秘密

使用Python 2的除法运算符语义对x / y元素进行除法。(弃用)tf.div(x, y,name=None)警告:不推荐使用此函数。它将在未来的版本中被删除。更新说明:不支持操作符或tf.math.divide。注意:最好使用遵循Python 3除法运算符语义的张量除法运算符或tf.divide。这个函数除x和y,强制使用Python 2语义。也就是说,如果x和y都是整数,那么结果就是整数。这与Python 3形成了对比,Python 3中使用/的除法总是浮点数,而使用//的除法总是整数。.

matplotlib绘图时汉字,符号显示问题_lyyolo的博客-程序员秘密

1.作图时汉字显示为方块的问题在用matplotlib进行作图时,如果含有中文标签,会发现不能正常显示,这是因为matplotlib的默认字体是英文字体,解决它的办法是,在作图前手动指定默认字体为中文字体,如黑体(SimHei)。import matplotlib.pyplot as pltplt.rcParams['font.sans-serif']=['SimHei'] #...

MyBatis--1_mybatis == '1_果子真好吃的博客-程序员秘密

概述MyBatisMyBatis 是一款优秀的持久层框架,它支持自定义 SQL、存储过程以及高级映射。MyBatis 免除了几乎所有的 JDBC 代码以及设置参数和获取结果集的工作。MyBatis 可以通过简单的 XML 或注解来配置和映射原始类型、接口和 Java POJO(Plain Old Java Objects,普通老式 Java 对象)为数据库中的记录。以开发sql语句的工作量为代价换取高灵活性##Hello MyBatis1、添加依赖&lt;dependency&gt;

随便推点

ubuntu wifi适配器找不到_weixin_40460978的博客-程序员秘密

ubuntu wifi适配器找不到首先在终端输入 nmcil device 命令,查看是否托管如果没有,编辑NetworkManager.conf ,将其中的managed设为true重启network-manger服务

logstash 报错_想要变瘦的胖子的博客-程序员秘密

elk运行一段时间后发现 logstash日志文件一直有警告输出,警告内容[2020-04-14T05:12:39,097][WARN ][org.apache.kafka.clients.NetworkClient][main] [Consumer clientId=xxx-2, groupId=xx] 3 partitions have leader brokers without a ...

【opencv】opencv的框架与各模块功能介绍_大姨妈V的博客-程序员秘密

       学习opencv已有三个月时间,特此记录一下自己的所学知识,便于日后回顾与整理。文中内容多为摘录,具体链接如下:摘录自:https://zhuanlan.zhihu.com/p/33008701(框架介绍)              http://blog.csdn.net/poem_qianmo/article/details/19925819(各模块介绍,opencv2版,毛星云...

第8章 函数编写_volatile parallel unsafe_Zhao.Mr的博客-程序员秘密

第8章 函数编写PostgreSQL 同大多数数据库一样,可以把若干 SQL 语句组合在一起,然后将其作为一个单元来处理,并且每次运行时可以输入不同的参数。这种机制在不同数据库中的名称不一样,有的叫存储过程,有的叫用户自定义函数,而 PostgreSQL 统一称之为函数。8.1 PostgreSQL函数功能剖析PostgreSQL 的函数可分为基本函数、聚合函数、窗口函数和触发器函数四大类。8.1.1 函数功能基础知识介绍函数的基本结构CREATE OR REPLACE FUNCTION fun

ARM学习笔记(七)--存储器映射的I/O_liufei_learning的博客-程序员秘密

存储器映射的I/O基于ARM内核的芯片具有许多的外设,这些外设访问的标准方法是使用存储器映射的I/O,为外设的每个寄存器都分配一个地址。通常,从这些地址装载数据用于读入,向这些地址保存数据用于输出。有些地址的装载和保存用于外设的控制功能,而不是输入或输出功能。注意:存储器映射的I/O位置的操作不同于正常的存储器位置的操作。通常,存储器映射的I/O位置没有高速缓存和无缓冲区。执行ARM 系统I/O 功能的标准方法是使用存储器映射的I/O。装载或保存I/O 值时,使用提供给I/O 功能的特殊存储器地址。通常,从

推荐文章

热门文章

相关标签