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 %I64d specifier.
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 分析 线段树。 离线预处理所有Query，统计各operation的次数。 区间Insert，注意使用lazy-tag，点Query答案。 写法 要维护两棵线段树，可并做一棵。 这是我第一次写的，TLE on test 24
1 #include2 using namespace std; 3 const int MAX_N=1e5+10; 4 typedef long long ll; 5 6 struct op{ 7 int l, r; 8 ll v; 9 }o[MAX_N];10 11 ll cnt[MAX_N], a[MAX_N];12 13 struct Node{14 int l, r;15 ll v;16 int mid(){ return (l+r)>>1;}17 }T[MAX_N<<2];18 19 void Build(int id, int l, int r){20 T[id].l=l, T[id].r=r, T[id].v=0;21 if(l==r) return;22 int mid=T[id].mid();23 Build(id<<1, l, mid);24 Build(id<<1|1, mid+1, r);25 }26 void Insert(int id, int l, int r, ll v){27 Node &now=T[id];28 if(now.l>=l&&now.r<=r){29 if(~now.v) now.v+=v;30 else{31 Insert(id<<1, l, r, v);32 Insert(id<<1|1, l, r, v);33 }34 }35 else{36 Node &lch=T[id<<1], &rch=T[id<<1|1];37 if(~now.v) lch.v=rch.v=now.v, now.v=-1; //ERROR-PRONE38 int mid=now.mid();39 if(l<=mid) Insert(id<<1, l, r, v);40 if(r>mid) Insert(id<<1|1, l, r, v);41 if(lch.v==rch.v) now.v=lch.v;42 }43 }44 45 void Qurery(int id, ll *a){46 Node &now=T[id];47 if(~now.v)48 for(int i=now.l; i<=now.r; i++) a[i]+=now.v;49 else{50 Qurery(id<<1, a);51 Qurery(id<<1|1, a);52 }53 }54 55 int main(){56 //freopen("in", "r", stdin);57 int N, M, K;58 scanf("%d%d%d", &N, &M, &K);59 for(int i=1; i<=N; i++) scanf("%lld", a+i);60 for(int i=1; i<=M; i++)61 scanf("%d%d%lld", &o[i].l, &o[i].r, &o[i].v);62 Build(1, 1, M);63 int l, r;64 while(K--){65 scanf("%d%d", &l, &r);66 Insert(1, l, r, 1);67 }68 Qurery(1, cnt);69 Build(1, 1, N);70 for(int i=1; i<=M; i++)71 if(cnt[i])72 Insert(1, o[i].l, o[i].r, o[i].v*cnt[i]);73 Qurery(1, a);74 for(int i=1; i<=N; i++)75 printf("%lld ", a[i]);76 puts("");77 return 0;78 }
上面的代码没有lazy-tag或者说我设置的lazy-tag没起到相应的作用。我的考虑是设置一个tag，最后求答案时可不必细分到每个叶子节点，但是这种优化对降低Insert的复杂度没有太大帮助，而Insert是最耗时的，因而总的复杂度还是没降下来。 AC的姿势
1 #include2 using namespace std; 3 const int MAX_N=1e5+10; 4 typedef long long ll; 5 6 struct op{ 7 int l, r, v; 8 }o[MAX_N]; 9 10 ll cnt[MAX_N], a[MAX_N];11 12 struct Node{13 int l, r;14 ll v;15 int mid(){ return (l+r)>>1;}16 }T[MAX_N<<2];17 18 void Build(int id, int l, int r){19 T[id].l=l, T[id].r=r, T[id].v=0;20 if(l==r) return;21 int mid=T[id].mid();22 Build(id<<1, l, mid);23 Build(id<<1|1, mid+1, r);24 }25 void Insert(int id, int l, int r, ll v){26 Node &now=T[id];27 if(now.l>=l&&now.r<=r) now.v+=v;28 else{29 Node &lch=T[id<<1], &rch=T[id<<1|1];30 if(now.v) 31 lch.v+=now.v, rch.v+=now.v, now.v=0;32 int mid=now.mid();33 if(l<=mid) Insert(id<<1, l, r, v);34 if(r>mid) Insert(id<<1|1, l, r, v);35 }36 }37 38 void Qurery(int id, ll *a){39 Node &now=T[id];40 if(now.l==now.r) a[now.l]+=now.v;41 else{42 Node &lch=T[id<<1], &rch=T[id<<1|1];43 if(now.v) 44 lch.v+=now.v, rch.v+=now.v;45 Qurery(id<<1, a);46 Qurery(id<<1|1, a);47 }48 }49 50 int main(){51 //freopen("in", "r", stdin);52 int N, M, K;53 scanf("%d%d%d", &N, &M, &K);54 for(int i=1; i<=N; i++) scanf("%lld", a+i);55 for(int i=1; i<=M; i++)56 scanf("%d%d%lld", &o[i].l, &o[i].r, &o[i].v);57 Build(1, 1, M);58 int l, r;59 while(K--){60 scanf("%d%d", &l, &r);61 Insert(1, l, r, 1);62 }63 Qurery(1, cnt);64 Build(1, 1, N);65 for(int i=1; i<=M; i++)66 if(cnt[i]&&o[i].v)67 Insert(1, o[i].l, o[i].r, o[i].v*cnt[i]);68 Qurery(1, a);69 for(int i=1; i<=N; i++)70 printf("%lld ", a[i]);71 puts("");72 return 0;73 }