BZOJ2683: 简单题_「bzoj2683」简单题-程序员宅基地

技术标签： 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;
}

本文链接：https://blog.csdn.net/Ep1C_HeReT1c/article/details/72657556

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

ceph安装配置文档（centos6.6）-程序员宅基地

文章浏览阅读877次。Ceph安装部署文档目录一：简介... 1二：部署环境介绍... 1三：集群配置准备工作... 2四：安装ceph软件包... 6五：安装ceph对象网关... 9六、搭建ceph集群... 106.1、配置mon节点... 106.2：添加osd节点... 136.2.1、添加第一块osd节点... 136.3：添加元数据服务器... 176.3.1、添加第一个元数据服务器... 17七：安装c..._ceph安装配置文档

Node.js日记：第一个程序Hello World-程序员宅基地

文章浏览阅读122次。JavaScript 代码运行环境JavaScript 的运行不像 C 语言等其他编译型语言编译后直接在操作系统上运行，因为它是脚本语言，运行时必须要借助引擎（解释器）来运行，所以它可以在封装了引擎的环境下运行。封装了 JavaScript 引擎的环境可以分为两类：一类是浏览器环境；一类是非浏览器环境，比如 Node.js。使用浏览器运行 JavaScript 代码：...

Python安装包，官网下载太慢解决方法：淘宝国内镜像_python淘宝镜像_Python自动化办公社区的博客-程序员宅基地

文章浏览阅读6.6k次，点赞3次，收藏8次。下载传送门????https://npm.taobao.org/mirrors/python/_python淘宝镜像

arm上ldrex和strexeq指令用来尝试获取独占内存权限和设置在独占权限时回写-程序员宅基地

文章浏览阅读996次。【duan注】关于LDREX 和 STREX这两对指令的具体使用方法，及其作用（独占访问存储器），请查看 DUI0204IC_rvct_assembler_guide.pdf 手册的148页。__raw_spin_lock在ARM处理器上的实现/******include/asm-arm/spinlock_types.h***/ typedef struct { vol

ManagementFactory打印应用线程,内存和GC等信息_managementfactory 堆外内存_码上得天下的博客-程序员宅基地

文章浏览阅读544次。ManagementFactory是一个为我们提供各种获取JVM信息的工厂类，使用ManagementFactory可以获取大量的运行时JVM信息，比如JVM堆的使用情况，以及GC情况，线程信息等，通过这些数据项我们可以了解正在运行的JVM的情况，以便我们可以做出相应的调整。本文将基于ManagementFactory，介绍如何通过ManagementFactory获取一些运行时的JVM信息，下面首先展示了ManagementFactory的类图，可以看出它提供了大量的工厂方法，使得我们可以通过调用这些方法_managementfactory 堆外内存

SD卡及接口设计基础_sdr50_MR.STRAW的博客-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏11次。要了解SD卡的设计规范，咱们必须从SD卡的分类讲起。有两种分类方式。一种是根据卡容量来分类。分为标准卡（SDSC）、高容量卡（SDHC）、扩展容量卡（SDXC）。SDSC不超过2GB，支持所有的SD协议。SDHC不超过32GB，但大于2GB，知识SD2.0协议。SDXC不超过2TB但大于32GB，支持SD3.0协议。另一种根据卡的速率来分类，如SDR104，即支持最大传输速率为104MB/S，时钟频率为208MHz，供电1.8V。SDR50、SDR25、SDR12类别以上，不再赘述。DDR50与SDR50相_sdr50