BZOJ3526 - Click Here
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]。
n≤200000，m≤1000000，0≤a[i],b[i]≤10000000,1≤c[i],d[i]≤n.
Output
m行，每行对应一个答案。如果能成功，输出TAK，否则输出NIE。
Solution
对于一个区间$[L,R]$，如果$[L,mid]$能够升序排列，$[mid,R]$也能够升序排列，那么$[L,R]$能够升序排列。
因此，若没有交换操作，是能够利用分治思想判断能否升序排列的。
现在考虑交换卡牌$x$和卡牌$y$，此时包含$x$或包含$y$的区间内信息被更新了，其余区间则不受影响。换言之，需要使用某种数据结构，能够实现存储和更新，这个显然是线段树的作用。
具体做法就是对每个节点存储4个信息，分别表示左端点换与不换/右端点换与不换的信息，然后用线段树维护。
CODE
CODE - Click Here