Description

有 $n$ 张卡片在桌上一字排开，每张卡片上有两个数，第i张卡片上，正面的数为 $a_i$，反面的数为 $b_i$。现在，有 $m$ 个熊孩子来破坏你的卡片了！

第i个熊孩子会交换 $c_i$ 和 $d_i$ 两个位置上的卡片。
每个熊孩子捣乱后，你都需要判断，通过任意翻转卡片（把正面变为反面或把反面变成正面，但不能改变卡片的位置），能否让卡片正面上的数从左到右单调不降。

Input Format

第一行一个 $n$。
接下来 $n$ 行，每行两个数 $a_i,b_i$。
接下来一行一个 $m$。
接下来 $m$ 行，每行两个数 $c_i,d_i$。

Output Format

$m$ 行，每行对应一个答案。如果能成功，输出TAK，否则输出NIE。

Sample Input

Sample Output

1
2

NIE
TAK

题目分析：

线段树区间合并题。看见题目有一个显而易见的贪心策略：为了以后更好的发展，当前选择的卡牌总是尽可能让它小的一面朝上，实在不行在大的一面朝上。大的一面都不行无解凉凉。

~~不过这题能用线段树做是真的挺神仙。~~

线段树记录下该区间内，第一张卡片选择小的一面和大的一面最后一张卡片能取得的最小值。若无法让整个序列单调不减为 $\infty$。线段树不需要支持查询操作，挺好写。不过这道题质量真的挺高。

每个区间很容易由它的两个子区间合并而来，详见代码。

$Code:$

#include <cstdio>
#include <algorithm>
#define inf 0x3fffffff
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 131072, stdin), p1 == p2) ? EOF : *p1 ++)

char buf[131072], *p1, *p2;
inline int read() {
char ch;
int x(0);
while ((ch = gc) < 48);
while (ch >= 48) x = x * 10 + ch - 48, ch = gc;
return x;
}

struct Pair {
int x, y;
} card[200005];

struct Segment_tree {
struct node {
int l, r, v1, v2;
} a[800005];

inline void Solve(int O) {
int mid(a[O << 1].r + 1);
if (a[O << 1].v1 <= card[mid].y) {
if (a[O << 1].v1 <= card[mid].x) a[O].v1 = a[O << 1 | 1].v1;
else a[O].v1 = a[O << 1 | 1].v2;
if (a[O << 1].v2 <= card[mid].y) {
if (a[O << 1].v2 <= card[mid].x) a[O].v2 = a[O << 1 | 1].v1;
else a[O].v2 = a[O << 1 | 1].v2;
}
else a[O].v2 = inf;
}
else a[O].v1 = a[O].v2 = inf;
}

void make_tree(int O, int L, int R) {
a[O].l = L, a[O].r = R;
int mid(L + R >> 1);
if (L != R) make_tree(O << 1, L, mid), make_tree(O << 1 | 1, mid + 1, R), Solve(O);
else a[O].v1 = card[L].x, a[O].v2 = card[L].y;
}

void update(int O, int p) {
if (a[O].l == a[O].r) {a[O].v1 = card[a[O].l].x, a[O].v2 = card[a[O].l].y; return;}
if (a[O << 1].r >= p) update(O << 1, p);
else update(O << 1 | 1, p);
Solve(O);
}
} Tree;

int main()  {
int n(read()), m;
for (int i(1); i <= n; ++ i) {
card[i].x = read(), card[i].y = read();
if (card[i].x > card[i].y) std::swap(card[i].x, card[i].y);
}
Tree.make_tree(1, 1, n);
m = read();
while (~-- m) {
int c(read()), d(read());
std::swap(card[c], card[d]);
Tree.update(1, c), Tree.update(1, d);
if (Tree.a[1].v1 <= 1e9) puts("TAK");
else puts("NIE");
}
}

zqs`s blog

POI2014 & NKOJ 3777 卡牌操作