虽然分块过n2e5 m1e6不太可能，但是蒟蒻跑得次慢的点只有700ms，看其他人的AC记录他们次慢的点都和我差不多啊QAQ，所以蒟蒻觉得还是有希望的（?）

#include<bits/stdc++.h>
using namespace std;
#define _ 0
#define timeused() (double)clock()/CLOCKS_PER_SEC
#define Set(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define repp(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define debug() assert(0)
typedef int ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x){
   T f=1;x=0;char c=getchar();
   for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
   for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
   x*=f;
   return x;
}
ll n,m,a[500005],a2[500005],bel[500005],siz,L[1005],R[1005],dp[1005][2],l,r;
inline void cg(ll be){
   if(R[be]>n) return;
   ll lst1=a[L[be]],lst2=a2[L[be]];
   rep(i,L[be]+1,R[be]){
      if(lst1!=-1){
         if(a2[i]<lst1) lst1=-1;
         else a[i]>=lst1?lst1=a[i]:lst1=a2[i];
      }
      if(lst2!=-1){
         if(a2[i]<lst2) lst2=-1;
         else a[i]>=lst2?lst2=a[i]:lst2=a2[i];
      }
   }
   dp[be][0]=lst1;
   dp[be][1]=lst2;
   return;
}
inline bool query(){
   ll x=1,y=n,tmp=n,now=-1;
   for(;tmp!=R[bel[tmp]];--tmp);
   rep(i,1,bel[tmp]){
      if(dp[i][0]==-1&&dp[i][1]==-1) return 0;
      if(a2[L[i]]<now) return 0;
      if(a[L[i]]>=now){
         if(dp[i][0]==-1) return 0;
         now=dp[i][0];
      }
      else{
         if(dp[i][1]==-1) return 0;
         now=dp[i][1];
      }
   } 
   rep(i,tmp+1,y){
      if(a2[i]<now) return 0;
      a[i]>=now?now=a[i]:now=a2[i];
   }
   return 1;
}
int main(){
   rd(n);
   rep(i,1,n){
      rd(a[i]);
      rd(a2[i]);
      if(a[i]>a2[i]) swap(a[i],a2[i]);
   }
   siz=ceil(sqrt(n));
   rep(i,1,n) bel[i]=(i-1)/siz+1;
   rep(i,1,siz){ 
      L[i]=(i-1)*siz+1;
      R[i]=i*siz;
      cg(i);
   }
   rd(m);
   while(m--){ 
      rd(l);
      rd(r);
      swap(a[l],a[r]);
      swap(a2[l],a2[r]);
      cg(bel[l]);
      if(bel[l]!=bel[r]) cg(bel[r]);
      query()?puts("TAK"):puts("NIE");
   }
}

谢谢大家awa