[bzoj 3526--POI2014]Card

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

这道题很容易想到一个贪心策略，那就是当左端点确定时，最优的策略就是右端点越小越好。
那么写一个线段树，来维护区间的右端点是什么，每次x,y交换，只需在线段树上暴力修改，注意一下细节问题就可以了。

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<cstdlib>
    #define inf 10000001
    using namespace std;
    inline int read()
    {
        int x=0,f=1;char ch=getchar();
        while(ch<\'0\' || ch>\'9\'){if(ch==\'-\')f=-1;ch=getchar();}
        while(ch>=\'0\' && ch<=\'9\')x=x*10+ch-\'0\',ch=getchar();
        return x*f;
    }
    inline void write(int x)
    {
        if(x<0)putchar(\'-\'),x=-x;
        if(x>9)write(x/10);
        putchar(x%10+\'0\');
    }
    int a[200010][2];
    struct trnode
    {
        int l,r,lc,rc,d[2];
    }tr[400010];int trlen;
    inline void update(int now)
    {
        int lc=tr[now].lc,rc=tr[now].rc;
        for(int i=0;i<2;i++)
        {
            tr[now].d[i]=inf;
            if(tr[lc].d[i]==inf)continue;
            for(int j=0;j<2;j++)if(tr[lc].d[i]<=a[tr[rc].l][j])tr[now].d[i]=min(tr[now].d[i],tr[rc].d[j]);
        }
    }
    inline void bt(int l,int r)
    {
        trlen++;int now=trlen;
        tr[now].l=l;tr[now].r=r;
        if(l==r)tr[now].d[0]=a[l][0],tr[now].d[1]=a[r][1];
        else
        {
            int mid=(l+r)>>1;
            tr[now].lc=trlen+1;bt(l,mid);
            tr[now].rc=trlen+1;bt(mid+1,r);
            update(now);
        }
    }
    inline void change(int now,int k)
    {
        if(tr[now].l==tr[now].r){tr[now].d[0]=a[k][0],tr[now].d[1]=a[k][1];return ;}
        int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)>>1;
        if(k<=mid)change(lc,k);
        else change(rc,k);
        update(now);
    }
    int main()
    {
        //freopen(\"a.in\",\"r\",stdin);
        //freopen(\"a.out\",\"w\",stdout);
        int n=read();
        for(int i=1;i<=n;i++)a[i][0]=read(),a[i][1]=read();
        bt(1,n);
        int m=read();
        while(m--)
        {
            int x=read(),y=read();
            swap(a[x],a[y]);
            change(1,x),change(1,y);
            bool bk=false;
            for(int i=0;i<2;i++)if(tr[1].d[i]!=inf){bk=true;break;}
            if(bk==true)puts(\"TAK\");
            else puts(\"NIE\");
        }
        return 0;
    }