题目大意

平面上有一堆带权值的点。两种操作：交换两个点的权值，查找一个矩形的第\(k\)小

\(N<=60000\)

\(M<=10000\)

\(10000ms\)

---

思考历程&各种可能过的方法

先是想了一会儿，然后突然发现一个惊天大秘密：\(10000ms\)！

然后就想出个\(O(NM)\)的做法……

将矩形内的所有点找出来，然后\(O(N)\)求第\(k\)大……

于是爆\(0\)了。后来才发现是输出的时候漏了句号，而且给出的矩形有\(x0>x1\)或\(y0>y1\)的情况……

改过来，\(50+\)

其实\(O(N)\)求第\(k\)大带巨大常数，不如优化：

首先将所有的点按照权值从小到大排序，然后扫过去就可以了。遇见第\(k\)个在矩形内的，直接退出。

然后就有了\(100\)分的好成绩。

当然，这是水法……

考虑一些看着像正解的东西。

首先想到的是树套树套树，显然不现实。

然后就想\(kd-tree\)。二分答案，如果把权值看成一个维，就相当于在一个三维空间中找一个长方体内点的个数。

修改的时候并不需要打个动态的\(kd-tree\)（不然常数大得要死）。我们先将所有修改后形成的新点加进来。每个点上有个标记表示它是否存在。修改的时候修改标记，同时维护一下就可以了。

时间复杂度是\(O(m(n+m)^{\frac{2}{3}}\lg 10^9)\)（如果将权值离散化，\(\lg 10^9\)可以变成\(\lg n\)）

感觉上可能不过……

然后又有个方法：\(kd-tree\)套权值线段树！

这样有个好处就是不需要再外面二分答案。

询问的时候在\(kd-tree\)里找对应的节点。找出来的是一堆整块的子树和零散的点。

然后就可以一起二分（也就是每棵权值线段树上的指针一起移动），对于零散的点暴力判就可以了。

时间复杂度是\(O(m\sqrt n\lg 10^9)\)

实际上这也差不多是正解的时间复杂度……（或许可以过吧……）

---

正解

题解中用到一个叫划分树的东西，类似于整体二分的过程记录下来，这里就不在赘述了。

它有个经典的用处就是求区间第\(k\)小。

然而这个东西修改很不方便……如果单是修改是\(O(n)\)的（随便想一想就能知道），或者重构，是\(O(n\lg n)\)的。

为了减小代码复杂度，还是考虑重构吧……

考虑按照\(x\)坐标分块。每个块内以\(y\)排序。

每个整块建立一个划分树。

修改的时候直接暴力重构。

查询的时候就是一堆整块和一些散点。散点记录到一个数组里面。

在几个划分树上二分即可（散点也是暴力判断）。

时间复杂度是\(O((n+m)\sqrt n \lg 10^8)\)

如果不重构，加上修改操作，时间复杂度会优一点。

还有，实际上也不需要划分树这种东西，用主席树代替也可以（应该会简单很多）。

---

代码（未A，待以后填坑）

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 60010#define M 10010#define MAX 1000000000#define K 250#define N_K 250inline int input(){    char ch=getchar();    while (ch<'0' || '9'
        
         en)        return;    int mid=l+r>>1,k=st-1;    for (int i=st,j=0;i<=en;++i){        if (d[lis[fl][i]].z<=mid){            ++j;            lis[fl+1][++k]=lis[fl][i];        }        num[fl][i]=j;    }    for (int i=st;i<=en;++i)        if (d[lis[fl][i]].z>mid)            lis[fl+1][++k]=lis[fl][i];    build(fl+1,l,mid,st,st+num[fl][en]-1);    build(fl+1,mid+1,r,st+num[fl][en],en);}int kth(int fl,int l,int r,int k){    if (l==r){        int siz=0;        for (int i=1;i<=nt;++i)            siz+=t[i].r-t[i].l+1;        for (int i=1;i<=nq;++i)            if (q[i]==l)                siz++;        if (k<=siz)            return l;        return -1;    }    int mid=l+r>>1,lsiz=0;    for (int i=1;i<=nt;++i)        lsiz+=num[fl][t[i].r]-(t[i].l>t[i].st?num[fl][t[i].l-1]:0);    for (int i=1;i<=nq;++i)        if (q[i]<=mid)            lsiz++;    if (k<=lsiz){        for (int i=1;i<=nt;++i){            t[i].en=t[i].st+num[fl][t[i].en]-1;            t[i].l=t[i].st+(t[i].l>t[i].st?num[fl][t[i].l-1]:0);            t[i].r=t[i].st+num[fl][t[i].r]-1;        }        return kth(fl+1,l,mid,k);    }    for (int i=1;i<=nt;++i){        int rsiz=t[i].r-t[i].l+1-lsiz;        t[i].r=t[i].r+num[fl][t[i].en]-num[fl][t[i].r];        t[i].l=t[i].r-rsiz+1;        t[i].st=t[i].st+num[fl][t[i].en];    }    for (int i=1;i<=nq;++i)        if (q[i]<=mid)            q[i]=MAX+1;    return kth(fl+1,mid+1,r,k-lsiz);}int main(){    //freopen("in.txt","r",stdin);    n=input(),m=input();    for (int i=1;i<=n;++i)        d[i]={input(),input(),input()},p[i]=i;    sort(p+1,p+n+1,cmp1);    for (int i=1;i*K<=n;++i){        ++nb;        for (int j=(i-1)*K+1;j<=i*K;++j)            bel[j]=nb;        end[i]=i*K;    }    if (n%K){        ++nb;        for (int j=n/K*K+1;j<=n;++j)            bel[j]=nb;        end[nb]=n;    }    for (int i=1;i<=nb;++i){        mxx[i]=d[p[end[i]]].x;        sort(p+end[i-1]+1,p+end[i]+1,cmp2);        for (int j=end[i-1]+1;j<=end[i];++j)            lis[0][j]=p[j];        build(0,0,MAX,end[i-1]+1,end[i]);    }    for (int i=1;i<=n;++i)        rev[p[i]]=i;    while (m--){        char op=getchar();        while (op<'A' || 'Z'
         
          x1) swap(x0,x1); if (y0>y1) swap(y0,y1); int lb=nb+1,rb=0; for (int i=1;i<=nb;++i) if (mxx[i]>=x0){ lb=i; break; } for (int i=nb;i>=1;--i) if (mxx[i]<=x1){ rb=i; break; } if (lb>rb+1){ printf("It doesn't exist.\n"); break; } nq=0; if (lb==rb+1){ for (int i=end[lb-1]+1;i<=end[lb];++i) if (x0<=d[p[i]].x && d[p[i]].x<=x1 && y0<=d[p[i]].y && d[p[i]].y<=y1) q[++nq]=d[p[i]].z; } else{ for (int i=end[lb-1]+1;i<=end[lb];++i) if (x0<=d[p[i]].x && d[p[i]].x<=x1 && y0<=d[p[i]].y && d[p[i]].y<=y1) q[++nq]=d[p[i]].z; for (int i=end[rb]+1;i<=end[rb+1];++i) if (x0<=d[p[i]].x && d[p[i]].x<=x1 && y0<=d[p[i]].y && d[p[i]].y<=y1) q[++nq]=d[p[i]].z; } nt=0; for (int i=lb+1;i<=rb;++i){ int l=end[i-1]+1,r=end[i],st=end[i]+1,en; while (l<=r){ int mid=l+r>>1; if (d[p[mid]].y>=y0) r=(st=mid)-1; else l=mid+1; } if (st==end[i]+1) continue; l=st,r=end[i]; en=st-1; while (l<=r){ int mid=l+r>>1; if (d[p[mid]].y<=y1) l=(en=mid)+1; else r=mid-1; } if (st>en) continue;// assert(st>=0 && en>=0); t[++nt]={st,en,end[i-1]+1,end[i]}; } int ans=kth(0,0,MAX,k); if (ans==-1) printf("It doesn't exist.\n"); else printf("%d\n",ans); } } return 0;}
         
        
       
      
     
    

---

总结

像这种题，暴力是不好卡掉的……

所以要看准数据范围，加以优秀的卡常操作……