A Simple Problem with Integers
64-bit integer IO format: %lld Java class name: Main
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 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4
Sample Output
4 55 9 15
Source
给你一个数列，每次询问一个区间的和，或者每次将一个区间的所有元素都加上一个数
树状数组天生用来动态维护数组前缀和，其特点是每次更新一个元素的值，查询只能查数组的前缀和，
但这个题目求的是某一区间的数组和，而且要支持批量更新某一区间内元素的值，怎么办呢？实际上，
还是可以把问题转化为求数组的前缀和。
首先，看更新操作$update(s, t, d)$把区间$A[s]...A[t]$都增加$d$，我们引入一个数组$delta[i]$，表示
$A[i]...A[n]$的共同增量，n是数组的大小。那么update操作可以转化为：
1）令$delta[s] = delta[s] + d$，表示将$A[s]...A[n]$同时增加$d$，但这样$A[t+1]...A[n]$就多加了$d$，所以
2）再令$delta[t+1] = delta[t+1] - d$，表示将$A[t+1]...A[n]$同时减$d$
然后来看查询操作$query(s, t)$，求$A[s]...A[t]$的区间和，转化为求前缀和，设$sum[i] = A[1]+...+A[i]$，则
$A[s]+...+A[t] = sum[t] - sum[s-1]$，
那么前缀和$sum[x]$又如何求呢？它由两部分组成，一是数组的原始和，二是该区间内的累计增量和, 把数组A的原始
值保存在数组org中，并且$delta[i]$对$sum[x]$的贡献值为$delta[i] imes (x+1-i)$，那么
[ sum[x] = org[1]+...+org[x] + delta[1] imes x + delta[2] imes (x-1) + delta[3] imes (x-2)+...+delta[x] imes 1]
[= org[1]+...+org[x] + sum_{i = 1}^{x}(delta[i] imes (x+1-i))]
[ sum[x] = sum_{i = 1}^{x}(org[i]) + (x+1) imessum_{i = 1}^{x}(delta[i]) - sum_{i = 1}^{x}(delta[i] imes i) ]
可以转化为 $sum_{i=1}^{x}(org[i]-delta[i]*i)+(x+1)*delta[i]$
这其实就是三个数组org[i], delta[i]和delta[i]*i的前缀和，org[i]的前缀和保持不变，事先就可以求出来，delta[i]和
delta[i]*i的前缀和是不断变化的，可以用两个树状数组来维护。
1 #include <cstdio> 2 #include <cstring> 3 4 using namespace std; 5 typedef long long LL; 6 const int maxn = 100010; 7 LL s[maxn],c[2][maxn]; 8 int n,m; 9 void add(LL *c,int i,LL val) { 10 while(i <= n) { 11 c[i] += val; 12 i += i&-i; 13 } 14 } 15 LL sum(LL *c,int i,LL ret = 0) { 16 while(i > 0) { 17 ret += c[i]; 18 i -= i&-i; 19 } 20 return ret; 21 } 22 int main() { 23 char cmd[4]; 24 LL x,y,z; 25 while(~scanf("%d%d",&n,&m)) { 26 memset(c,0,sizeof c); 27 for(int i = 1; i <= n; ++i) { 28 scanf("%lld",s + i); 29 s[i] += s[i-1]; 30 } 31 while(m--) { 32 scanf("%s",cmd); 33 if(cmd[0] == 'C') { 34 scanf("%lld%lld%lld",&x,&y,&z); 35 add(c[0],x,z); 36 add(c[0],y+1,-z); 37 add(c[1],x,x*z); 38 add(c[1],y+1,-z*(y+1)); 39 } else { 40 scanf("%lld%lld",&x,&y); 41 printf("%lld ",s[y] - s[x-1] + (y+1)*sum(c[0],y) - sum(c[1],y) - x*sum(c[0],x-1) + sum(c[1],x-1)); 42 } 43 } 44 } 45 return 0; 46 }
然后是Splay，灰常灰常慢
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 typedef long long LL; 6 const int maxn = 100010; 7 int seq[maxn],n,m; 8 struct SplayTree{ 9 int v[maxn],lazy[maxn],fa[maxn],ch[maxn][2],sz[maxn]; 10 LL sum[maxn]; 11 int tot,root; 12 void newnode(int &x,int key,int f){ 13 v[x = ++tot] = key; 14 fa[x] = f; 15 lazy[x] = ch[x][0] = ch[x][1] = 0; 16 sz[x] = 1; 17 } 18 void pushup(int x){ 19 sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + v[x]; 20 sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; 21 } 22 void pushdown(int x){ 23 if(lazy[x]){ 24 lazy[ch[x][0]] += lazy[x]; 25 lazy[ch[x][1]] += lazy[x]; 26 sum[ch[x][0]] += (LL)lazy[x]*sz[ch[x][0]]; 27 sum[ch[x][1]] += (LL)lazy[x]*sz[ch[x][1]]; 28 v[ch[x][0]] += lazy[x]; 29 v[ch[x][1]] += lazy[x]; 30 lazy[x] = 0; 31 } 32 } 33 void build(int &x,int L,int R,int f){ 34 if(L > R) return; 35 int mid = (L + R)>>1; 36 newnode(x,seq[mid],f); 37 build(ch[x][0],L,mid - 1,x); 38 build(ch[x][1],mid + 1,R,x); 39 pushup(x); 40 } 41 void init(){ 42 tot = 0; 43 newnode(root,0,0); 44 newnode(ch[root][1],0,root); 45 build(ch[ch[root][1]][0],1,n,ch[root][1]); 46 } 47 void rotate(int x,int kd){ 48 int y = fa[x]; 49 pushdown(y); 50 pushdown(x); 51 ch[y][kd^1] = ch[x][kd]; 52 fa[ch[x][kd]] = y; 53 fa[x] = fa[y]; 54 ch[x][kd] = y; 55 fa[y] = x; 56 if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x; 57 pushup(y); 58 } 59 void splay(int x,int goal){ 60 while(fa[x] != goal){ 61 if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]); 62 else{ 63 int y = fa[x],z = fa[y],s = (y == ch[z][0]); 64 if(x == ch[y][s]){ 65 rotate(x,s^1); 66 rotate(x,s); 67 }else{ 68 rotate(y,s); 69 rotate(x,s); 70 } 71 } 72 } 73 pushup(x); 74 if(!goal) root = x; 75 } 76 void select(int k,int goal){ 77 int x = root; 78 while(k != sz[ch[x][0]]){ 79 if(k < sz[ch[x][0]]) x = ch[x][0]; 80 else{ 81 k -= sz[ch[x][0]] + 1; 82 x = ch[x][1]; 83 } 84 } 85 splay(x,goal); 86 } 87 }spt; 88 int main(){ 89 char op[5]; 90 int x,y,z; 91 while(~scanf("%d%d",&n,&m)){ 92 for(int i = 1; i <= n; ++i) 93 scanf("%d",seq + i); 94 spt.init(); 95 while(m--){ 96 scanf("%s%d%d",op,&x,&y); 97 spt.select(x - 1,0); 98 spt.select(y + 1,spt.root); 99 int RL = spt.ch[spt.ch[spt.root][1]][0]; 100 if(op[0] == 'C'){ 101 scanf("%d",&z); 102 spt.lazy[RL] += z; 103 spt.sum[RL] += z*spt.sz[RL]; 104 spt.v[RL] += z; 105 }else printf("%lld ",spt.sum[RL]); 106 } 107 } 108 return 0; 109 }