首页 > 代码库 > bzoj2674 Attack

bzoj2674 Attack

2024-08-26 00:26:14   220人阅读

Description

　　chnlich非常喜欢玩三国志这款游戏，并喜欢用一些策略出奇制胜。现在，他要开始征服世界的旅途了。
　　他的敌人有N座城市和N个太守，N个城市可以看作在二维平面上的N个点。
　　N座城市的标号为0,1,2,……,N-1。
　　第i座城市的坐标为(Xi,Yi)，镇守这座城市的太守的能力值为Zi。
　　chnlich每次会选择一个边平行于坐标轴的矩形区域，并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。
　　不过，他的敌人经常会偷偷交换两座城市的太守，防止弱点被chnlich发现。
　　现在，chnlich想要知道，每次奇袭时他的敌人的能力值。

Input

　　输入的第一行包含两个整数N,M，N表示城市与太守的个数，M表示接下来发生了M个事件。
　　输入的第二行到第N+1行，每行包含三个整数，第i+2行的三个整数依次表示编号为i的城市的Xi,Yi,Zi，含义如题所述。
　　输入的第N+2行到第N+M+1行，每行有两种可能形式：
　　第一种
　　QUERY x0 y0 x1 y1 k
　　表示chnlich询问一个相对顶点为(x0,y0),(x1,y1)的矩形中，第k小能力值太守的能力值。
　　第二种
　　SWAP x y
　　表示chnlich的敌人交换了编号为x和y两座城市的太守。

Output

　　对于每一个QUERY，输出一行。
　　若不存在第k小能力值的太守，输出"It doesn‘t exist."(不包含引号)。
　　否则输出一个整数，表示矩形内能力值第k小太守的能力值。
kd树维护平面上的点，trie维护kd树每颗子树中的所有权值，自底向上修改，查询时把对应的trie的根和零散的点取出并一起二分查询
#include<cstdio>#include<algorithm>int n,m,X0,Y0,X1,Y1,rs[60007],rp,xs[60007],xp;char op[15];void mins(int&a,int b){if(a>b)a=b;}void maxs(int&a,int b){if(a<b)a=b;}int vs[60007],ch[80007*401][2],sz[80007*401],p=0;struct node{    int x[2],mn[2],mx[2],v,rt,id;    node*c[2],*f;    void init(int ID){        scanf("%d%d%d",x,x+1,&v);        mn[0]=mx[0]=x[0];        mn[1]=mx[1]=x[1];        id=ID;        vs[id]=v;        rt=++p;    }    void up(){        for(int i=0;i<2;++i)if(c[i]){            c[i]->f=this;            for(int j=0;j<2;++j){                mins(mn[j],c[i]->mn[j]);                maxs(mx[j],c[i]->mx[j]);            }        }    }    void ins(int x){        int w=rt;        ++sz[w];        for(int i=15;~i;--i){            int d=x>>i&1;            if(!ch[w][d])ch[w][d]=++p;            ++sz[w=ch[w][d]];        }        if(f)f->ins(x);    }    void del(int x){        int w=rt;        --sz[w];        for(int i=15;~i;--i)--sz[w=ch[w][x>>i&1]];        if(f)f->del(x);    }    void get(){        if(mx[0]<X0||mn[0]>X1||mx[1]<Y0||mn[1]>Y1)return;        if(X0<=mn[0]&&mx[0]<=X1&&Y0<=mn[1]&&mx[1]<=Y1){            rs[rp++]=rt;            return;        }        if(X0<=x[0]&&x[0]<=X1&&Y0<=x[1]&&x[1]<=Y1)xs[xp++]=v;        for(int i=0;i<2;++i)if(c[i])c[i]->get();    }}ns[60007],*rt,*nr[60007];int dx=0;bool operator<(const node&a,const node&b){    return a.x[dx]!=b.x[dx]?a.x[dx]<b.x[dx]:a.x[dx^1]<b.x[dx^1];}node*build(node*l,node*r){    if(l==r)return 0;    node*m=l+(r-l>>1);    std::nth_element(l,m,r);    dx^=1;    m->c[0]=build(l,m);    m->c[1]=build(m+1,r);    dx^=1;    m->up();    return m;}void query(int k){    int L=0,R=65535,M,s=xp;    for(int i=0;i<rp;++i)s+=sz[rs[i]];    if(s<k||!k){        puts("It doesn‘t exist.");        return;    }    while(L<R){        M=L+R>>1;        s=0;        for(int i=0;i<rp;++i)s+=sz[ch[rs[i]][0]];        for(int i=0;i<xp;++i)if(L<=xs[i]&&xs[i]<=M)++s;        if(s<k){            k-=s;            for(int i=0;i<rp;++i)rs[i]=ch[rs[i]][1];            L=M+1;        }else{            for(int i=0;i<rp;++i)rs[i]=ch[rs[i]][0];            R=M;        }    }    printf("%d\n",vs[L]);}int main(){    scanf("%d%d",&n,&m);    for(int i=0;i<n;++i)ns[i].init(i);    std::sort(vs,vs+n);    rt=build(ns,ns+n);    for(int i=0;i<n;++i)nr[ns[i].id]=ns+i;    for(int i=0;i<n;++i)ns[i].ins(ns[i].v=std::lower_bound(vs,vs+n,ns[i].v)-vs);    for(int i=0;i<m;++i){        scanf("%s",op);        if(op[0]==‘Q‘){            int k;            scanf("%d%d%d%d%d",&X0,&Y0,&X1,&Y1,&k);            if(X0>X1)std::swap(X0,X1);            if(Y0>Y1)std::swap(Y0,Y1);            rp=xp=0;            rt->get();            query(k);        }else{            int a,b,av,bv;            scanf("%d%d",&a,&b);            av=nr[a]->v;            bv=nr[b]->v;            nr[a]->v=bv;            nr[b]->v=av;            nr[a]->del(av);            nr[a]->ins(bv);            nr[b]->del(bv);            nr[b]->ins(av);        }    }    return 0;}

 

bzoj2674 Attack


联系
我们