自动搬运

查看原文

来自洛谷，原作者为

	Energy_Making 即将AFO

搬运于2025-08-24 21:50:16，当前版本为作者最后更新于2021-03-01 22:39:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1.前置知识

线段树

2.解法

这道题是一道线段树的连通性问题。而我们要维护的信息则也跟连通性有关——$l$ 分别取正背面，$r$ 能取到正面还是背面。

具体而言，我们把数字较小的一面记为 $a$，较大的一面记为 $b$。线段树中维护的信息即为 $va$：$l$ 取 $a$ 出发时 $r$ 的最小值（显而易见的贪心思想）与 $vb$：$l$ 取 $b$ 出发时 $r$ 的最小值。那么难点就在于维护 $va$ 与 $vb$。这里放出 $va$ 作为参考。

int mid=(l+r)>>1;
if(a[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].va;
else if(b[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].vb;
else node[p].va=inf;

首先我们都讨论了node[p<<1].va是因为 $p$ 与 $p$ 的左儿子起点 $a$ 相同。

然后我们讨论a[mid+1]与b[mid+1]是因为要满足不下降的条件，注意先讨论较小的一项是因为要满足贪心原则（一个位置上的数合法时越小越有可能成功），如果两个都不行则用极大值标记为此路不通。

最后的 change 操作就将有改变的地方交换重新建树即可。

3.代码

#include<stdio.h>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int a[200005],b[200005];
struct seg
{
	int l,r,va,vb;
	seg()
	{
		va=vb=inf;
	}
};
seg node[1000005];
void merge(int p,int l,int r)//精华所在
{
	int mid=(l+r)>>1;
	if(a[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].va;
	else if(b[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].vb;
	else node[p].va=inf;
	if(a[mid+1]>=node[p<<1].vb)node[p].vb=node[p<<1|1].va;
	else if(b[mid+1]>=node[p<<1].vb)node[p].vb=node[p<<1|1].vb;
	else node[p].vb=inf;
   	//vb操作与va同理。
}
void build(int p,int l,int r)//常规操作
{
	node[p].l=l;
	node[p].r=r;
	if(l==r)
	{
		node[p].va=a[l];
		node[p].vb=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	merge(p,l,r);
}
void change(int p,int l,int r,int x)//相比于build，只是没有赋l与r的值，再加了个范围判断。
{
	if(l==r)
	{
		node[p].va=a[l];
		node[p].vb=b[l];
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)change(p<<1,l,mid,x);
	else change(p<<1|1,mid+1,r,x);
	merge(p,l,r);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		a[i]=min(x,y);
		b[i]=max(x,y);
	}
	build(1,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		swap(a[x],a[y]);
		swap(b[x],b[y]);
		change(1,1,n,x);
		change(1,1,n,y);
		if(node[1].va==inf&&node[1].vb==inf)printf("NIE\n");
		else printf("TAK\n");
	}
	return 0;
}