CDQ分治求前缀和

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=200005;
 4 int n,a_tot,q_tot,ans[N];
 5 char s[10];
 6 struct query
 7 {
 8     int id,v,op;
 9     bool operator < (const query &rhs)const
10     {
11         if(id==rhs.id) return op<rhs.op;
12         return id<rhs.id;
13     }
14 }query[N],tmp[N];
15 void init()
16 {
17     a_tot=0; q_tot=0;
18     memset(ans,0,sizeof(ans));
19 }
20 void cdq(int l,int r)
21 {
22     if(l==r) return;
23     int m=(l+r)>>1;
24     cdq(l,m); cdq(m+1,r);
25     int p=l,q=m+1,tot=0,sum=0;
26     while(p<=m && q<=r)
27     {
28         if(query[p]<query[q])
29         {
30             if(query[p].op==1) sum+=query[p].v;
31             tmp[tot++]=query[p++];
32         }
33         else
34         {
35             if(query[q].op==2) ans[query[q].v]+=sum;
36             else if(query[q].op==3) ans[query[q].v]-=sum;
37             tmp[tot++]=query[q++];
38         }
39     }
40     while(p<=m) tmp[tot++]=query[p++];
41     while(q<=r)
42     {
43         if(query[q].op==2) ans[query[q].v]+=sum;
44         else if(query[q].op==3) ans[query[q].v]-=sum;
45         tmp[tot++]=query[q++];
46     }
47     for(int i=0;i<tot;i++) query[i+l]=tmp[i];
48 }
49 int main()
50 {
51     int T; scanf("%d",&T);
52     for(int Case=1;Case<=T;Case++)
53     {
54         init();
55         scanf("%d",&n);
56         for(int i=1;i<=n;i++)
57         {
58             int g; scanf("%d",&g);
59             query[a_tot].op=1;
60             query[a_tot].id=i;
61             query[a_tot++].v=g;
62         }
63         while(scanf("%s",&s)!=EOF)
64         {
65             if(s[0]=='E') break;
66             if(s[0]=='S' || s[0]=='A')
67             {
68                 int flag=1,x,v;
69                 if(s[0]=='S') flag=-1;
70                 scanf("%d%d",&x,&v);
71                 query[a_tot].id=x;
72                 query[a_tot].v=flag*v;
73                 query[a_tot++].op=1;
74             }
75             else
76             {
77                 int l,r; scanf("%d%d",&l,&r);
78                 query[a_tot].id=l-1;
79                 query[a_tot].op=3;
80                 query[a_tot++].v=q_tot;
81                 query[a_tot].id=r;
82                 query[a_tot].op=2;
83                 query[a_tot++].v=q_tot;
84                 q_tot++;
85             }
86         }
87         cdq(0,a_tot-1);
88         printf("Case %d:
",Case);
89         for(int i=0;i<q_tot;i++) printf("%d
",ans[i]);
90     }
91     return 0;
92 }