【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
2 5
3 4
6 3
2 7
2
3 4
1 3
Sample Output
NIE
TAK
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|1
using 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;
}