数据结构题。个人认为是比较好的数据结构题。题意：给定一个长度为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)的复杂度。
#include <stdio.h>
#include <string.h>
#define maxn 100005
#define lson(c) (c<<1)
#define rson(c) (c<<1|1)
#define mid(x, y) ((x+y)>>1)
typedef long long LL; struct Tree{
LL f[maxn*];
Tree(){
memset(f, , sizeof(f));
}
void init(){
memset(f, , sizeof(f));
}
void push_down(int c){
int l = lson(c), r = rson(c);
f[l] += f[c];
f[r] += f[c];
f[c] = ;
}
void update(int l, int r, int c, int lp, int rp, LL d){
if(lp <= l && r <= rp){
f[c] += d;
return ;
}
push_down(c);
int m = mid(l, r);
if(rp <= m) update(l, m, lson(c), lp, rp, d);
else if(lp > m) update(m + , r, rson(c), lp, rp, d);
else{
update(l, m, lson(c), lp, m, d);
update(m+, r, rson(c), m+, rp, d);
}
}
void query(int c, int l, int r, LL a[], int s){
if(l==r){
if(s)
a[l] = a[l]*f[c];
else a[l] = a[l] + f[c];
return ;
}
push_down(c);
int mid = mid(l, r);
query(lson(c), l, mid, a, s);
query(rson(c), mid+, r, a, s);
}
}insTree, arrTree;
LL a[maxn], ind[maxn];
int ls[maxn], rs[maxn]; int main(){
//freopen("test.in", "r", stdin);
for(int n, m, k; scanf("%d%d%d", &n, &m, &k)!=EOF; ){
insTree.init();
arrTree.init();
for(int i = ; i <= n; i ++){
scanf("%I64d", &a[i]);
}
for(int i = ; i <= m; i ++){
scanf("%d %d %I64d", &ls[i], &rs[i], &ind[i]);
}
for(int i = , x, y; i <= k; i ++){
scanf("%d%d", &x, &y);
insTree.update(, m, , x, y, );
}
insTree.query(, , m, ind, );
for(int i = ; i <= m; i ++){
arrTree.update(, n, , ls[i], rs[i], ind[i]);
}
arrTree.query(, , n, a, );
for(int i = ; i <= n; i ++){
printf("%I64d ", a[i]);
}
printf("\n");
}
}
#include <stdio.h>
#include <string.h>
#define maxn 100005
typedef long long LL;
LL a[maxn], ind[maxn];
LL lx[maxn], ly[maxn];
int px[maxn], py[maxn]; int main(){
//freopen("test.in", "r", stdin);
for(int n, m, k; scanf("%d%d%d", &n, &m, &k)!=EOF; ){
memset(lx, , sizeof(lx));
memset(ly, , sizeof(ly));
for(int i = ; i <= n; i ++) scanf("%I64d", &a[i]);
for(int i = ; i <= m; i ++) scanf("%d%d%I64d", &px[i], &py[i], &ind[i]);
for(int i = , x, y; i <= k; i ++){
scanf("%d%d", &x, &y); lx[x] += , lx[y+] -= ;
}
LL s = ;
for(int i = ; i <= m; i ++){
s += lx[i];
ind[i] = ind[i] *s;
}
for(int i = ; i <= m; i ++){
ly[px[i]] += ind[i];
ly[py[i]+] -= ind[i];
}
s = ;
for(int i = ; i <= n; i ++){
s += ly[i];
printf("%I64d ", a[i] + s);
}
printf("\n");
}
return ;
}