蠢了……

我们用线段树，记$w0$为该区间最左端取小值时，最右端最小能取大还是小还是无解，$w1$表示最左端取大值时，最右端最小能取大还是小还是无解

然后只要把交换看做修改就好了

这么说可能很难懂，看看代码应该就明白了

1 //minamoto 2 #include
     
       3 #include
      
        4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 int read(){ 8     #define num ch-'0' 9     char ch;bool flag=0;int res;10     while(!isdigit(ch=getc()))11     (ch=='-')&&(flag=true);12     for(res=num;isdigit(ch=getc());res=res*10+num);13     (flag)&&(res=-res);14     #undef num15     return res;16 }17 const int N=3e5+5;18 int a[N][2],w0[N<<2],w1[N<<1];19 #define ls (p<<1)20 #define rs (p<<1|1)21 void upd(int p,int l,int r){22     int mid=(l+r)>>1,t;23     if((t=w0[ls])==-1) w0[p]=-1;24     else{25         t=a[mid][t];26         if(t<=a[mid+1][0]) w0[p]=w0[rs];27         else if(t<=a[mid+1][1]) w0[p]=w1[rs];28         else w0[p]=-1;29     }30     if((t=w1[ls])==-1) w1[p]=-1;31     else{32         t=a[mid][t];33         if(t<=a[mid+1][0]) w1[p]=w0[rs];34         else if(t<=a[mid+1][1]) w1[p]=w1[rs];35         else w1[p]=-1;36     }37 }38 void build(int p,int l,int r){39     if(l==r) return (void)(w0[p]=0,w1[p]=1);40     int mid=(l+r)>>1;41     build(ls,l,mid),build(rs,mid+1,r);42     upd(p,l,r);43 }44 void update(int p,int l,int r,int x){45     if(l==r) return;46     int mid=(l+r)>>1;47     x<=mid?update(ls,l,mid,x):update(rs,mid+1,r,x);48     upd(p,l,r);49 }50 int main(){51 //    freopen("testdata.in","r",stdin);52     int n=read();53     for(int i=1;i<=n;++i){54         a[i][0]=read(),a[i][1]=read();55         if(a[i][0]>a[i][1]) swap(a[i][0],a[i][1]);56     }57     build(1,1,n);58     int m=read();59     while(m--){60         int x=read(),y=read();swap(a[x][0],a[y][0]),swap(a[x][1],a[y][1]);61         update(1,1,n,x),update(1,1,n,y);62         puts(w0[1]==-1?"NIE":"TAK");63     }64     return 0;65 }