CF702F T-shirts题解

Iceturky · 2024-07-26 22:09:09 · 题解

Link

考虑衣服来减人的钱而非人买衣服。这样只需要衣服顺序加入即可完成对 q 的限制。

问题转化为有一个集合，每次把集合分为两部分，一部分小于 c ，另一部分大于等于 c ，使第二部分元素的计数器增加，值减少 c ，再合并两个集合。看起来很像平衡树，但中间会有重叠。

考虑重叠部分，发现其都至少减少了一半。因此对于重叠的部分直接暴力插入，每一个元素最多会被暴力插入 \mathrm{O(\log w)} 次，不重叠部分直接合并即可。

实现上使用了 splay ，每次将树分为三部分，小于 c ，介于 c+1 与 2c 之间与大于 2c 。中间部分暴力修改后暴力插入到第一个集合内，后面部分直接打标记，与第一部分合并。由于这两部分没有交，所以合并是均摊 \mathrm{O(\log n)} 。

中间因为在 find 时没有把找的那个点的 tag 给 pushdown 调了好久。

code

const int N=2e5+5;

struct shirts{
    int c,p;
    bool operator<(shirts ano)const{
        return p==ano.p?c<ano.c:p>ano.p;
    }
}a[N];

int ans[N];

struct Splay{
    struct node{
        int fa,s[2];
        int val;
        int cnt,id;
        int tag1,tag2;
    }t[N<<5];
    int rt,idx;
    Splay(){
        rt=idx=0;
    }
    void pushdown(int x){
        if(t[x].tag1==0&&t[x].tag2==0)
            return;
        if(t[x].s[0]){
            t[t[x].s[0]].tag1+=t[x].tag1;
            t[t[x].s[0]].tag2+=t[x].tag2;
            t[t[x].s[0]].val+=t[x].tag1;
            t[t[x].s[0]].cnt+=t[x].tag2;
        }
        if(t[x].s[1]){
            t[t[x].s[1]].tag1+=t[x].tag1;
            t[t[x].s[1]].tag2+=t[x].tag2;
            t[t[x].s[1]].val+=t[x].tag1;
            t[t[x].s[1]].cnt+=t[x].tag2;
        }
        t[x].tag1=t[x].tag2=0;
    }
    void rotate(int x){
        int y=t[x].fa,z=t[y].fa;
        pushdown(z),pushdown(y);pushdown(x);
        bool w=x==t[y].s[1];
        if(z)
            t[z].s[y==t[z].s[1]]=x;
        t[x].fa=z;
        t[y].s[w]=t[x].s[w^1];
        t[t[x].s[w^1]].fa=y;
        t[x].s[w^1]=y;
        t[y].fa=x;
    }
    void splay(int x,int k){
        if(x==0||x==k)
            return;
        while(t[x].fa!=k){
            int y=t[x].fa;
            if(t[y].fa!=k){
                int z=t[y].fa;
                if((x==t[y].s[1])^(y==t[z].s[1]))
                    rotate(x);
                else
                    rotate(y);
            }rotate(x);
        }
        if(k==0)
            rt=x;
    }
    int fd(int x,int num){
        while(t[x].s[num>t[x].val])
            pushdown(x),x=t[x].s[num>t[x].val];
        pushdown(x);
        return x;
    }
    void insert(int num,int id,int cnt){
        int y=fd(rt,num);
        int x=++idx;
        t[x].cnt=cnt,t[x].id=id;
        t[y].s[num>t[y].val]=x;
        t[x].fa=y;
        t[x].s[0]=t[x].s[1]=t[x].tag1=t[x].tag2=0;
        t[x].val=num;
        splay(x,0);
    }
    void clr(int x){
        if(x==0)
            return;
        pushdown(x);
//      cout<<"clr"<<x<<" "<<t[x].id<<" "<<t[x].val<<" "<<t[x].cnt<<endl;
        insert(t[x].val,t[x].id,t[x].cnt);
        clr(t[x].s[0]);
        clr(t[x].s[1]);
    }
    void update(int num){
        splay(fd(rt,num),0);
        if(t[rt].val>=num)
            splay(fd(t[rt].s[0],inf),0);
//      cout<<t[rt].val<<endl;
        splay(fd(t[rt].s[1],num*2),rt);
        int tmp=t[rt].s[1];
        if(t[tmp].val<num*2)
            splay(fd(t[tmp].s[1],-inf),rt);//可能会存在不存在这一部分的情况
        tmp=t[rt].s[1];
//      cout<<"rt:"<<t[tmp].id<<" "<<t[tmp].val<<" "<<t[tmp].cnt<<" "<<t[tmp].tag1<<" "<<t[tmp].tag2<<endl;
//      cout<<"ls:"<<t[t[tmp].s[0]].id<<" "<<t[t[tmp].s[0]].val<<" "<<t[t[tmp].s[0]].cnt<<" "<<t[t[tmp].s[0]].tag1<<" "<<t[t[tmp].s[0]].tag2<<endl;
//      cout<<"rs:"<<t[t[tmp].s[1]].id<<" "<<t[t[tmp].s[1]].val<<" "<<t[t[tmp].s[1]].cnt<<" "<<t[t[tmp].s[1]].tag1<<" "<<t[t[tmp].s[1]].tag2<<endl;
        t[tmp].tag1+=-num;
        t[tmp].tag2++;
        t[tmp].val+=-num;
        t[tmp].cnt++;
        pushdown(tmp);
        int tmpp=t[tmp].s[0];
        t[tmp].s[0]=0;
        clr(tmpp);
    }
    void output(int x){
        int tmp=x;
        cout<<"x:"<<t[tmp].id<<" "<<t[tmp].val<<" "<<t[tmp].cnt<<" "<<t[tmp].tag1<<" "<<t[tmp].tag2<<endl;
        cout<<"ls:"<<t[t[tmp].s[0]].id<<" "<<t[t[tmp].s[0]].val<<" "<<t[t[tmp].s[0]].cnt<<" "<<t[t[tmp].s[0]].tag1<<" "<<t[t[tmp].s[0]].tag2<<endl;
        cout<<"rs:"<<t[t[tmp].s[1]].id<<" "<<t[t[tmp].s[1]].val<<" "<<t[t[tmp].s[1]].cnt<<" "<<t[t[tmp].s[1]].tag1<<" "<<t[t[tmp].s[1]].tag2<<endl;
        if(t[tmp].s[0])
            output(t[tmp].s[0]);
        if(t[tmp].s[1])
            output(t[tmp].s[1]);
    }
    void dfs(int x){
        pushdown(x);
//      print(x),pc(' '),print(t[x].id),pc(' '),print(t[x].val),pc(' '),print(t[x].cnt),pc('\n');
        ans[t[x].id]=t[x].cnt;
        if(t[x].s[0])
            dfs(t[x].s[0]);
        if(t[x].s[1])
            dfs(t[x].s[1]);
    }
}T;

signed main(){
    signed n=read();
    for(int i=1;i<=n;i++)
        a[i]={read(),read()};
    sort(a+1,a+1+n);
    int m=read();
    T.insert(inf,0,0);
//      T.dfs(T.rt),pc('\n'),
    T.insert(-inf,0,0);
//      T.dfs(T.rt),pc('\n');
    for(int i=1;i<=m;i++)
//      T.dfs(T.rt),pc('\n'),
        T.insert(read(),i,0);
//  T.dfs(T.rt),pc('\n');
    for(int i=1;i<=n;i++){
//      T.dfs(T.rt);
//      cout<<endl;
//      cout<<a[i].c<<endl;
//      cout<<endl;
        T.update(a[i].c);
//      T.output(T.rt);
    }
    T.dfs(T.rt);
    for(int i=1;i<=m;i++)
        print(ans[i]),pc(' ');
    pc('\n');
    return 0;
}