题目描述

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.

题目分析

线段树 表示左端点正面/反面 右端点正面/反面时是否能够单调不降

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct your
{
    int x,y,f[2][2];
}a[200010*4];
int da[200010],db[200010];
void pushup(int x)
{
    int mid=(a[x].x+a[x].y)>>1;
    a[x].f[0][0]=a[x].f[0][1]=a[x].f[1][0]=a[x].f[1][1]=0;
    if(da[mid]<=da[mid+1]) a[x].f[0][0] |= a[x<<1].f[0][0]&a[x<<1|1].f[0][0] , a[x].f[0][1] |= a[x<<1].f[0][0]&a[x<<1|1].f[0][1] , a[x].f[1][0] |=  a[x<<1].f[1][0]&a[x<<1|1].f[0][0] , a[x].f[1][1] |= a[x<<1].f[1][0]&a[x<<1|1].f[0][1]; 
    if(da[mid]<=db[mid+1]) a[x].f[0][0] |= a[x<<1].f[0][0]&a[x<<1|1].f[1][0] , a[x].f[0][1] |= a[x<<1].f[0][0]&a[x<<1|1].f[1][1] , a[x].f[1][0] |=  a[x<<1].f[1][0]&a[x<<1|1].f[1][0] , a[x].f[1][1] |= a[x<<1].f[1][0]&a[x<<1|1].f[1][1];
    if(db[mid]<=da[mid+1]) a[x].f[0][0] |= a[x<<1].f[0][1]&a[x<<1|1].f[0][0] , a[x].f[0][1] |= a[x<<1].f[0][1]&a[x<<1|1].f[0][1] , a[x].f[1][0] |=  a[x<<1].f[1][1]&a[x<<1|1].f[0][0] , a[x].f[1][1] |= a[x<<1].f[1][1]&a[x<<1|1].f[0][1];
    if(db[mid]<=db[mid+1]) a[x].f[0][0] |= a[x<<1].f[0][1]&a[x<<1|1].f[1][0] , a[x].f[0][1] |= a[x<<1].f[0][1]&a[x<<1|1].f[1][1] , a[x].f[1][0] |=  a[x<<1].f[1][1]&a[x<<1|1].f[1][0] , a[x].f[1][1] |= a[x<<1].f[1][1]&a[x<<1|1].f[1][1];
}   
void build(int dx,int dy,int num)
{
    a[num].x=dx,a[num].y=dy;
    if(dx==dy)
    {
        a[num].f[1][1]=a[num].f[0][0]=1;
        return ;
    }
    int mid=(dx+dy)>>1;
    build(dx,mid,num<<1),build(mid+1,dy,num<<1|1);
    pushup(num);
}
void update(int dx,int tmp,int nmp,int num)
{
    if(a[num].x==dx&&a[num].y==dx)
    {
        da[dx]=tmp,db[dx]=nmp;
        return ;
    }
    int mid=(a[num].x+a[num].y)>>1;
    if(dx<=mid) update(dx,tmp,nmp,num<<1);
    else update(dx,tmp,nmp,num<<1|1);
    pushup(num);
}
int main()
{   
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&da[i],&db[i]);
    build(1,n,1);
    scanf("%d",&m);
    for(int x,y,i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int tmp=da[x],nmp=db[x];
        update(x,da[y],db[y],1),update(y,tmp,nmp,1);
        printf("%s\n", a[1].f[0][0] | a[1].f[0][1] | a[1].f[1][0] | a[1].f[1][1] ? "TAK":"NIE");
    }
    return 0;
}