南将军麾下有百万精兵，现已知共有M个士兵，编号为1~M，每次有任务的时候，总会有一批编号连在一起人请战（编号相近的人经常在一块，相互之间比较熟悉），最终他们获得的军功，也将会平分到每个人身上，这样，有时候，计算他们中的哪一个人到底有多少军功就是一个比较困难的事情，军师小工的任务就是在南将军询问他某个人的军功的时候，快速的报出此人的军功，请你编写一个程序来帮助小工吧。
假设起始时所有人的军功都是0.
输入 只有一组测试数据。 每一行是两个整数T和M表示共有T条指令，M个士兵。（1<=T,M<=1000000) 随后的T行，每行是一个指令。 指令分为两种： 一种形如 ADD 100 500 55 表示，第100个人到第500个人请战，最终每人平均获得了55军功，每次每人获得的军功数不会超过100，不会低于-100。 第二种形如： QUERY 300 表示南将军在询问第300个人的军功是多少。 输出 对于每次查询输出此人的军功，每个查询的输出占一行。 样例输入 4 10 ADD 1 3 10 QUERY 3 ADD 2 6 50 QUERY 3 样例输出 1060
超时代码：
#include <stdio.h> #include <string.h> #include<iostream> #include <algorithm> using namespace std; struct node { int l,r,value; int qu; }; node tree[3000001]; void build(int l,int r,int k) { tree[k].l=l; tree[k].r=r; if(tree[k].l==tree[k].r) { tree[k].value=0; tree[k].qu=0; return ; } int mid=(tree[k].l+tree[k].r)>>1; build(l,mid,2*k); build(mid+1,r,2*k+1); } void updata(int l,int r,int k,int val) { if(tree[k].l==l&&tree[k].r==r) { tree[k].qu+=val; // cout<<" tree[k].qu "<<tree[k].qu<<" "<<tree[k].l<<" "<<tree[k].r<<endl; return; } int mid=(tree[k].l+tree[k].r)>>1; if(tree[k].qu) { tree[2*k].qu+=tree[k].qu; tree[2*k+1].qu+=tree[k].qu; tree[k].qu=0; } if(r<=mid) { updata(l,r,2*k,val); } else if(l>mid) { updata(l,r,2*k+1,val); } else { updata(l,mid,2*k,val); updata(mid+1,r,2*k+1,val); } } void query(int l,int r,int k) { // cout<<l<<" "<<r<<" ooooo "<<k<<" k "<<tree[k].l<<" "<<tree[k].r<<endl; if(tree[k].l==l&&tree[k].r==r) { // cout<<l<<" l r "<<r<<endl; tree[k].value+=tree[k].qu; tree[k].qu=0; cout<<tree[k].value<<endl;//" "<<k<<" "<<tree[k].l<<" "<<tree[k].r; return ; } // cout<<" kakaka "<<endl; int mid=(tree[k].l+tree[k].r)>>1; if(tree[k].qu) { tree[2*k].qu+=tree[k].qu; tree[2*k+1].qu+=tree[k].qu; tree[k].qu=0; } if(r<=mid) { query(l,r,2*k); } else { query(l,r,2*k+1); } } int main() { int t,n; int l,r,val; char str[10]; scanf("%d%d",&t,&n); build(1,n,1); for(int i=1;i<=t;i++) { scanf("%s",str); if(str[0]=='A') { scanf("%d%d%d",&l,&r,&val); updata(l,r,1,val); } int aa; if(str[0]=='Q') { scanf("%d",&aa); //cout<<aa<<endl; query(aa,aa,1); } } return 0; } ac代码 #include<stdio.h> const int N = 1000002; struct TREE { int Left; int Right; int num; }; TREE tree[N<<2]; void Build(int root, int l, int r) { tree[root].Left = l; tree[root].Right = r; tree[root].num = 0; if(l < r) { int m = (l + r)>>1; Build(root<<1, l, m); Build(root<<1|1, m + 1, r); } } void Insert(int root, int b, int e, int v) { //[b,e]覆盖了root表示的区间 if(b <= tree[root].Left && tree[root].Right <= e) { tree[root].num += v; return; } int m = (tree[root].Left + tree[root].Right)>>1; //[b,e]位于root的左半区间 if(e <= m) Insert(root<<1, b, e, v); else if(b > m)//[b,e]位于root的右半区间 Insert(root<<1|1, b, e, v); else//[b,e]与两个区间都相交 { Insert(root<<1, b, m, v); Insert(root<<1|1, m + 1, e, v); } } int Query(int root, int x) { if(tree[root].Left == tree[root].Right) return tree[root].num; int m = (tree[root].Left + tree[root].Right)>>1; int sum = tree[root].num; if(x <= m)//询问x所在的那部分区间 sum += Query(root<<1, x); else sum += Query(root<<1|1, x); return sum; } int main() { int n,m; int b,e,v; char str[10]; int i; while(scanf("%d %d", &n, &m) != EOF) { Build(1, 1, m); for(i = 0; i < n; ++i)//这里最开始写成m了，被坑了 { scanf("%s", str); if(str[0] == 'A') { scanf("%d %d %d", &b, &e, &v); Insert(1, b, e, v); } else { scanf("%d", &b); printf("%d\n", Query(1, b)); } } } return 0; }