首页 > 代码库 > 【BZOJ3526】[Poi2014]Card 线段树

【BZOJ3526】[Poi2014]Card 线段树

2024-10-08 02:33:39   211人阅读

【BZOJ3526】[Poi2014]Card

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

NIE
TAK

HINT

【样例解释】
交换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.

题解：线段树的区间合并好题~

对于区间x，我们令s[x][0/1][0/1]表示i的左端点选择（a/b），右端点选择（a/b）能否单调不降，然后pushup一下就行了

 

#include <cstdio>#include <cstring>#include <iostream>#define lson x<<1#define rson x<<1|1using namespace std;const int maxn=200010;int n,m;int s[maxn<<2][2][2],v[maxn][2];void pushup(int l,int r,int x){	int mid=l+r>>1,i,j,k;	for(i=0;i<=1;i++)	for(j=0;j<=1;j++)	for(s[x][i][j]=0,k=0;k<=1;k++)	for(l=0;l<=1;l++)		s[x][i][j]|=s[lson][i][k]&s[rson][l][j]&(v[mid][k]<=v[mid+1][l]);}void build(int l,int r,int x){	if(l==r)	{		s[x][1][1]=s[x][0][0]=1;		return ;	}	int mid=l+r>>1;	build(l,mid,lson),build(mid+1,r,rson);	pushup(l,r,x);}void updata(int l,int r,int x,int a){	if(l==r)	{		s[x][1][1]=s[x][0][0]=1;		return ;	}	int mid=l+r>>1;	if(a<=mid)	updata(l,mid,lson,a);	else	updata(mid+1,r,rson,a);	pushup(l,r,x);}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int main(){	n=rd();	int i,a,b;	for(i=1;i<=n;i++)	v[i][0]=rd(),v[i][1]=rd();	build(1,n,1),m=rd();	for(i=1;i<=m;i++)	{		a=rd(),b=rd();		swap(v[a][0],v[b][0]),swap(v[a][1],v[b][1]);		updata(1,n,1,a),updata(1,n,1,b);		if(s[1][0][0]|s[1][0][1]|s[1][1][0]|s[1][1][1])	printf("TAK\n");		else	printf("NIE\n");	}	return 0;}

 

【BZOJ3526】[Poi2014]Card 线段树


联系
我们