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
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+;
typedef long long ll; struct op{
int l, r;
ll v;
}o[MAX_N]; ll cnt[MAX_N], a[MAX_N]; struct Node{
int l, r;
ll v;
int mid(){return (l+r)>>;}
}T[MAX_N<<]; void Build(int id, int l, int r){
T[id].l=l, T[id].r=r, T[id].v=;
if(l==r) return;
int mid=T[id].mid();
Build(id<<, l, mid);
Build(id<<|, mid+, r);
}
void Insert(int id, int l, int r, ll v){
Node &now=T[id];
if(now.l>=l&&now.r<=r){
if(~now.v) now.v+=v;
else{
Insert(id<<, l, r, v);
Insert(id<<|, l, r, v);
}
}
else{
Node &lch=T[id<<], &rch=T[id<<|];
if(~now.v) lch.v=rch.v=now.v, now.v=-; //ERROR-PRONE
int mid=now.mid();
if(l<=mid) Insert(id<<, l, r, v);
if(r>mid) Insert(id<<|, l, r, v);
if(lch.v==rch.v) now.v=lch.v;
}
} void Qurery(int id, ll *a){
Node &now=T[id];
if(~now.v)
for(int i=now.l; i<=now.r; i++) a[i]+=now.v;
else{
Qurery(id<<, a);
Qurery(id<<|, a);
}
} int main(){
//freopen("in", "r", stdin);
int N, M, K;
scanf("%d%d%d", &N, &M, &K);
for(int i=; i<=N; i++) scanf("%lld", a+i);
for(int i=; i<=M; i++)
scanf("%d%d%lld", &o[i].l, &o[i].r, &o[i].v);
Build(, , M);
int l, r;
while(K--){
scanf("%d%d", &l, &r);
Insert(, l, r, );
}
Qurery(, cnt);
Build(, , N);
for(int i=; i<=M; i++)
if(cnt[i])
Insert(, o[i].l, o[i].r, o[i].v*cnt[i]);
Qurery(, a);
for(int i=; i<=N; i++)
printf("%lld ", a[i]);
puts("");
return ;
}
上面的代码没有lazy-tag或者说我设置的lazy-tag没起到相应的作用。我的考虑是设置一个tag,最后求答案时可不必细分到每个叶子节点,但是这种优化对降低Insert的复杂度没有太大帮助,而Insert是最耗时的,因而总的复杂度还是没降下来。
AC的姿势
#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5+;
typedef long long ll; struct op{
int l, r, v;
}o[MAX_N]; ll cnt[MAX_N], a[MAX_N]; struct Node{
int l, r;
ll v;
int mid(){return (l+r)>>;}
}T[MAX_N<<]; void Build(int id, int l, int r){
T[id].l=l, T[id].r=r, T[id].v=;
if(l==r) return;
int mid=T[id].mid();
Build(id<<, l, mid);
Build(id<<|, mid+, r);
}
void Insert(int id, int l, int r, ll v){
Node &now=T[id];
if(now.l>=l&&now.r<=r) now.v+=v;
else{
Node &lch=T[id<<], &rch=T[id<<|];
if(now.v)
lch.v+=now.v, rch.v+=now.v, now.v=;
int mid=now.mid();
if(l<=mid) Insert(id<<, l, r, v);
if(r>mid) Insert(id<<|, l, r, v);
}
} void Qurery(int id, ll *a){
Node &now=T[id];
if(now.l==now.r) a[now.l]+=now.v;
else{
Node &lch=T[id<<], &rch=T[id<<|];
if(now.v)
lch.v+=now.v, rch.v+=now.v;
Qurery(id<<, a);
Qurery(id<<|, a);
}
} int main(){
//freopen("in", "r", stdin);
int N, M, K;
scanf("%d%d%d", &N, &M, &K);
for(int i=; i<=N; i++) scanf("%lld", a+i);
for(int i=; i<=M; i++)
scanf("%d%d%lld", &o[i].l, &o[i].r, &o[i].v);
Build(, , M);
int l, r;
while(K--){
scanf("%d%d", &l, &r);
Insert(, l, r, );
}
Qurery(, cnt);
Build(, , N);
for(int i=; i<=M; i++)
if(cnt[i]&&o[i].v)
Insert(, o[i].l, o[i].r, o[i].v*cnt[i]);
Qurery(, a);
for(int i=; i<=N; i++)
printf("%lld ", a[i]);
puts("");
return ;
}