题目分析

这是一个关于卡片序列的维护问题。每张卡片有两个数字（正反面），我们可以选择展示正面或反面。在多次交换操作后，需要判断能否通过选择每张卡片的展示面，使得整个序列的数字非递减。

关键观察

1. 决策的传递性：每张卡片有两种选择（正面或反面），但选择不是独立的。当前卡片的选择会影响下一张卡片的选择范围。

2. 状态设计：对于每个区间，我们需要维护：

   • 如果区间以较小值开始，整个区间能形成的最小结尾值
   • 如果区间以较大值开始，整个区间能形成的最小结尾值

3. 线段树维护：由于有大量的交换操作，我们需要用数据结构来高效维护区间信息。这里使用线段树，每个节点存储：

   • l0：区间第一张卡片使用较小值时的值
   • l1：区间第一张卡片使用较大值时的值
   • mn0：以较小值开始时，整个区间能形成的最小结尾值
   • mn1：以较大值开始时，整个区间能形成的最小结尾值

算法思路

1. 预处理：对于每张卡片，确保第一个值不大于第二个值，这样l0总是较小值，l1总是较大值。

2. 线段树构建：自底向上合并区间信息。合并时检查：

   • 如果左区间以较小值结束，右区间能否接上
   • 如果左区间以较大值结束，右区间能否接上

3. 查询判断：如果根节点的mn0不是无穷大，说明存在一种选择方案使得整个序列非递减。

4. 更新操作：交换卡片后，更新对应位置的线段树节点。

复杂度分析

• 时间复杂度：$O((n + m) \log n)$，构建线段树$O(n \log n)$，每次交换更新$O(\log n)$
• 空间复杂度：$O(n)$，存储线段树

代码实现

#include <algorithm>
#include <cctype>
#include <cstdio>
#define MAXN 200001
#define LMX 0x3f3f3f3f
using namespace std;

namespace IO {
#define SIZ (1 << 19)
static char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
#define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
inline void rd(int &x) {
    x = 0;
    char c = gc();
    while (!isdigit(c))
        c = gc();
    while (isdigit(c))
        x = x * 10 + (c ^ 48), c = gc();
}
template <typename... Arg>
inline void rd(int &x, Arg &...args) {
    rd(x), rd(args...);
}

static char obuf[SIZ], *p3 = obuf;
inline void flush() {
    fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
}
inline void pc(const char c) {
    if (p3 - obuf == SIZ)
        flush();
    *p3++ = c;
}
inline void prt(const char *s) {
    pc(s[0]), pc(s[1]), pc(s[2]), pc('\n');
}
#undef gc
#undef SIZ
}
using IO::prt;
using IO::rd;

struct {
    int x, y;
} a[MAXN];

namespace Seg {
struct Node {
    int l0, l1, mn0, mn1;
} nodes[MAXN << 2];

#define pusharg(ndid) nodes[ndid], nodes[(ndid) << 1], nodes[(ndid) << 1 | 1]

void pushup(Node &rt, const Node &ls, const Node &rs) {
    rt.l0 = ls.l0, rt.l1 = ls.l1;

    if (rs.l0 >= ls.mn0)
        rt.mn0 = rs.mn0;
    else if (rs.l1 >= ls.mn0)
        rt.mn0 = rs.mn1;
    else
        rt.mn0 = LMX;

    if (rs.l0 >= ls.mn1)
        rt.mn1 = rs.mn0;
    else if (rs.l1 >= ls.mn1)
        rt.mn1 = rs.mn1;
    else
        rt.mn1 = LMX;
}

void build(const int id, const int l, const int r) {
    if (l == r) {
        nodes[id].l0 = nodes[id].mn0 = a[l].x;
        nodes[id].l1 = nodes[id].mn1 = a[l].y;
        return;
    }
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    pushup(pusharg(id));
}

void update(const int id, const int l, const int r, const int pos) {
    if (l == r) {
        nodes[id].l0 = nodes[id].mn0 = a[l].x;
        nodes[id].l1 = nodes[id].mn1 = a[l].y;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(id << 1, l, mid, pos);
    else
        update(id << 1 | 1, mid + 1, r, pos);
    pushup(pusharg(id));
}

inline bool query() {
    return nodes[1].mn0 != LMX;
}
#undef pusharg
}
using Seg::query;
using Seg::update;

int main() {
    int n;
    rd(n);
    for (int i = 1; i <= n; ++i) {
        rd(a[i].x, a[i].y);
        if (a[i].x > a[i].y)
            swap(a[i].x, a[i].y);
    }

    Seg::build(1, 1, n);
    int q, x, y;
    rd(q);
    while (q--) {
        rd(x, y);
        if (x != y) {
            swap(a[x], a[y]);
            update(1, 1, n, x);
            update(1, 1, n, y);
        }
        prt(query() ? "TAK" : "NIE");
    }
    IO::flush();
    return 0;
}

总结

本题的关键在于将序列的可行性判断转化为区间信息的维护。通过线段树存储每个区间在不同起始选择下的最小可能结尾值，我们能够高效处理动态的卡片交换操作。

技巧亮点：

1. 将问题抽象为区间合并问题
2. 设计合适的状态表示区间信息
3. 使用线段树支持动态更新
4. 优化IO处理大量数据

这种"状态传递"的思想在很多序列问题中都有应用，值得掌握。