三国之战
Time Limit 1000 Memory Limit 65536 description 在三国某某战争中,魏军要围攻蜀国. ,诸葛亮亲自指挥战争,对抗曹操。现假设诸葛亮有N个大炮,每个大炮都有一个攻击值ai(ai>=0 &&ai<=100) , 而且他有一个神奇的技能,就是他能指定任意区间的大炮,使他们的攻击值都乘以x(x.>=0 && x<=10),同时他也会询问某段区间的大炮的总攻击值。(数据保证答案不会超过long long)input 第一行输入N(N<=100000),接下一行N个数ai,代表第i个大炮的攻击值 接着输入Q,代表Q次操作,格式: attack l r x 代表把第l到 第r个大炮的攻击值都乘以x query l r 查询l到r大炮攻击和值 output 输出每次查询结果 sample_input 4 1 1 1 1 3 attack 1 2 2 query 1 4 query 2 2
3
100 100 100 3 query 1 3 attack 1 3 0 query 1 3 sample_output Case 1: 6 2 Case 2: 300 0 hintsource
这一题我A了很久才搞定,主要时间就花在调试上面
因为一个漏洞。6
1 1 1 1 1 1 6 attack 1 4 4 attack 3 6 2 attack 1 1 3 attack 1 5 3 attack 1 4 0 query 3 68
#include<iostream>
#include<cstdio> #include<algorithm> #include<cstring> #define N 100030 using namespace std; class node { public: int l,r; int sum,lazy; bool flag; }root[4*N]; int shu[N]; void build(int t,int l,int r) { root[t].l=l;root[t].r=r;root[t].lazy=1; root[t].flag=0; if(root[t].l==root[t].r){cin>>root[t].sum;return;} build(t<<1,l,(l+r)/2);build(t<<1|1,(l+r)/2+1,r); root[t].sum=root[t<<1].sum+root[t<<1|1].sum; } void up(int t) { if(root[t<<1].flag&&root[t<<1].l!=root[t<<1].r)up(t<<1); if(root[t<<1|1].flag&&root[t<<1|1].l!=root[t<<1|1].r)up(t<<1|1); root[t<<1].lazy*=root[t].lazy;root[t<<1|1].lazy*=root[t].lazy; root[t<<1].flag=1;root[t<<1|1].flag=1; root[t<<1].sum*=root[t].lazy; root[t<<1|1].sum*=root[t].lazy; root[t].lazy=1; root[t].flag=0; } void update(int t,int l,int r,int date) { if(root[t].l==l&&root[t].r==r) { if(root[t].flag&&root[t].l!=root[t].r)//就是这调了N久才知道要补上 up(t); root[t].sum*=date;root[t].lazy=date;root[t].flag=1; return;} else { if(root[t].flag&&root[t].l!=root[t].r) { up(t); } if(root[t<<1].r>=r)update(t<<1,l,r,date); else if(root[t<<1|1].l<=l)update(t<<1|1,l,r,date); else {update(t<<1,l,root[t<<1].r,date);update(t<<1|1,root[t<<1|1].l,r,date);} root[t].sum=root[t<<1].sum+root[t<<1|1].sum; } } int query(int t,int l,int r) { int s; if(root[t].l==l&&root[t].r==r)return root[t].sum; else { if(root[t].flag&&root[t].l!=root[t].r) { up(t); } if(root[t<<1].r>=r)s=query(t<<1,l,r); else if(root[t<<1|1].l<=l) s=query(t<<1|1,l,r); else s=query(t<<1,l,root[t<<1].r)+query(t<<1|1,root[t<<1|1].l,r); root[t].sum=root[t<<1].sum+root[t<<1|1].sum; } return s; } int main() { int n,q; char s[33]; int a,b,c; int cas=0; while(scanf("%d",&n)!=EOF) { build(1,1,n); scanf("%d",&q); printf("Case %d:\n",++cas); //cout<<"Case "<<++cas<<": "<<"\n"; for(int j=1;j<=q;j++) { //cin>>s>>a>>b; scanf("%s%d%d",s,&a,&b); if(strcmp(s,"attack")==0) { scanf("%d",&c); update(1,a,b,c); } else { //cout<<query(1,a,b)<<"\n"; printf("%d\n",query(1,a,b)); } }}
}