题目链接：GMOJ 2865

题目

题解

本题因为时间限制多开了十倍的原因，有多种解法。

解法A

思路

代码

#include<cstdio>
#include<algorithm>
using std::swap;
using std::sort;
using std::nth_element;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)
        ch=getchar();
    while('0'<=ch&&ch<='9')
        res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=60000+5;
const int MAXM=10000+5;
struct Node{
    int x,y,z,ID;
    void Read(int i){
        ID=i;
        x=read(),y=read(),z=read();
        return;
    }
    bool operator<(const Node &a)const{
        return z<a.z;
    }
};
int n,m;
int ID[MAXN];
Node C[MAXN];
inline void QUERY(int,int,int,int,int);
inline void SWAP(int,int);
int main(void){
    register int i;
    n=read(),m=read();
    for(i=1;i<=n;++i)
        C[i].Read(i);
    sort(C+1,C+n+1);
    for(i=1;i<=n;++i)
        ID[C[i].ID]=i;
    for(i=1;i<=m;++i){
        static char ch;
        do{
            ch=getchar();
        }while(ch!='Q'&&ch!='S');
        if(ch=='Q'){
            static int lx,ly,rx,ry,k;
            lx=read(),ly=read(),rx=read(),ry=read(),k=read();
            //scanf("%d%d%d%d%d",&lx,&ly,&rx,&ry,&k);
            QUERY(lx,ly,rx,ry,k);
        }
        if(ch=='S'){
            static int a,b;
            a=read(),b=read();
            //scanf("%d%d",&a,&b);
            SWAP(a+1,b+1);
        }
    }
    return 0;
}
inline void QUERY(int lx,int ly,int rx,int ry,int k){
    register bool flag=false;
    register int i,cnt=0;
    if(rx<lx)
        swap(lx,rx);
    if(ry<ly)
        swap(ly,ry);
    for(i=1;i<=n;++i)
        if(lx<=C[i].x&&C[i].x<=rx&&ly<=C[i].y&&C[i].y<=ry)
            if(++cnt==k){
                flag=true;
                printf("%d\n",C[i].z);
                break;
            }
    if(!flag)
        puts("It doesn't exist.");
    return;
}
inline void SWAP(int a,int b){
    swap(C[ID[a]].x,C[ID[b]].x),
    swap(C[ID[a]].y,C[ID[b]].y),
    swap(ID[a],ID[b]);
    return;
}