题目

题目大意

平面上有一堆带权值的点。两种操作：交换两个点的权值，查找一个矩形的第\(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 <cstdio>

#include <cstring>

#include <algorithm>

#include <cassert>

#define N 60010

#define M 10010

#define MAX 1000000000

#define K 250

#define N_K 250

inline int input(){

	char ch=getchar();

	while (ch<'0' || '9'<ch)

		ch=getchar();

	int x=0;

	do{

		x=x*10+ch-'0';

		ch=getchar();

	}

	while ('0'<=ch && ch<='9');

	return x;

}

int n,m;

struct DOT{

	int x,y,z;

} d[N];

int p[N],rev[N];

inline bool cmp1(int a,int b){return d[a].x<d[b].x;}

inline bool cmp2(int a,int b){return d[a].y<d[b].y;}

int nb,bel[N],end[N_K],mxx[N_K];

int lis[31][N],num[31][N];

int nq,q[N];

int nt;

struct Range{

	int l,r,st,en;

} t[N_K];

void build(int fl,int l,int r,int st,int en){

	if (l==r || st>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'<op)

			op=getchar();

		if (op=='S'){

			int a=input()+1,b=input()+1,tmp=d[a].z;

			d[a].z=d[b].z;

			build(0,0,MAX,end[bel[rev[a]]-1]+1,end[bel[rev[a]]]);

			d[b].z=tmp;

			build(0,0,MAX,end[bel[rev[b]]-1]+1,end[bel[rev[b]]]);

		}

		else{

			int x0=input(),y0=input(),x1=input(),y1=input(),k=input();

			if (x0>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;

}

总结

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

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

巴特西

[JZOJ2865]【集训队互测 2012】Attack

题目

题目大意

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

正解

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

总结

最新文章

热门文章