不妨假设ai<bi（不满足交换），线段树维护区间左端点取ai/bi，右端点最小是多少，修改时相当于两次单点修改（注意修改是永久的）
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define oo 0x3f3f3f3f 5 #define L (k<<1) 6 #define R (L+1) 7 #define mid (l+r>>1) 8 int n,m,x,y,a[N][2],f[N<<2][2]; 9 void update(int k,int l,int r,int x){ 10 if (l==r){ 11 f[k][0]=a[l][0]; 12 f[k][1]=a[r][1]; 13 return; 14 } 15 if (x<=mid)update(L,l,mid,x); 16 else update(R,mid+1,r,x); 17 f[k][0]=f[k][1]=oo; 18 for(int i=0;i<2;i++) 19 for(int j=1;j>=0;j--) 20 if (f[L][i]<=a[mid+1][j])f[k][i]=f[R][j]; 21 } 22 int main(){ 23 scanf("%d",&n); 24 memset(f,oo,sizeof(f)); 25 a[n+1][0]=a[n+1][1]=oo-1; 26 for(int i=1;i<=n;i++){ 27 scanf("%d%d",&a[i][0],&a[i][1]); 28 if (a[i][0]>a[i][1])swap(a[i][0],a[i][1]); 29 update(1,1,n,i); 30 } 31 scanf("%d",&m); 32 for(int i=1;i<=m;i++){ 33 scanf("%d%d",&x,&y); 34 swap(a[x][0],a[y][0]); 35 swap(a[x][1],a[y][1]); 36 update(1,1,n,x); 37 update(1,1,n,y); 38 if (f[1][0]==oo)printf("NIE "); 39 else printf("TAK "); 40 } 41 }