倍增分块与平衡树

· · 题解

首先发现本题每次在每次行走时都形如一个分段函数，但这个分段函数还有一个权值维，就不知道怎么维护了。

所以可以尝试将已知权值放在一起维护，像扫描线一样，将所有询问在 l 处插入，在 r 处删除（并以当前权值获得答案），每次只需要相应修改值域区间即可。

形如 >l 的数 -l 的操作适用倍增分块，即将 [2^k,2^{k+1}) 视为一块，每次将大块直接打标记，将会掉块的取出；等块将合法值取出暴力减，并且这些必定变块。

显然每个数最多变块 O(\log V) 次，可以接受。

考虑动态维护有序值域区间，这个用平衡树维护就可以了，因为 Splay 是相对灵活的，所以我使用了 Splay，总时间复杂度 O((n+m)\log n\log V)，空间 O(n+m)：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e9+7;
using ll=long long;
int n,m,sta[N];
struct dat{int l,r,v;}d[N];
vector<int>ad[N],dl[N];
int L[N],R[N],kt;
int t[N][2],f[N],rt[42];
#define ls t[x][0]
#define rs t[x][1]
#define tp(x) (t[f[x]][1]==x)
#define in(x) (t[f[x]][0]==x||tp(x))
int stk[N],tp;
ll t1[N],t2[N],w[N],v[N];
void ad1(int x,ll d){t1[x]+=d,v[x]-=d;}
void ad2(int x,ll d){t2[x]+=d,w[x]+=d;}
int Ik(int d){
    // cerr<<d<<endl;
    for(int i=kt;i;--i)
        if(d>=L[i])return i;
    assert(0);
    return -1e9;
}
void pd(int x){
    if(t1[x]){
        if(ls)ad1(ls,t1[x]);
        if(rs)ad1(rs,t1[x]);
    }if(t2[x]){
        if(ls)ad2(ls,t2[x]);
        if(rs)ad2(rs,t2[x]);
    }t1[x]=t2[x]=0;
}
void ppd(int x){
    if(in(x))ppd(f[x]);pd(x);
}
void rot(int x){
    int y=f[x],k=tp(x),w=t[x][!k];
    t[f[w]=t[x][!k]=y][k]=w;
    if(in(y))t[f[y]][tp(y)]=x;
    f[x]=f[y],f[y]=x;
}
void splay(int x){ppd(x);
    for(int y=f[x];in(x);rot(x),y=f[x])
        if(in(y))rot(tp(x)^tp(y)?x:y);
}
void ins(int &x,int p){
    if(!x){x=p;return;}
    int k=v[p]>=v[x];pd(x);
    ins(t[x][k],p),f[t[x][k]]=x;
}
void spt(int x,int &L,int &R,int k){//<=k to L
    L=R=0;if(!x)return;
    int mst=0;
    while(1){pd(x);
        if(v[x]<=k){
            mst=x;
            if(rs)x=rs;
            else break;
        }else if(ls)x=ls;
        else break;
    }splay(x);
    if(mst){
        x=mst,splay(x);
        L=x,f[R=rs]=0,rs=0;
    }else L=0,R=x;
}
void Add(int x){int k=Ik(v[x]);ins(rt[k],x),splay(x),rt[k]=x;}
void dfs(int x){
    pd(x);
    if(ls)dfs(ls);
    if(rs)dfs(rs);
    f[x]=ls=rs=0;
    stk[++tp]=x;
}
void PPD(int x){
    if(x){
        pd(x);
        if(ls)PPD(ls);
        if(rs)PPD(rs);
    }
}
void add1(int lm,int vl){
    int l,r,k;tp=0;
    for(k=1;k<=kt;++k)
        if(R[k]>lm&&rt[k])
            if(L[k]<=lm){
                spt(rt[k],rt[k],r,lm);
                ad1(r,lm),ad2(r,vl);
                if(r)dfs(r);
            }else{
                ad1(rt[k],lm),ad2(rt[k],vl);
                spt(rt[k],l,rt[k],L[k]-1);
                if(l)dfs(l);
            }
    while(stk[tp])Add(stk[tp--]);
}
int mg(int x,int y){
    if(!x||!y)return x|y;
    while(rs)x=rs;
    splay(x),f[rs=y]=x;return x;
}
void add2(int lm,int vl){
    int l,r,k;
    for(k=1;k<=kt;++k)
        if(L[k]<lm&&rt[k])
            if(R[k]>=lm){
                spt(rt[k],l,r,lm-1);
    // printf("l:%d r:%d\n",l,r);
    // for(int x=1;x<=m;++x)
    //  if(sta[x])printf("x:%d v:%d w:%lld ls:%d rs:%d f:%d\n",x,v[x],w[x],ls,rs,f[x]);
                if(l)ad2(l,vl);
                rt[k]=mg(l,r);
            }else ad2(rt[k],vl);
}
int main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y,lm,vl;
    cin>>n>>m;
    for(i=1;i<=n;++i)
        cin>>d[i].l>>d[i].r>>d[i].v;
    for(i=1;i<=m;++i){
        cin>>l>>r>>v[i];
        ad[l].push_back(i);
        dl[r].push_back(i);
    }
    for(l=kt=0;l<=M;l=r+1){
        r=min(3ll*(l+1),1ll*M),++kt;
        L[kt]=l,R[kt]=r;
    }
    for(i=1;i<=n;++i){
        for(int x:ad[i])Add(x),sta[x]=1;
        if(d[i].r==-1)add1(d[i].l,d[i].v);
        else add2(d[i].l,-d[i].v),add2(d[i].r+1,d[i].v);
        for(int x:dl[i]){
            splay(x);
            f[ls]=f[rs]=0;
            k=Ik(v[x]);
            rt[k]=mg(ls,rs);
        }
        // PPD(rt[1]),PPD(rt[2]);
        // exit(0);
    }
    for(i=1;i<=m;++i)
        printf("%lld\n",w[i]);
    return 0;
}