15:Challenge 11(主席树裸题)
2018-06-17 22:02:44来源:未知 阅读 ()
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
-
给一个长为N的数列,有M次操作,每次操作是以下两种之一:
(1)修改数列中的一个数
(2)求某次操作后连续一段的和
- 输入
- 第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行,每行开头是一个字符,若该字符为'M',则表示一个修改操作,接下来两个整数x和y,表示把x位置的数修改为y;若该字符为'Q',则表示一个询问操作,接下来三个整数x、y、z,表示求数列中[x,y]这段区间在第z次操作后的和。 - 输出
- 对每一个询问操作单独输出一行,表示答案。
- 样例输入
-
5 4 1 2 3 4 5 Q 2 3 0 M 3 5 Q 2 3 2 Q 1 3 1
- 样例输出
-
5 7 6
- 提示
- 1<=N<=10^5,1<=M<=10^5,输入保证合法,且所有整数及答案可用带符号32位整型存储。
- 查看
- 提交
- 统计
- 提问
感觉数据有问题,
调了大半天最后居然是读入优化错了。
但是我前几道题也是用的这个读入优化,,,,
见鬼了。。
#include<cstdio> #include<cstring> #include<cmath> using namespace std; const int MAXN=2000001; const int mod=998244353; inline void read(int &n) { //char c='+';bool flag=0;n=0; //while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar(); //while(c>='0'&&c<='9') n=n*10+c-48,c=getchar(); scanf("%d",&n); } struct node { int ls,rs,sum; node(){ls=rs=sum=0;} }tree[MAXN]; int how; int root[MAXN]; int cz[MAXN]; int ans=0; int tot=0; void update(int k) { tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum; } void change(int l,int r,int &k,int pre,int pos,int val) { if(!k) k=++tot; tree[k].sum=tree[pre].sum; if(l==r) { tree[k].sum=val; return ; } int mid=(l+r)>>1; if(pos<=mid) tree[k].rs=tree[pre].rs,change(l,mid,tree[k].ls,tree[pre].ls,pos,val); else tree[k].ls=tree[pre].ls,change(mid+1,r,tree[k].rs,tree[pre].rs,pos,val); update(k); } void query(int l,int r,int k,int wl,int wr) { if(wl<=l&&r<=wr) { ans+=tree[k].sum; return ; } int mid=(l+r)>>1; if(wl<=mid) query(l,mid,tree[k].ls,wl,wr); if(wr>mid) query(mid+1,r,tree[k].rs,wl,wr); } int main() { int n,m; read(n);read(m); for(int i=1;i<=n;i++) { read(how); change(1,n,root[0],root[0],i,how); } int now=0; for(int i=1;i<=m;i++) { cz[i]=now; char s[3]; scanf("%s",s); if(s[0]=='M')// 修改 { now++;cz[i]=now; int pos,val;read(pos);read(val); change(1,n,root[now],root[now-1],pos,val); } else { int ll,rr,tim; read(ll);read(rr);read(tim); ans=0; query(1,n,root[cz[tim]],ll,rr); printf("%d\n",ans); } } return 0; }
好吧是读入优化没判断负数
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 树状结构之主席树 2019-01-03
- 洛谷P4197 Peaks(Kruskal重构树 主席树) 2018-09-18
- codechef September Challenge 2018 Division 2 A-F 2018-09-18
- BZOJ4299: Codechef FRBSUM(主席树) 2018-09-18
- 洛谷P2468 [SDOI2010]粟粟的书架(二分答案 前缀和 主席树) 2018-09-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