Codeforces 702F T-shirt 可持久化Treap练手

Description

给出n件T-shirt的重要程度qi和花费ci，有k个人最开始分别有bi的金钱，每个人的选衣服的策略都是一样的：将所有T-shirt按照重要程度q从大到小排序，重要程度相同的按花费从小到大排，然后每个人从头开始取T-shirt，如果金钱数大于当前的T-shirt的花费，那么就买下这件衣服，问每个人最多能够买的T-shirt数量。

Data Constraint

1≤n,k≤2⋅105 1≤ci,qi≤109 1≤bj≤109

最暴力的做法

将所有的T-shirt按照题目要求排序，对于每一个人，从前往后扫，能买就买，不能买就跳过，最后算出答案。

可持久化Treap

最近学了可持久化Treap，便找了道题来练练手。
上述做法是O(nk)，显然会超时。
将所有的人按照bi排序，建出一棵Treap。
然后按顺序枚举每一件T-shirt，对于当前的第i件T-shirt，将Treap split成两棵Treap，记为T1和T2。T1里的bi全部小于ci(即买不起这件T-shirt的人)，T2里的bi全部大于等于ci，于是便给T2打上一个标记，将T2内的全部bi减掉ci，答案加1。
如果我们这是便简单地将两棵Treap合并为一棵，便很有可能破坏序列的有序性。
因而，在合并之前，我们还需调整T1和T2，不停调整直到使得T1中的最大值小于等于T2中的最小值，随后才能合并。
对于每次调整，找出T2内的最小值（记为 k），与T1内的最大值（记为 p）比较，若k<p则暴力用O(log n)的时间将k从T2中split掉，再用split和merge操作把k加入T1中。
这样做看上去好像会超时，但我们分析一下复杂度，便能发现这是O(n log22 n)的。
证明:
设k在被减掉ci前的金钱数为v（v=k+ci），显然有ci>p，减掉ci后便有p>v-ci，
于是便有ci>p>v-ci，整理得ci>v2
这也就意味着每一次v减完ci后会被调整(从T2调整到T1)，当且仅当v减去了一个大于自己一半的ci，因而对于每一个bi，最多会被暴力调整log n次，调整一次是O(log n)的，因而总的时间复杂度就是O(n log22 n)。

Code

#include<iostream> 
#include<cstdio>
#include<cstring>
#pragma GCC optimize(3) 
#include<algorithm> 
#include<ctime>

#define fo(i,j,l) for(int i=j;i<=l;i++)
#define fd(i,j,l) for(int i=j;i>=l;i--) 
#define fi first
#define se second
#define random(x) rand()%x

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const ll N=42e4,maxn=6e9;
struct note{
    int l,r,size;
    ll rnd;
}s[N];
struct nnn{
    ll v,c;
}gift[N],pe[N];

ll down[N],mo[N],va[N],h[N],dy[N];
int n,m,j,k,l,i,o,root;
ll ans[N];
void getdown(int o)
{
    mo[s[o].l]-=down[o];
    down[s[o].l]+=down[o];
    mo[s[o].r]-=down[o];
    down[s[o].r]+=down[o];
    va[s[o].l]+=h[o];
    va[s[o].r]+=h[o];
    h[s[o].l]+=h[o];
    h[s[o].r]+=h[o];
    down[o]=h[o]=0;
}

int merge(int a,int b)
{
    if(!(a*b))return a^b;
    if(!down[a])getdown(a);
    if(!down[b])getdown(b);
    if(s[a].rnd<s[b].rnd){
        int ls=merge(s[a].r,b);
        s[a].r=ls; 
        s[a].size=s[s[a].l].size+s[ls].size+1; 
        return a;
    }else{
        int ls=merge(a,s[b].l);
        s[b].l=ls;
        s[b].size=s[ls].size+s[s[b].r].size+1;
        return b;
    }
}

P split(int o,int wz)
{
    if(!wz)return P(0,o);
    if(down[o]!=0)getdown(o);
    if(s[s[o].l].size>=wz){
        P ls=split(s[o].l,wz);
        s[o].l=ls.se;
        s[o].size=s[s[o].r].size+s[ls.se].size+1;
        return P(ls.fi,o);
    }else{
        P ls=split(s[o].r,wz-s[s[o].l].size-1);
        s[o].r=ls.fi;
        s[o].size=s[s[o].l].size+s[ls.fi].size+1;
        return P(o,ls.se);
    }
}

int search(int o,ll p)
{
    if(o==0)return 0;
    if(down[o]!=0)getdown(o);
    if(mo[o]>=p) return search(s[o].l,p);
    else return s[s[o].l].size+1+search(s[o].r,p);
}

ll read()
{
    ll o=0; char ch=' ';
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar())o=o*10+ch-48;
    return o;
}

void pri(ll o)
{
    if(!o)return;
    pri(o/10); putchar('0'+o%10);
}

void write(ll o)
{
    if(o==0)putchar('0');
    pri(o);
}

bool kmp(nnn a,nnn b){
    return a.v!=b.v ? a.v>b.v : a.c<b.c;
}

bool kmp2(nnn a,nnn b){
    return a.v<b.v;
}

int main()
{
    cin>>n;
    fo(i,1,n)gift[i].c=read(),gift[i].v=read();
    sort(gift+1,gift+n+1,kmp);
    cin>>m;
    fo(i,1,m)pe[i].v=read(),pe[i].c=i;
    sort(pe+1,pe+m+1,kmp2);
    fo(i,1,m)mo[i]=pe[i].v;
    srand(time(0));
    fo(i,1,m){
        s[i].size=1;
        s[i].rnd=random(maxn);
        if(i==1)root=1;else root=merge(root,i);
    }
    ll zd=0;
    fo(i,1,n){
        int k=search(root,gift[i].c);
        if(k==m)continue;
        if(k==0){
            mo[root]-=gift[i].c;
            va[root]+=1;
            down[root]+=gift[i].c;
            h[root]+=1;
            continue;
        }
        P bl=split(root,k);
        int le=bl.fi,ri=bl.se;
        mo[ri]-=gift[i].c;
        va[ri]+=1;
        down[ri]+=gift[i].c;
        h[ri]+=1;
        if(k!=1){
            P rr=split(le,k-1);
            zd=mo[rr.se];
            le=merge(rr.fi,rr.se);
        }else zd=mo[le];
        while(s[ri].size>0){
            P oo=split(ri,1);
            int zb=oo.fi,yb=oo.se;
            if(mo[zb]>=zd){
                ri=merge(zb,yb);
                break;
            }
            int y=search(le,mo[zb]);
            P kk=split(le,y);
            if(y!=0)zb=merge(kk.fi,zb);
            if(kk.se!=0)zb=merge(zb,kk.se);
            le=zb; s[0].size=0; ri=oo.se;
        }
        root=merge(le,ri);
    }
    int y;P kk;
    fo(i,1,m){
        if(i!=m)kk=split(root,1),y=kk.fi;
        else y=root;
        ans[pe[y].c]=va[y];
        root=kk.se;
    }
    fo(i,1,m)write(ans[i]),putchar(' ');
}