洛谷P3374 【模板】树状数组 1(CDQ分治)
2018-06-17 21:28:50来源:未知 阅读 ()
题目描述
如题,已知一个数列,你需要进行下面两种操作:
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:新博客开通啦!
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash