[文章目录]
Description
有n张卡片在桌上一字排开，每张卡片上有两个数，第i张卡片上，正面的数为a[i]，反面的数为b[i]。现在，有m个熊孩子来破坏你的卡片了！第i个熊孩子会交换c[i]和d[i]两个位置上的卡片。每个熊孩子捣乱后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面变成正面，但不能改变卡片的位置），能否让卡片正面上的数从左到右单调不降。n<=2*10^5 m<=10^6
对于每段区间，影响其他区间的只有首尾两个元素。记录四种情况是否可行，线段树进行区间合并。时间复杂度O(mlogn+n)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 201000
int w[N][2];
bool v[N<<2][2][2];
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
inline void ud(int pos,int x,int y)
{
v[pos][0][0]|=v[pos<<1][0][x]&v[pos<<1|1][y][0];
v[pos][0][1]|=v[pos<<1][0][x]&v[pos<<1|1][y][1];
v[pos][1][0]|=v[pos<<1][1][x]&v[pos<<1|1][y][0];
v[pos][1][1]|=v[pos<<1][1][x]&v[pos<<1|1][y][1];
}
inline void pushup(int pos,int mid)
{
memset(v[pos],0,sizeof v[pos]);
if(w[mid][0]<=w[mid+1][0]) ud(pos,0,0);
if(w[mid][0]<=w[mid+1][1]) ud(pos,0,1);
if(w[mid][1]<=w[mid+1][0]) ud(pos,1,0);
if(w[mid][1]<=w[mid+1][1]) ud(pos,1,1);
}
void build(int pos,int l,int r)
{
if(l==r)
{
v[pos][1][1]=v[pos][0][0]=1;
return ;
}
int mid=(l+r)>>1;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
pushup(pos,mid);
}
void fix(int pos,int l,int r,int x)
{
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) fix(pos<<1,l,mid,x);
else fix(pos<<1|1,mid+1,r,x);
pushup(pos,mid);
}
int main()
{
int n,m; read(n);
for(int i=1;i<=n;++i) read(w[i][0]),read(w[i][1]);
build(1,1,n); read(m); int x,y;
while(m--)
{
read(x); read(y);
swap(w[x][0],w[y][0]); swap(w[x][1],w[y][1]);
fix(1,1,n,x); fix(1,1,n,y);
if(v[1][0][0]|v[1][0][1]|v[1][1][0]|v[1][1][1]) puts("TAK");
else puts("NIE");
}
return 0;
}