【BZOJ3110】【ZJOI2013】k大数查询

题意简析

给定一个区间，可以在这个区间上每个整数点插入若干个数(这些数数值可以重复)你需要支持2种操作：

1)在[a,b]间所有整数点插入c

2)查询[a,b]内第c大的数

解题思路

树套树裸题，外层是权值线段树，内层是普通线段树，通过将操作1的c离散后维护即可。

总复杂度均为\(O(n\log_{2}^{2}n)\).

#include <stdio.h>

#include <algorithm>

#define Uint unsigned int

#define MN 50005

#define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),TT==S)?EOF:*S++)

char BB[1<<15],*S=BB,*TT=BB;

inline int in(){

    int x=0; bool f=0; char c;

    for (;(c=getchar())<'0'||c>'9';f=c=='-');

    for (x=c-'0';(c=getchar())>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0');

    return f?-x:x;

}int n,q,op[MN],a[MN],b[MN],c[MN],v[MN],rk[MN],cnt,A,B,V;

#define mid (l+r>>1)

struct node{

    node *ls,*rs;Uint sum,mark;

    node(){ls=rs=NULL;sum=mark=0;}

    inline void ad(Uint l,Uint x){sum+=x*l;mark+=x;}

    inline void pushdown(int l,int r){

        if (!mark||l==r) return;

        if (!ls) ls=new node();if (!rs) rs=new node();

        ls->ad(mid-l+1,mark);rs->ad(r-mid,mark);mark=0;

    }

    inline void pushup(){sum=(ls?ls->sum:0)+(rs?rs->sum:0);}

};

void update(int l,int r,int ad,node *&x){

    if (l>B||r<A) return;if (x==NULL) x=new node();

    if (A<=l&&r<=B){x->ad(r-l+1,ad);return;}

    x->pushdown(l,r);update(l,mid,ad,x->ls);

    update(mid+1,r,ad,x->rs);x->pushup();

}

Uint query(int l,int r,node *&x){

    if (x==NULL||l>B||r<A) return 0;

    if (l>=A&&r<=B) return x->sum;x->pushdown(l,r);

    return query(l,mid,x->ls)+query(mid+1,r,x->rs);

}

struct node2D{

    node2D *ls,*rs;node *val;

    node2D(){ls=rs=NULL;val=NULL;}

}*root;

#define midd (L+R>>1)

void U(int L,int R,node2D *&x){

    if (x==NULL) x=new node2D();

    if (L!=R){

        if (V<=midd) U(L,midd,x->ls);

        else U(midd+1,R,x->rs);

    }update(1,n,1,x->val);

}

Uint Q(int L,int R,node2D *x){

    if (x==NULL) return 0;if (L==R)return L;

    register Uint tmp=x->rs?query(1,n,x->rs->val):0;

    if (tmp>=V) return Q(midd+1,R,x->rs);

    else return V-=tmp,Q(L,midd,x->ls);

}

inline bool cmp(int a,int b){return c[a]<c[b];}

void init(){

    n=in(),q=in();for (int i=1; i<=q; ++i)

        op[i]=in(),a[i]=in(),b[i]=in(),c[i]=in(),(op[i]==1)?v[++cnt]=i:0;

    std::sort(v+1,v+cnt+1,cmp);for (register int i=1; i<=cnt; ++i) rk[v[i]]=i;

}

void solve(){

    for (register int i=1; i<=q; ++i){

        if (op[i]==1) A=a[i],B=b[i],V=rk[i],U(1,cnt,root);

        else A=a[i],B=b[i],V=c[i],printf("%d\n",c[v[Q(1,cnt,root)]]);

    }

}int main(){init();solve();}

巴特西

【BZOJ3110】【ZJOI2013】k大数查询

题意简析

解题思路

最新文章

热门文章