NKOJ 3777 卡牌操作（线段树）

发表于 |
字数统计: 1,012字 | 阅读时长 ≈ 5min

P3777卡牌操作

问题描述

有n张卡片在桌上一字排开，每张卡片上有两个数，第i张卡片上，正面的数为a[i]，反面的数为b[i]。现在，有m个熊孩子来破坏你的卡片了！
第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。
每个熊孩子捣乱后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面变成正面，但不能改变卡片的位置），能否让卡片正面上的数从左到右单调不降。

输入格式

第一行一个n。
接下来n行，每行两个数a[i],b[i]。
接下来一行一个m。
接下来m行，每行两个数c[i],d[i]。

输出格式

m行，每行对应一个答案。如果能成功，输出TAK，否则输出NIE。

样例输入

4
2 5
3 4
6 3
2 7
2
3 4
1 3

样例输出

NIE
TAK

提示

【样例解释】
交换3和4后，卡片序列为(2,5) (3,4) (2,7) (6,3)，不能成功。
交换1和3后，卡片序列为(2,7) (3,4) (2,5) (6,3)，翻转第3张卡片，卡片的正面为2,3,5,6，可以成功。

n≤200000，m≤1000000，0≤a[i],b[i]≤10000000,1≤c[i],d[i]≤n.

首先用图论的思想，将一个卡牌看成两个点$A_i$和$B_i$，不妨设$A_i<=B_i$，如果$A_i$的值小于$A_{i+1}$，那么就连一条从$A_i$指向$A_{i+1}$的边，同理处理所有点。
那么是否有解的问题就变成了问是否存在一条路径可以从1走到n。

然后用到线段树维护连通性。

我们讨论一个区间$[L,R]$，用Va表示从$A_L$出发能够到达$R$号点时最小的权值，Vb表示从$B_L$出发。
那么我们ls为区间的左儿子，rs为右儿子，那么我们需要考虑是否能通过左右儿子的值来算出$[L,R]$的值。令mid为$L+R>>1$。

首先我们考虑算出$Va_{[L,R]}$
那么如果$Va_{ls}<=A_{mid+1}$，那么意味着从mid点可以连到$A_{mid+1}$，所以$Va_{[L,R]}=Va_{rs}$。
否则讨论$Va_{ls}<=B_{mid+1}$，成立就意味着从mid点可以连到$B_{mid+1}$，所以$Va_{[L,R]}=Vb_{rs}$。
如果都不满足，那么mid不能连到mid+1，意味着不存在一条从$A_L$到$A_R$或$B_R$的路径，那么$Va_{[L,R]}=inf$。

$Vb_{[L，R]}$同理计算。
最后只需要看$Va_{[1,n]}$和$Vb_{[1,n]}$是否存在就行了。

关于修改显然就是单点修改了。具体可以参考代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 222222
#define M 2222222
using namespace std;
int n,A[N],B[N],m;
int ls[M],rs[M],va[M],vb[M],tot;
void UD(int p,int l,int r)
{
	int mid=(l+r>>1)+1;
	if(va[ls[p]]<=A[mid])va[p]=va[rs[p]];
	else if(va[ls[p]]<=B[mid])va[p]=vb[rs[p]];
	else va[p]=1e9;
	if(vb[ls[p]]<=A[mid])vb[p]=va[rs[p]];
	else if(vb[ls[p]]<=B[mid])vb[p]=vb[rs[p]];
	else vb[p]=1e9;
}
int BT(int x,int y)
{
	int p=++tot;
	if(x<y)
	{
		int mid=x+y>>1;
		ls[p]=BT(x,mid);
		rs[p]=BT(mid+1,y);
		UD(p,x,y);
	}
	else va[p]=A[x],vb[p]=B[x];
	return p;
}
void CHA(int p,int l,int r,int k)
{
	if(l==r){va[p]=A[l];vb[p]=B[l];return;}
	int mid=l+r>>1;
	if(k<=mid)CHA(ls[p],l,mid,k);
	else CHA(rs[p],mid+1,r,k);
	UD(p,l,r);
}
int main()
{
	int i,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&A[i],&B[i]);
		if(A[i]>B[i])swap(A[i],B[i]);
	}
	BT(1,n);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		swap(A[x],A[y]);
		swap(B[x],B[y]);
		CHA(1,1,n,x);
		CHA(1,1,n,y);
		if(va[1]!=1e9||vb[1]!=1e9)puts("TAK");
		else puts("NIE");
	}
}