题解 P3374 【【模板】树状数组 1】

· · 题解

这里是一篇 CDQ分治 的题解！

CDQ分治的基本思想可以概括为：把这些询问排成一个序列（离线），递归处理相对于左区间和右区间的询问，在计算答案时，合并两个子问题（类似于归并排序求逆序对），即考虑左半区间内的修改对右半区间内的询问产生的影响。也就是，用左边的子问题来帮助解决右边的子问题。因此，CDQ分治可以支持修改。

对于这道题，我们把两个操作拆成三个操作：

  1. 修改。
  2. 对于查询操作 [l,r] 的 [1,l-1] 查询前缀和。在此时，我们需要把此次查询的结果减去当前前缀和。
  3. 对于查询操作 [l,r] 的 [1,r] 查询前缀和。在此时，我们需要把此次查询的结果加上当前前缀和。

然后，我们对于整个询问序列进行CDQ分治，即可出解。相比于树状数组，常数较大，最大的点跑了540ms。若有不理解的地方可自行对照代码。

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct Query{
    int type,id,val;
    bool operator <(const Query sasa) const {
        return id==sasa.id?type<sasa.type:id<sasa.id;
    }
}a[2000005];
int qid,ans[2000005];
int aid=0;
Query tmp[2000005];
void CDQ(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    CDQ(l,mid);
    CDQ(mid+1,r);
    int sum=0,p=l,q=mid+1,o=l;
    while(p<=mid&&q<=r){
        if(a[p]<a[q]){
            if(a[p].type==1)sum+=a[p].val;
            tmp[o++]=a[p++];
        }
        else {
            if(a[q].type==2)ans[a[q].val]-=sum;
            if(a[q].type==3)ans[a[q].val]+=sum;
            tmp[o++]=a[q++];
        }
    }
    while(p<=mid)tmp[o++]=a[p++];
    while(q<=r){
        if(a[q].type==2)ans[a[q].val]-=sum;
        if(a[q].type==3)ans[a[q].val]+=sum;
        tmp[o++]=a[q++];
    }
    for(int i=l;i<=r;i++)a[i]=tmp[i];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int t;
        scanf("%d",&t);
        a[++qid].type=1;
        a[qid].id=i;
        a[qid].val=t;//把最初的N个数也看成修改操作
    }
    for(int i=1;i<=m;i++){
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1){
            a[++qid].type=1;
            a[qid].id=x;
            a[qid].val=y;
        }
        else {
            a[++qid].type=2;
            a[qid].id=x-1;
            a[qid].val=++aid;
            a[++qid].type=3;
            a[qid].id=y;
            a[qid].val=aid;
        }
    }
    CDQ(1,qid);
    for(int i=1;i<=aid;i++)printf("%d\n",ans[i]);
}