东莞seo建站哪家好,namesilo wordpress,网站顶部广告代码,超级seo企业网站系统题干#xff1a;
C国的死对头A国这段时间正在进行军事演习#xff0c;所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段#xff0c;所以每个工兵营地…题干
C国的死对头A国这段时间正在进行军事演习所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动可能增加或减少若干人手,但这些都逃不过C国的监视。 中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动而Derek每次询问的段都不一样所以Tidy不得不每次都一个一个营地的去数很快就精疲力尽了Derek对Tidy的计算速度越来越不满:你个死肥仔算得这么慢我炒你鱿鱼!”Tidy想“你自己来算算看这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说“死肥仔叫你平时做多点acm题和看多点算法书现在尝到苦果了吧!”Tidy说我知错了。。。但Windbreaker已经挂掉电话了。Tidy很苦恼这么算他真的会崩溃的聪明的读者你能写个程序帮他完成这项工作吗不过如果你的程序效率不够高的话Tidy还是会受到Derek的责骂的.
Input
第一行一个整数T表示有T组数据。 每组数据第一行一个正整数NN50000,表示敌人有N个工兵营地接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人1ai50。 接下来每行有一条命令命令有4种形式 (1) Add i j,i和j为正整数,表示第i个营地增加j个人j不超过30 (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人j不超过30; (3)Query i j ,i和j为正整数,ij表示询问第i到第j个营地的总人数; (4)End 表示结束这条命令在每组数据最后出现; 每组数据最多有40000条命令
Output
对第i组数据,首先输出“Case i:”和回车, 对于每个Query询问输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Case 1:
6
33
59
题目大意 中文题啦。
解题报告 每个线段树小萌新都必做的模板题。build建树现用的板子跟此略有不同不过其实还是要具体题目具体分析pushdown没有用到因为没有区间更新操作。 注意是单点更新还是单点覆盖更新这关系到你的val是还是。但是pushup中的更新都是。
AC代码
#includebits/stdc.husing namespace std;
const int MAXN 50000 5;
int n;
int a[MAXN];
struct TREE {int l,r;int val;int laz;
} tree[4*MAXN];
void pushup(int cur) {tree[cur].val tree[2*cur].val tree[2*cur 1].val;
}
void build(int l ,int r,int cur) {if(l r) {tree[cur].l tree[cur].r l;//写成tree[r].r 了。。 tree[cur].val a[l];tree[cur].laz 0;return ;//这步return必须加不然就无限递归了。这就是为什么写递归函数要将出口写在最前面就是不给他再次进入递归函数的机会 }int m (lr)/2;tree[cur].l l;tree[cur].r r;
// tree[cur].val 0;build(l,m,2*cur);build(m1,r,2*cur 1);pushup(cur);
}
void pushdown(int l,int r,int cur) {int m (lr)/2;if(tree[cur].laz !0) {tree[2*cur].val (m-l1) *tree[cur].laz;tree[2*cur].laz tree[cur].laz;tree[2*cur 1].val (r-m) * tree[cur].laz;tree[2*cur 1].laz tree[cur].laz;tree[cur].laz 0;}
}
//pl-pr为查询区间l和r为树种 当前cur下标
int query2(int pl,int pr,int l,int r,int cur) {if(pll prr) return tree[cur].val; pushdown(cur,l,r);int m (lr)/2;int res 0;if(pl m) res query2(pl,pr,l,m,2*cur);//下面这里是if啊不是else if(pr m1) res query2(pl,pr,m1,r,2*cur 1);return res;
}void update1(int tar,int val,int l,int r,int cur) {if(l r) {tree[cur].val val;tree[cur].laz val;return;//这步return必须加不然就无限递归了。这就是为什么写递归函数要将出口写在最前面就是不给他再次进入递归函数的机会 }int m (l r)/2;if(tarm) update1(tar,val,l,m,2*cur);else update1(tar,val,m1,r,2*cur 1);pushup(cur);
}
int main()
{int t;int iCase 0;int tmp1,tmp2;char op[10];cint;while(t--) {printf(Case %d:\n,iCase);scanf(%d,n);for(int i 1; in; i ) {scanf(%d,a[i]);}memset(tree,0,sizeof(tree));build(1,n,1);
// printf(%d %d ,tree[1].l,tree[1].r);
// for(int i 1; i100; i) printf(%d ,tree[i].val);while(scanf(%s,op) ) {if(op[0] E) break;else if(op[0] A) {scanf(%d%d,tmp1,tmp2);update1(tmp1,tmp2,1,n,1);}else if(op[0] S) {scanf(%d%d,tmp1,tmp2);update1(tmp1,-tmp2,1,n,1);}else if(op[0] Q) {scanf(%d%d,tmp1,tmp2);printf(%d\n,query2(tmp1,tmp2,1,n,1));}}}return 0 ;}
