题解：P10540 [THUPC 2024 决赛] 古明地枣的袜子

· · 题解

考虑换维，将操作按 x 降序第一关键字 y 升序第二关键字，则每次查询形如选出一些数求最大前缀和。分块，每块对 O(B^2) 种选操作可能预处理出总和和最大前缀和，查询把所有块信息拼起来即可。注意这里求最大前缀和不算 x=n 的操作，把它们的贡献钦定算在答案里。

每块的预处理容易扫描线做到 O(B^2\log B)，但并不优秀，可以做到 O(B^2)，考虑分治，合并直接枚举选法做即可，T(n)=2T(\frac{n}{2})+O(n^2)\implies T(n)=O(n^2)，注意选法枚举应与分治段长相关而非每次都 O(B^2) 枚举。

const int N=5e5+5,B=1e3,BC=N/B+5;

int n,m,q;
struct node{int x;ll y;int i;}ns[N];

namespace bit{
    ll dat[N];
    void modify(int x,ll v){for(;x<=n;x+=x&-x)dat[x]+=v;}
    ll query(int x){ll v=0;for(;x;x-=x&-x)v+=dat[x];return v;}
    ll query(int lq,int rq){return query(rq)-query(lq-1);}
}

int bc,lb[BC],rb[BC];
struct NODE{
    vec<pii> a;
    vec<vec<ll>> s,f;
    void clear(){vec<pii>().swap(a),vec<vec<ll>>().swap(s),vec<vec<ll>>().swap(f);};
}dat;
vec<int> ne,la;
void build(int l,int r,NODE &dat){
    if(l==r){
        dat=NODE();
        dat.a.pub(l,0);
        dat.s.resize(1,vec<ll>(1,ns[l].y));
        dat.f.resize(1,vec<ll>(1,max(ns[l].y,0ll)));
        return;
    }
    int m=l+r>>1;NODE L,R;
    build(l,m,L),build(m+1,r,R);
    dat.a.resize(L.a.size()+R.a.size());
    for(int it=0,lt=0,rt=0;lt<L.a.size()||rt<R.a.size();++it)
        if(lt==L.a.size())dat.a[it]={R.a[rt++].fir,1};
        else if(rt==R.a.size())dat.a[it]={L.a[lt++].fir,0};
        else dat.a[it]=ns[L.a[lt].fir].i<ns[R.a[rt].fir].i?pii{L.a[lt++].fir,0}:pii{R.a[rt++].fir,1};
    dat.f.resize(dat.a.size(),vec<ll>(dat.a.size())),dat.s.resize(dat.a.size(),vec<ll>(dat.a.size()));
    int lt=-1,rt=-1;
    repl(l,0,dat.a.size()){
        int lr=lt,rr=rt;
        repl(r,l,dat.a.size()){
            ++(dat.a[r].sec?rr:lr);
            dat.s[l][r]=(lt<lr?L.s[lt+1][lr]:0)+(rt<rr?R.s[rt+1][rr]:0);
            dat.f[l][r]=max((lt<lr?L.f[lt+1][lr]:0),(lt<lr?L.s[lt+1][lr]:0)+(rt<rr?R.f[rt+1][rr]:0));
        }
        ++(dat.a[l].sec?rt:lt);
    }
    L.clear(),R.clear();
}

pii qs[N];
ll ans[N],sum[N];

void INIT(){}
void MAIN(){
    read(n,q);
    rep(i,1,n){int x,y;read(x,y);x<n?ns[++m]={x,y,i},void():bit::modify(i,y);}
    sort(ns+1,ns+1+m,[&](node a,node b){return a.x==b.x?a.y<b.y:a.x>b.x;});
    bc=(m-1)/B+1;
    rep(i,1,q)read(qs[i].fir,qs[i].sec);
    rep(i,1,bc){
        lb[i]=(i-1)*B+1,rb[i]=min(m,i*B),build(lb[i],rb[i],dat);
        ne.resize(n+2),la.resize(n+2);int it;
        it=0;la[0]=-1;rep(j,1,n)la[j]=it<dat.a.size()&&ns[dat.a[it].fir].i==j?it++:la[j-1];
        it=dat.a.size()-1;ne[n+1]=it+1;per(j,n,1)ne[j]=~it&&ns[dat.a[it].fir].i==j?it--:ne[j+1];
        rep(j,1,q){
            auto [l,r]=qs[j];
            if(ne[l]<=la[r])chmax(ans[j],sum[j]+dat.f[ne[l]][la[r]]),sum[j]+=dat.s[ne[l]][la[r]];
        }
    }
    rep(i,1,q)put(ans[i]+bit::query(qs[i].fir,qs[i].sec));
}