洛谷P3374 【模板】樹狀數組 1（CDQ分治）

題目描述

如題，已知一個數列，你需要進行下麵兩種操作：

1.將某一個數加上x

2.求出某區間每一個數的和

輸入輸出格式

輸入格式：

第一行包含兩個整數N、M，分別表示該數列數字的個數和操作的總個數。

第二行包含N個用空格分隔的整數，其中第i個數字表示數列第i項的初始值。

接下來M行每行包含3個整數，表示一個操作，具體如下：

操作1： 格式：1 x k 含義：將第x個數加上k

操作2： 格式：2 x y 含義：輸出區間[x,y]內每個數的和

輸出格式：

輸出包含若幹行整數，即為所有操作2的結果。

輸入輸出樣例

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

14
16

說明

時空限制：1000ms,128M

數據規模：

對於30%的數據：N<=8，M<=10

對於70%的數據：N<=10000，M<=10000

對於100%的數據：N<=500000，M<=500000

樣例說明：

故輸出結果14、16

CDQ分治維護二維偏序

第一維用排序搞掉

第二維用CDQ分治

慢的要死。。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<ctime>
 5 #include<cstdlib>
 6 using namespace std;
 7 #define ls T[now].ch[0]
 8 #define rs T[now].ch[1]
 9 const int MAXN=2*1e6+10;
10 inline char nc()
11 {
12     static char buf[MAXN],*p1=buf,*p2=buf;
13     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
14 }
15 inline int read()
16 {
17     char c=nc();int x=0,f=1;
18     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
19     while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
20     return x*f;
21 }
22 int n,m;
23 struct node
24 {
25     int idx;//第幾次詢問
26     int val;//修改的值
27     int type;//操作類型 
28     bool operator<( const node &a) const {
29         return idx==a.idx?type<a.type:idx<a.idx;}
30 }Q[MAXN];
31 int qidx=0;//操作的個數
32 int aidx=0;//詢問的個數
33 int ans[MAXN]; 
34 node tmp[MAXN];
35 void CDQ(int l,int r)
36 {
37     if(r-l<=1)    return ;
38     int mid=(l+r)>>1;CDQ(l,mid);CDQ(mid,r);
39     int sum=0;
40     int p=l,q=mid,o=0;
41     while(p<mid&&q<r)
42     {
43         if(Q[p]<Q[q])
44         {
45             if(Q[p].type==1) sum+=Q[p].val;
46             tmp[o++]=Q[p++];
47         }
48         else
49         {
50             if( Q[q].type==2)    ans[Q[q].val]-=sum;
51             else if(Q[q].type==3)    ans[Q[q].val]+=sum;
52             tmp[o++]=Q[q++];
53         }
54     }
55     while(p<mid) tmp[o++]=Q[p++];
56     while(q<r) 
57     {
58         if( Q[q].type==2)    ans[Q[q].val]-=sum;
59         else if(Q[q].type==3)    ans[Q[q].val]+=sum;
60         tmp[o++]=Q[q++];
61     }
62     for(int i=0;i<o;i++) Q[i+l]=tmp[i];
63 }
64 int main()
65 {
66     #ifdef WIN32
67     freopen("a.in","r",stdin);
68     #else
69     #endif
70     n=read();m=read();
71     for(int i=1;i<=n;i++)
72     {
73         Q[qidx].idx=i;
74         Q[qidx].type=1;
75         Q[qidx].val=read();++qidx;
76     }
77     for(int i=0;i<m;i++)
78     {
79         int type=read();
80         Q[qidx].type=type;
81         if(type==1)    Q[qidx].idx=read(),Q[qidx].val=read();
82         else
83         {
84             int l=read(),r=read();
85             Q[qidx].idx=l-1;Q[qidx].val=aidx;++qidx;
86             Q[qidx].type=3;Q[qidx].idx=r;Q[qidx].val=aidx;aidx++;
87         }
88         ++qidx;
89     }
90     CDQ(0,qidx);
91     for(int i=0;i<aidx;i++)    printf("%d\n",ans[i]);
92     return 0;
93 }