BZOJ 3110 [Zjoi2013]K大数查询 ——树套树

【题目分析】

外层区间线段树，内层是动态开点的权值线段树。

SY神犇说树套树注重的是内外层的数据结构的选择问题，果然很重要啊。

动态开点的实现方法很好。

【代码】

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <set>

#include <map>

#include <string>

#include <algorithm>

#include <vector>

#include <iostream>

#include <queue>

using namespace std;

#define mlog 16

#define inf (0x3f3f3f3f)

unsigned Getunsigned()

{

    unsigned x=0,f=1; char ch=getchar();

    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}

    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}

    return x*f;

}

#define maxn 50005

#define F(i,j,k) for (unsigned i=j;i<=k;++i)

#define maxm maxn<<8

unsigned rt[maxn<<2],n,m,sum[maxm],le[maxm],ri[maxm],lazy[maxm];

unsigned c,L,R,cnt,opt;

void push(unsigned &o,unsigned l,unsigned r)

{

    if (!o) o=++cnt;

    if (L<=l&&r<=R)

    {

        lazy[o]++;

        sum[o]+=(r-l+1);

        return;

    }

    unsigned mid=l+r>>1;

    if (L<=mid) push(le[o],l,mid);

    if (R>mid) push(ri[o],mid+1,r);

    sum[o]=sum[le[o]]+sum[ri[o]]+lazy[o]*(r-l+1);

}

void modi(unsigned o,unsigned l,unsigned r)

{

    push(rt[o],1,n); if (l==r) return ;

    unsigned mid=l+r>>1;

    if (c<=mid) modi(o<<1,l,mid);

    else modi(o<<1|1,mid+1,r);

}

unsigned calc(unsigned o,unsigned l,unsigned r)

{

    if (!o) return 0;

    if (L<=l&&r<=R) return sum[o];

    unsigned mid=l+r>>1,tmp=0;

    if (L<=mid) tmp+=calc(le[o],l,mid);

    if (R>mid) tmp+=calc(ri[o],mid+1,r);

    return tmp+lazy[o]*(min(R,r)-max(L,l)+1);

}

unsigned ask(unsigned o,unsigned l,unsigned r)

{

    if (l==r) return l;

    unsigned mid=l+r>>1,tmp=calc(rt[o<<1],1,n);

    if (c<=tmp) return ask(o<<1,l,mid);

    c-=tmp; return ask(o<<1|1,mid+1,r);

}

int main()

{

    n=Getunsigned();

    m=Getunsigned();

    F(i,1,m)

    {

        opt=Getunsigned(); L=Getunsigned();

        R=Getunsigned(); c=Getunsigned();

        if (opt==1) c=n-c+1,modi(1,1,n);

        else printf("%u\n",n-ask(1,1,n)+1);

    }

    return 0;

}