本文共 3295 字，大约阅读时间需要 10 分钟。
Description
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.
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
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std; 17 typedef long long LL; 18 const int INF=0x5fffffff; 19 const double EXP=1e-6; 20 const int MS=100005; 21 22 struct node 23 { 24 int l,r; 25 LL sum,inc; //特别注意这里 26 int mid() 27 { 28 return (l+r)/2; 29 } 30 }nodes[4*MS]; 31 32 void creat(int root,int l,int r) 33 { 34 nodes[root].l=l; 35 nodes[root].r=r; 36 nodes[root].sum=0; 37 nodes[root].inc=0; 38 if(l==r) 39 return ; 40 creat(root<<1,l,(l+r)/2); 41 creat(root<<1|1,(l+r)/2+1,r); 42 } 43 44 void insert(int root,int pos,int value) 45 { 46 if(nodes[root].l==nodes[root].r) 47 { 48 nodes[root].sum+=value; 49 return ; 50 } 51 nodes[root].sum+=value; 52 if(pos<=nodes[root].mid()) 53 insert(root<<1,pos,value); 54 else 55 insert(root<<1|1,pos,value); 56 } 57 58 void add(int root,int a,int b,int c) 59 { 60 if(nodes[root].l==a&&nodes[root].r==b) 61 { 62 nodes[root].inc+=c; 63 return ; 64 } 65 nodes[root].sum+=c*(b-a+1); 66 if(b<=nodes[root].mid()) 67 add(root<<1,a,b,c); 68 else if(a>nodes[root].mid()) 69 add(root<<1|1,a,b,c); 70 else 71 { 72 add(root<<1,a,nodes[root].mid(),c); 73 add(root<<1|1,nodes[root].mid()+1,b,c); 74 } 75 } 76 77 LL query(int root,int a,int b) 78 { 79 if(nodes[root].l>=a&&nodes[root].r<=b) 80 return nodes[root].sum+nodes[root].inc*(nodes[root].r-nodes[root].l+1); 81 nodes[root].sum+=nodes[root].inc*(nodes[root].r-nodes[root].l+1); 82 add(root<<1,nodes[root].l,nodes[root].mid(),nodes[root].inc); 83 add(root<<1|1,nodes[root].mid()+1,nodes[root].r,nodes[root].inc); 84 nodes[root].inc=0; 85 if(b<=nodes[root].mid()) 86 return query(root<<1,a,b); 87 else if(a>nodes[root].mid()) 88 return query(root<<1|1,a,b); 89 else 90 return query(root<<1,a,nodes[root].mid())+query(root<<1|1,nodes[root].mid()+1,b); 91 } 92 93 int main() 94 { 95 int N,Q,x,y,z; 96 scanf("%d%d",&N,&Q); 97 creat(1,1,N); 98 for(int i=1;i<=N;i++) 99 {100 scanf("%d",&x);101 insert(1,i,x);102 }103 char cmd[MS];104 while(Q--)105 {106 scanf("%s",cmd);107 if(cmd[0]=='Q')108 {109 scanf("%d%d",&x,&y);110 printf("%lld\n",query(1,x,y));111 }112 else113 {114 scanf("%d%d%d",&x,&y,&z);115 add(1,x,y,z);116 }117 }118 return 0;119 }
转载于:https://www.cnblogs.com/767355675hutaishi/p/3861569.html