数据结构题。个人认为是比较好的数据结构题。题意：给定一个长度为n的数组a，然后给定m个操作序列，每个操作：l, r, x将区间[l, r]内的元素都增加a,然后有k个查询，查询形式是对于操作序列x,y是将第x个操作到第y个操作执行一遍。然后求最后的数组的元素值。
1.线段树解法：维护两棵线段树，一棵用于维护执行的操作序列的执行次数，一棵用于维护数组a的值。复杂度O(nlogn)。
2.扫描区间。对于数组和操作序列分别维护一个数组lx[],ly[]。ly[i]表示区间[i, m]中每个操作执行的次数，lx[i]表示区间[i, n]中每个数的增量的值。O(n)的复杂度。
1 #include <stdio.h> 2 #include <string.h> 3 #define maxn 100005 4 #define lson(c) (c<<1) 5 #define rson(c) (c<<1|1) 6 #define mid(x, y) ((x+y)>>1) 7 typedef long long LL; 8 9 struct Tree{ 10 LL f[maxn*4]; 11 Tree(){ 12 memset(f, 0, sizeof(f)); 13 } 14 void init(){ 15 memset(f, 0, sizeof(f)); 16 } 17 void push_down(int c){ 18 int l = lson(c), r = rson(c); 19 f[l] += f[c]; 20 f[r] += f[c]; 21 f[c] = 0; 22 } 23 void update(int l, int r, int c, int lp, int rp, LL d){ 24 if(lp <= l && r <= rp){ 25 f[c] += d; 26 return ; 27 } 28 push_down(c); 29 int m = mid(l, r); 30 if(rp <= m) update(l, m, lson(c), lp, rp, d); 31 else if(lp > m) update(m + 1, r, rson(c), lp, rp, d); 32 else{ 33 update(l, m, lson(c), lp, m, d); 34 update(m+1, r, rson(c), m+1, rp, d); 35 } 36 } 37 void query(int c, int l, int r, LL a[], int s){ 38 if(l==r){ 39 if(s) 40 a[l] = a[l]*f[c]; 41 else a[l] = a[l] + f[c]; 42 return ; 43 } 44 push_down(c); 45 int mid = mid(l, r); 46 query(lson(c), l, mid, a, s); 47 query(rson(c), mid+1, r, a, s); 48 } 49 }insTree, arrTree; 50 LL a[maxn], ind[maxn]; 51 int ls[maxn], rs[maxn]; 52 53 int main(){ 54 //freopen("test.in", "r", stdin); 55 for(int n, m, k; scanf("%d%d%d", &n, &m, &k)!=EOF; ){ 56 insTree.init(); 57 arrTree.init(); 58 for(int i = 1; i <= n; i ++){ 59 scanf("%I64d", &a[i]); 60 } 61 for(int i = 1; i <= m; i ++){ 62 scanf("%d %d %I64d", &ls[i], &rs[i], &ind[i]); 63 } 64 for(int i = 1, x, y; i <= k; i ++){ 65 scanf("%d%d", &x, &y); 66 insTree.update(1, m, 1, x, y, 1); 67 } 68 insTree.query(1, 1, m, ind, 1); 69 for(int i = 1; i <= m; i ++){ 70 arrTree.update(1, n, 1, ls[i], rs[i], ind[i]); 71 } 72 arrTree.query(1, 1, n, a, 0); 73 for(int i = 1; i <= n; i ++){ 74 printf("%I64d ", a[i]); 75 } 76 printf("\n"); 77 } 78 }
1 #include <stdio.h> 2 #include <string.h> 3 #define maxn 100005 4 typedef long long LL; 5 LL a[maxn], ind[maxn]; 6 LL lx[maxn], ly[maxn]; 7 int px[maxn], py[maxn]; 8 9 int main(){ 10 //freopen("test.in", "r", stdin); 11 for(int n, m, k; scanf("%d%d%d", &n, &m, &k)!=EOF; ){ 12 memset(lx, 0, sizeof(lx)); 13 memset(ly, 0, sizeof(ly)); 14 for(int i = 1; i <= n; i ++) scanf("%I64d", &a[i]); 15 for(int i = 1; i <= m; i ++) scanf("%d%d%I64d", &px[i], &py[i], &ind[i]); 16 for(int i = 1, x, y; i <= k; i ++){ 17 scanf("%d%d", &x, &y); lx[x] += 1, lx[y+1] -= 1; 18 } 19 LL s = 0; 20 for(int i = 1; i <= m; i ++){ 21 s += lx[i]; 22 ind[i] = ind[i] *s; 23 } 24 for(int i = 1; i <= m; i ++){ 25 ly[px[i]] += ind[i]; 26 ly[py[i]+1] -= ind[i]; 27 } 28 s = 0; 29 for(int i = 1; i <= n; i ++){ 30 s += ly[i]; 31 printf("%I64d ", a[i] + s); 32 } 33 printf("\n"); 34 } 35 return 0; 36 }