题解：AT_abc389_f [ABC389F] Rated Range

emmoy · 2025-01-19 10:49:44 · 题解

提供一个平衡树做法。

首先你可以将询问离线下来，排序后塞进一棵文艺平衡树里，然后枚举 i\in[1,n]，根据 l_i-1 与 r_i 将 FHQ split 开，打个加一的 tag 再 merge 回去，最后将所有 tag 下传就行了。

#include<bits/stdc++.h>
#define N 700010
using namespace std;
int n,m,sz[N],ls[N],rs[N],val[N],lasy[N],f[N];
unsigned int rd[N];
mt19937 rnd(time(0));
int root,cnt;
int g(int x,int y)
{
    sz[++cnt]=1,val[cnt]=x,rd[cnt]=rnd();
    f[cnt]=y;
    return cnt;
}
void upd(int p)
{
    sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
void pushdown(int p)
{
    if(lasy[p])
    {
        if(ls[p]) lasy[ls[p]]+=lasy[p],val[ls[p]]+=lasy[p];
        if(rs[p]) lasy[rs[p]]+=lasy[p],val[rs[p]]+=lasy[p];
        lasy[p]=0;
    }
}
void split(int p,int k,int &x,int &y)
{
    if(!p) {x=y=0;return ;}
    pushdown(p);
    if(k<val[p]) y=p,split(ls[p],k,x,ls[p]);
    else x=p,split(rs[p],k,rs[p],y);
    upd(p);
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    if(rd[x]<rd[y])
    {
        pushdown(x);
        rs[x]=merge(rs[x],y);
        upd(x);
        return x;
    }
    else{
        pushdown(y);
        ls[y]=merge(x,ls[y]);
        upd(y);
        return y;
    }
}
void solve(int l,int r)
{
    int x,y;
    split(root,l-1,x,y);
    int u,v;
    split(y,r-l+1,u,v);
    lasy[u]^=1;
    root=merge(x,merge(u,v));
}
int l[N],r[N];
struct node{
    int val,id;
}h[N];
int ans[N];
void solve(int p)
{
    if(!p) return;
    pushdown(p);
    ans[f[p]]=val[p];
    print(ls[p]);
    print(rs[p]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    cin>>m;
    for(int i=1;i<=m;i++) cin>>h[i].val,h[i].id=i;
    sort(h+1,h+1+m,[&](node x,node y){return x.val<y.val;});
    for(int i=1;i<=m;i++) root=merge(root,g(h[i].val,h[i].id));
    for(int i=1;i<=n;i++){
        int x,y,z;
        split(root,l[i]-1,x,y);
        split(y,r[i],y,z);
        lasy[y]++,val[y]++;
        root=merge(x,merge(y,z));
    }
    solve(root);
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}