平衡树好题。
考虑整体直接模拟操作。
-
l -1 x- \(x\in[1,l]\)：不用动；
- \(x\in(l,2l]\)：整体减去 \(l\) 之后暴力插回去；
- \(x\in(2l,+\infty)\)：整体减 \(l\) 与第一段合并。
-
l r x：区间加即可
复杂度显然是 2log 的，考虑重新插入一次的时候值会减半。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10;
int n,m,a[N],b[N],c[N];
vector<pair<int,int> >o[N];
vector<int>q[N];
mt19937 rnd(time(0));
struct node{
int fa,ls,rs,rnd,val,laz;
ll ans,tag;
}t[N];
int root;
void pushup(int rt){
if(t[rt].ls)t[t[rt].ls].fa=rt;
if(t[rt].rs)t[t[rt].rs].fa=rt;
t[rt].fa=0;
}
void pushadd(int rt,int x){
if(rt)t[rt].val+=x,t[rt].laz+=x;
}
void pushans(int rt,ll x){
if(rt)t[rt].ans+=x,t[rt].tag+=x;
}
void pushdown(int rt){
if(t[rt].laz){
pushadd(t[rt].ls,t[rt].laz);
pushadd(t[rt].rs,t[rt].laz);
t[rt].laz=0;
}
if(t[rt].tag){
pushans(t[rt].ls,t[rt].tag);
pushans(t[rt].rs,t[rt].tag);
t[rt].tag=0;
}
}
void split(int rt,int val,int &x,int &y){
if(!rt){
x=y=0;return;
}
pushdown(rt);
if(val<t[rt].val)y=rt,split(t[rt].ls,val,x,t[rt].ls);
else x=rt,split(t[rt].rs,val,t[rt].rs,y);
pushup(rt);
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(t[x].rnd<t[y].rnd){
pushdown(x);
t[x].rs=merge(t[x].rs,y);
return pushup(x),x;
}else{
pushdown(y);
t[y].ls=merge(x,t[y].ls);
return pushup(y),y;
}
}
void insert(int x,int &y){
if(!x)return;
pushdown(x);
insert(t[x].ls,y);
insert(t[x].rs,y);
int r1,r2;
split(y,t[x].val,r1,r2);
t[x].fa=t[x].ls=t[x].rs=0;
y=merge(merge(r1,x),r2);
}
ll ans[N];
void update(int rt){
if(t[rt].fa)update(t[rt].fa);
pushdown(rt);
}
ll query(int x){
update(x);
return t[x].ans;
}
int main(){
freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(int i=1,l,r,x;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
o[l].push_back({x,i});
q[r].push_back(i);
}
for(int i=1;i<=n;i++){
for(auto p:o[i]){
int x,id,r1,r2;
tie(x,id)=p;
t[id]={0,0,0,(int)rnd(),x,0,0,0};
split(root,x,r1,r2);
root=merge(merge(r1,id),r2);
}
if(~b[i]){
if(a[i]<=b[i]){
int r1,r2,r3;
split(root,b[i],r2,r3);
split(r2,a[i]-1,r1,r2);
pushans(r2,c[i]);
root=merge(merge(r1,r2),r3);
}
}else{
int r1,r2,r3;
split(root,a[i],r1,r2);
pushans(r2,c[i]);
pushadd(r2,-a[i]);
split(r2,a[i],r2,r3);
insert(r2,r1);
root=merge(r1,r3);
}
for(int x:q[i])ans[x]=query(x);
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}