将每个位置拆成两个状态 \(0/1\),分别表示该牌选择正面/反面,如果 \(v_{i,a} \le v_{i + 1, b}\) 则在这两个状态间连边,
最终就是看两头是否存在一条通路。
可以用线段树来维护每段区间两头的四种情况是否可能连通即可。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 1e9 + 7;
typedef pair <int, int> P;
typedef long long LL;
int n, m, a[N][2];
bool c[N<<2][2][2], t[N<<2];
inline void chk_(int o, int l, int r) {
int mid = (l + r)>>1;
c[o][0][0] = c[o][0][1] = c[o][1][0] = c[o][1][1] = t[o] = 0;
if (!t[o<<1] || !t[o<<1|1])
return;
rep (i, 0, 1)
rep (j, 0, 1)
rep (x, 0, 1)
rep (y, 0, 1)
if (a[mid][x] <= a[mid + 1][y])
c[o][i][j] = max(c[o][i][j], c[o<<1][i][x] && c[o<<1|1][y][j]);
t[o] = c[o][0][0] || c[o][0][1] || c[o][1][0] || c[o][1][1];
}
void build_(int o, int l, int r) {
if (l == r) {
c[o][0][0] = c[o][1][1] = t[o] = 1;
return;
}
int mid = (l + r)>>1;
build_(o<<1, l, mid), build_(o<<1|1, mid + 1, r);
chk_(o, l, r);
}
void update_(int o, int l, int r, int x) {
if (l == r)
return;
int mid = (l + r)>>1;
if (x <= mid)
update_(o<<1, l, mid, x);
else
update_(o<<1|1, mid + 1, r, x);
chk_(o, l, r);
}
int main() {
scanf("%d", &n);
rep (i, 1, n)
scanf("%d%d", &a[i][0], &a[i][1]);
build_(1, 1, n);
scanf("%d", &m);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
swap(a[u], a[v]);
update_(1, 1, n, u), update_(1, 1, n, v);
printf("%s\n", t[1] ? "TAK" : "NIE");
}
}