2 seconds
256 megabytes
standard input
standard output
Greg has an array a = a1, a2, ..., an and m operations.
Each operation looks as: li, ri, di, (1 ≤ li ≤ ri ≤ n).
To apply operation i to the array means to increase all array elements with numbers li, li + 1, ..., ri by
value di.
Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 ≤ xi ≤ yi ≤ m).
That means that one should apply operations with numbers xi, xi + 1, ..., yi to
the array.
Now Greg is wondering, what the array a will be after all the queries are executed. Help Greg.
The first line contains integers n, m, k (1 ≤ n, m, k ≤ 105).
The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105) —
the initial array.
Next m lines contain operations, the operation number i is
written as three integers: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).
Next k lines contain the queries, the query number i is
written as two integers: xi, yi, (1 ≤ xi ≤ yi ≤ m).
The numbers in the lines are separated by single spaces.
On a single line print n integers a1, a2, ..., an —
the array after executing all the queries. Separate the printed numbers by spaces.
Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred
to use the cin, cout streams of the %I64dspecifier.
3 3 3 1 2 3 1 2 1 1 3 2 2 3 4 1 2 1 3 2 3
9 18 17
1 1 1 1 1 1 1 1 1
2
4 3 6 1 2 3 4 1 2 1 2 3 2 3 4 4 1 2 1 3 2 3 1 2 1 3 2 3
5 18 31 20
一道关于线段树的题目
最下面的代码在第26组数据跑超时了！
正确的解法是构建两颗线段树：
两棵线段树，一棵维护每种指令用了多少次，一棵维护每段被怎么更新，时间复杂度都是nlogn级别的
很有代表性！！！！！
值得学习
b树用来保存节点修改的次数
a树用来具体计算！！
AC代码如下:注意数据是否溢出很多地方要用LongLong要注意！！！！
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <sstream> #include <vector> #include <stack> #include <map> #include <queue> #include <set> #include <iostream> #include <stdlib.h> #include <cctype> #define rep1(i,s,e) for(int i = (s);i<(e);++i) #define rep2(i,s,e) for(int i = (s);i<=(e);++i) #define maxn 310000 #define INF 1000000007 #define ls (root<<1) #define rs (root<<1|1) #define M L+(R-L)/2 using namespace std; int n,m,k; struct operation { int from; int to; long long val; }op[maxn]; struct tree { long long sum[maxn<<2]; long long addv[maxn<<2]; void push_up(int root) { sum[root] = sum[root<<1] + sum[root<<1|1]; } void push_down(int root,int m)//m为root节点的区间长度？ { if(addv[root])//节点有标记才往下传 { addv[root<<1] += addv[root]; addv[root<<1|1] += addv[root]; sum[root<<1] += addv[root]*(m-(m>>1)); sum[root<<1|1] += addv[root]*(m>>1); addv[root] = 0;//清楚本节点标记 } } void build(int root ,int L,int R) { int m = L+(R-L)/2; addv[root] = 0; if(L==R) { scanf("%lld",&sum[root]); return ; } build(root<<1,L,m); build(root<<1|1,m+1,R); push_up(root); } void update(int l,int r,long long v,int root ,int L,int R) { if(l<=L&&r>=R)//修改区间包括了[L,R]那么整个区间修改 { addv[root] += v;//更新每个节点的addv值 sum[root] += v*(R-L+1); return ; } int m =L+(R-L)/2; push_down(root,R-L+1);//将改变传递到子节点 if(l<=m) update(l,r,v,root<<1,L,m); if(r>m) update(l,r,v,root<<1|1,m+1,R); push_up(root); } long long query(int p,int root,int L,int R) { int m = L+(R-L)/2; if(L==R) { return sum[root]; } push_down(root,R-L+1); if(p<=m) return query(p,root<<1,L,m); else return query(p,root<<1|1,m+1,R); } }a,b; int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&k)==3) { memset(b.sum, 0, sizeof(b.sum)); memset(b.addv, 0, sizeof(b.addv)); a.build(1,1,n); for(int i = 1;i<=m;++i) { scanf("%d%d%I64d",&op[i].from,&op[i].to,&op[i].val); } for(int i = 0;i<k;++i) { int l,r; scanf("%d%d",&l,&r); b.update(l,r,1,1,1,m); } for(int i = 1;i<=m;++i) { long long temp = b.query(i,1,1,m); a.update(op[i].from,op[i].to,op[i].val*temp,1,1,n); } for(int i = 1;i<=n;++i) printf("%I64d ",a.query(i,1,1,n)); printf("\n"); } return 0; }#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <sstream> #include <vector> #include <stack> #include <map> #include <queue> #include <set> #include <iostream> #include <stdlib.h> #include <cctype> #define rep1(i,s,e) for(int i = (s);i<(e);++i) #define rep2(i,s,e) for(int i = (s);i<=(e);++i) #define maxn 310000 #define INF 1000000007 #define ls (root<<1) #define rs (root<<1|1) #define M L+(R-L)/2 using namespace std; int n,m,k; struct operation { long long from; long long to; long long val; }op[maxn]; long long sum[maxn<<2]; long long addv[maxn<<2]; bool changed[maxn<<2]; void push_down(int root,int m)//m为root节点的区间长度？ { if(addv[root])//节点有标记才往下传 { addv[root<<1] += addv[root]; addv[root<<1|1] += addv[root]; sum[root<<1] += addv[root]; sum[root<<1|1] += addv[root]; addv[root] = 0;//清楚本节点标记 } } void build(int root ,int L,int R) { int m = L+(R-L)/2; addv[root] = 0; if(L==R) { scanf("%I64d",&sum[root]); return ; } build(root<<1,L,m); build(root<<1|1,m+1,R); //push_up(root); } void update(int l,int r,int v,int root ,int L,int R) { if(l<=L&&r>=R)//修改区间包括了[L,R]那么整个区间修改 { addv[root] += v;//更新每个节点的addv值 sum[root] += v;//*(R-L+1); return ; } int m =L+(R-L)/2; push_down(root,R-L+1);//将改变传递到子节点 if(l<=m) update(l,r,v,root<<1,L,m); if(r>m) update(l,r,v,root<<1|1,m+1,R); //push_up(root); } long long query(int p,int root,int L,int R) { int m = L+(R-L)/2; if(L==R) { return sum[root]; } push_down(root,R-L+1); if(p<=m) query(p,root<<1,L,m); else query(p,root<<1|1,m+1,R); } long long num[maxn]; long long temp[maxn]; int main() { freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&k)==3) { memset(num,0,sizeof(num)); build(1,1,n); for(int i = 1;i<=m;++i) { scanf("%I64d%I64d%I64d",&op[i].from,&op[i].to,&op[i].val); } for(int i = 0;i<k;++i) { int a,b; scanf("%d%d",&a,&b); for(int j = a;j<=b;++j) { num[j]++; } } for(int i = 1;i<=m;++i) { op[i].val *= num[i]; if(num[i]==0) continue; update(op[i].from,op[i].to,op[i].val,1,1,n); } for(int i = 1;i<=n;++i) printf("%I64d ",query(i,1,1,n)); printf("\n"); } return 0; }