BZOJ 3110 k大数查询 (树套树)

题意

5e4个可重集合，初试全空，5e4个操作：
1.在第[l,r]集合里加入一个数c
2.问[l,r]所有集合的并的第k大数

思路

发现很多题解都写得权值线段树套区间线段树啊，我觉得这题反过来套比较直白吧。。
不过写了一半陷入了奇怪的思维漩涡里。。
就跟着题解写了个权值套区间线段树，在luogu上开了o2，加了读入挂，还用了标记永久化才勉强过
明天再试试原来的写法

代码

这题实在是因为调了很多天，才发博客的

inline ll R(){
    ll x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0'; 
        c=getchar();
    }
    return x*f;
}
struct qst{
    ll l,r;
    ll id;
    ll x;
}Q[maxn];
vector<ll>v;
int ok;
int gt(ll x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
ll a[maxn],add[maxn];
int ls[maxn],rs[maxn];
int tot,ntot;
int n,m;
void build(int l, int r, int root){
    int mid=l+r>>1;
    tot=max(tot,root);
    if(l==r)return;
    build(lson);build(rson);return;
}
void up(int x, int y, int l, int r, int root){
    int mid = l+r>>1;
    a[root]+=max(0,(min(r,y)-max(x,l)+1));
    if(x<=l&&r<=y){
        add[root]++;
        return;
    }
    if(x<=mid){
        if(ls[root]==0)ls[root]=++tot;
        up(x,y,l,mid,ls[root]);
    }
    if(y>mid){
        if(rs[root]==0)rs[root]=++tot;
        up(x,y,mid+1,r,rs[root]);
    }
}
void update(int v, int x, int y, int l, int r, int root){
    int mid = l+r>>1;
    up(x,y,1,n,root);
    if(l==r)return;
    if(v<=mid)update(v,x,y,lson);
    else update(v,x,y,rson);
}
ll qy(int x, int y, int l, int r, int root, ll A){
    int mid = l+r>>1;
    if(x<=l&&r<=y)return A*(r-l+1)+a[root];
    ll ans = 0;
    if(x<=mid)ans+=qy(x,y,l,mid,ls[root],A+add[root]);
    if(y>mid)ans+=qy(x,y,mid+1,r,rs[root],A+add[root]);
    return ans;
}
int ask(int x, int y, int l, int r, int root, ll k){
    int mid = l+r>>1;
    if(l==r)return l;
    ll sum = qy(x,y,1,n,rc,0);
    if(sum>=k)return ask(x,y,rson,k);
    else return ask(x,y,lson,k-sum);
}
int main(){
    n=R();m=R();
    for(int i = 1; i <= m; i++){
        Q[i].id=R();Q[i].l=R();Q[i].r=R();Q[i].x=R();
        if(Q[i].id==1)v.pb(Q[i].x);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    ntot=v.size();
    build(1,ntot,1);
    ok =0 ;
    for(int i = 1; i <= m; i++){
        if(Q[i].id==1){
            update(gt(Q[i].x),Q[i].l,Q[i].r,1,ntot,1);
        }
        else{
            ll tmp=v[ask(Q[i].l,Q[i].r,1,ntot,1,Q[i].x)-1];
            printf("%lld
",tmp);
        }
    }
    return 0;
}