A - 敌兵布阵
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组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。 接下来每行有一条命令，命令有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为正整数,i<=j，表示询问第i到第j个营地的总人数; (4)End 表示结束，这条命令在每组数据最后出现; 每组数据最多有40000条命令Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。Sample Input
1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End
Sample Output
Case 1:63359
AC代码：
#include#include #include #include using namespace std;typedef long long ll;const int MAXNODE = 1 << 19;const int MAX = 2e5 + 10;struct Node{ ll left; ll right; ll value;};Node node[MAXNODE];ll father[MAX];void BuildTree(ll i,ll left,ll right){ node[i].left = left; node[i].right = right; node[i].value = 0; if(left == right) { father[left] = i; return ; } else { ll temp = (left + right) / 2.0; BuildTree(i << 1,left,temp); BuildTree((i << 1) + 1,temp + 1,right); }}void Update(ll ri){ if(ri == 1) return ; ll fi = ri / 2; ll a = node[fi << 1].value; ll b = node[(fi << 1) + 1].value; node[fi].value = a + b; Update(fi);}ll M;void query(ll i,ll l,ll r)//查找{ if(node[i].left == l && node[i].right == r) { M += node[i].value; return ; } i = i << 1; if(l <= node[i].right) { if(r <= node[i].right) { query(i,l,r); } else { query(i,l,node[i].right); } } i += 1; if(r >= node[i].left) { if(l >= node[i].left) { query(i,l,r); } else { query(i,node[i].left,r); } }}int main(){ ll T,t,n,i,v,a,b; scanf("%lld",&T); t = 1; while(T--) { printf("Case %lld:\n",t++); scanf("%lld",&n); BuildTree(1,1,n); for(i = 1;i <= n; i++) { scanf("%lld",&v); node[father[i]].value = v; Update(father[i]); } char s[100]; getchar(); while(~scanf("%s",s)&& s[0] != 'E') { scanf("%lld%lld",&a,&b); if(s[0] == 'Q') { M = 0; query(1,a,b); printf("%lld\n",M); } if(s[0] == 'A') { node[father[a]].value += b; Update(father[a]); } if(s[0] == 'S') { node[father[a]].value -= b; Update(father[a]); } getchar(); } } return 0;}
I Hate It
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。 学生ID编号分别从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。 接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。 当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。Output
对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5
Sample Output
5659
Hint
Huge input,the C function scanf() will work better than cin
#include#include #include #include #include #include using namespace std;typedef long long ll;#define lson l,m,i*2#define rson m+1,r,i*2+1const int MAXN=2e5+10;struct Node{ ll l,r,value=0; //l,r为左右区间，v为最值 ll mid() //成员函数 { return (l+r)/2.0; }};Node node[MAXN*4];void push_up(ll i){ node[i].value =max(node[i*2].value,node[i*2+1].value);}void Build(ll l,ll r,ll i){ node[i].l=l; node[i].r=r; node[i].value=0; if(l==r) { scanf("%lld",&node[i].value); return; } ll m=node[i].mid(); //m=(l+r)/2.0 Build(lson); //Build(l,m,i*2) Build(rson); //Build(m+1,r,i*2+1) push_up(i);}void update(ll l,ll r,ll i,ll v,ll num) //单点更新{ if(l==r&&l==num) { node[i].value=v; return ; } ll m=node[i].mid(); if(m>=num) update(l,m,i*2,v,num); else update(m+1,r,i*2+1,v,num); push_up(i);}ll M;void query(ll l,ll r,ll i) //查找{ if(node[i].l==l&&node[i].r==r) { M=max(node[i].value,M); return; } ll m=node[i].mid(); if(r<=m) { query(l,r,i*2); } else { if(l>m) { query(l,r,i*2+1); } else { query(lson); query(rson); } }}int main(){ ll n,m,a,b; char s[10]={0}; while(~scanf("%lld%lld",&n,&m)) { memset(s,0,sizeof(s)); Build(1,n,1); while(m--) { getchar(); scanf("%s",s); //puts(s); scanf("%lld%lld",&a,&b); if(s[0]=='Q') { M=0; query(a,b,1); printf("%lld\n",M); } else { update(1,n,1,b,a); } } } return 0;}
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab.Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4
Sample Output
455915
Hint
The sums may exceed the range of 32-bit integers.
#include#include using namespace std;const int N = 1e5 + 10;typedef long long LL;typedef struct Node{ int l; int r; int mid() { return (l + r) / 2.0; }}Node;LL ans;Node node[N << 2];//为什么乘4LL add[N << 2];// 延迟标记数组LL sum[N << 2];//每个节点的sumvoid PushUp(int i);#define lson i << 1,l,m#define rson i << 1 | 1,m + 1,rvoid build(int i,int l,int r)//建树并完成初始化{ node[i].l = l; node[i].r = r; sum[i] = 0; add[i] = 0; if(l == r) { scanf("%d",&sum[i]);//在内部输入，为叶子节点 return ;//一定要写return！！！ } int m = node[i].mid(); build(lson);//只想下更新sum build(rson); PushUp(i);//递归回去完成区间的更新.}void PushUp(int i) // 建树递归返回时更新。{ sum[i] = sum[i << 1] + sum[i << 1 | 1];}void PushDown(int i,int L) // L为区间长度 （延迟标记）{ if(add[i]) { add[i << 1] += add[i]; add[i << 1 | 1] += add[i]; sum[i << 1] += add[i] * (L - (L >> 1)); // 易错 sum[i << 1 | 1] += add[i] * (L >> 1); add[i] = 0; }}void update(int v,int l,int r,int i)//更新操作，区间【l,r】加值v{ if(node[i].l == l && node[i].r == r)//当找到目标区间时， { sum[i] += (LL)v * (r - l + 1);//更新当前节点的值， add[i] += v;//延迟标记+V return ; } PushDown(i,node[i].r - node[i].l + 1);// 因为没有匹配到合适的区间,向下寻找,检查这个区间是否有标记. int m = node[i].mid();//如果有标记,说明应该先把之前的标记量给计算出,再进行寻找. if(r <= m) { update(v,l,r,i << 1); } else { if(l > m) update(v,l,r,i << 1 | 1); else { update(v,l,m,i << 1); update(v,m + 1,r,i << 1 | 1); } } PushUp(i);//递归返回}void query(int l,int r,int i) //查询{ if(node[i].l == l && node[i].r == r) { ans += sum[i]; return ; } PushDown(i,node[i].r - node[i].l + 1); int m = node[i].mid(); if(r <= m) query(l,r,i << 1 ); else { if(l > m) query(l,r,i << 1 | 1); else { query(l,m,i << 1); query(m + 1,r,i << 1 | 1); } }}int main(){ int n,m; while(~scanf("%d%d",&n,&m)) { build(1,1,n); char cc; while(m--) { int a,b,c; getchar(); cc=getchar(); if(cc == 'Q') { ans = 0; scanf("%d%d",&a,&b); query(a,b,1); printf("%d\n",ans); } else { scanf("%d%d%d",&a,&b,&c); update(c,a,b,1); } } } return 0;}
用树状数组
#include#include #include #include #include #include using namespace std;const int M=200000+10;const int MAX=0x3f3f3f3f;typedef long long ll;ll a[101010],c[101010],t[101010],n;ll aa[100100]={0},bb[100100]={0},sum[100100]={0};ll lowbit(ll x){ return x&(-x);}ll Getsum(ll i,ll q[])//求前几项和{ ll ans=0; while(i>0) { ans+=q[i]; i-=lowbit(i); } return ans;}void update(ll i,ll v,ll q[])//更新{ while(i<=n) { q[i]+=v; i+=lowbit(i); }}int main(){ ll m,i,x,y,v,ans=0; scanf("%lld%lld",&n,&m); for(i=1;i<=n;i++) scanf("%lld",&a[i]); sum[1]=a[1]; for(i=2;i<=n;i++) sum[i]=sum[i-1]+a[i]; char ccc; while(m--) { getchar(); ccc=getchar(); if(ccc=='Q') { scanf("%lld%lld",&x,&y); ans=0; ans=sum[y]-sum[x-1]; ans+=(y+1)*Getsum(y,aa)-Getsum(y,bb); ans-=x*Getsum((x-1),aa)-Getsum((x-1),bb); printf("%lld\n",ans); } else if(ccc=='C') { scanf("%lld%lld%lld",&x,&y,&v); update(x,v,aa); update(y+1,-v,aa); update(x,x*v,bb); update(y+1,-(y+1)*v,bb); } } return 0;}