题解：P3569 [POI2014] KAR-Cards

本文主要是介绍题解：P3569 [POI2014] KAR-Cards，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

有 $n$ 个元素，第 $i$ 个元素有两个权值 $a_i$ 和 $b_i$ ；有 $m$ 次操作，每次操作会交换两个元素的位置，且都需要回答：是否存在一种方案，使得每个元素各选择一个权值后，组成的序列从左到右单调不降。

解法

完全可以把交换操作看作两次单点修改，每次只需要考虑一个元素的变化对答案的影响即可。对于一个区间中的元素，显然开头的数越小，该区间能够单调不降的概率越大。不妨设 $a_i<b_i$ ，考虑线段树，对于区间 $[L, R]$ 我们维护两个值：

第 $L$ 个元素选择 $a_L$ ，第 $R$ 个元素尽量小的情况下，第 $R$ 个元素会选择 $a_R$ ， $b_R$ 或无解；
第 $L$ 个元素选择 $b_L$ ，第 $R$ 个元素尽量小的情况下，第 $R$ 个元素会选择 $a_R$ ， $b_R$ 或无解。

合并两个相邻区间的信息时，我们枚举左区间 $[L, R]$ 选择 $a_L$ 或 $b_L$ 、右区间 $[L^{'}, R^{'}]$ 选择 $a_{L'}$ 或 $b_{L'}$ ，判断 $a_R<b_{L'}$ 是否成立（已经保证小区间内单调不降或无解）；最后贪心地让合并后的区间 $[L, R^{'}]$ 末尾选择的数尽可能小。总时间复杂度 $O(n+m\log n)$ 。

实现

开两个数组 $x, y$ 维护这两个值（直接存末尾卡牌选择的值）。在建树、修改的时候用子区间信息进行更新。令该区间为 $[l, r]$ ，两个子区间的编号为 $L, R$ （以 $mid=\lfloor\cfrac{l+r}{2}\rfloor$ 为界），我们枚举用 $x [L]$ 还是 $y [L]$ 连接两个子区间、用 $x [R]$ 还是 $y [R]$ 作为结尾，并且优先考虑使用较小的 $x [R]$ 作为结尾。我们在修改的时候顺便更换 $a, b$ 数组，则只需判断 $x [L]$ 或者 $y [L]$ 是否不大于 $a [mi d + 1]$ 或者 $b [mi d + 1]$ （共 $4$ 种）。最终该区间的末尾取决于 $R$ 子区间末尾的选择。注意处理好无解的情况。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct Card { int A,B; } a[maxn];
int x[maxn << 2], y[maxn << 2]; // x 第一张小，y 第一张大
#define lson l,mid,rt << 1
#define rson mid + 1,r,rt << 1 | 1
const int inf = 1e7 + 5;
void update(int l,int r,int rt) {int mid = l + r >> 1;int L = rt << 1, R = rt << 1 | 1; // 两个子区间的编号x[rt] = y[rt] = inf;// 分类讨论if (x[L] <= a[mid + 1].A) x[rt] = x[R];else if (x[L] <= a[mid + 1].B) x[rt] = y[R];if (y[L] <= a[mid + 1].A) y[rt] = x[R];else if (y[L] <= a[mid + 1].B) y[rt] = y[R];
}
void build(int l,int r,int rt) {if (l == r) return x[rt] = a[l].A, y[rt] = a[l].B, void(0);int mid = l + r >> 1;build(lson); build(rson); update(l,r,rt);
}
int now;
void modify(int l,int r,int rt,Card k) {if (l == r) return x[rt] = k.A, y[rt] = k.B, void(0);int mid = l + r >> 1;if (now <= mid) modify(lson,k);else modify(rson,k);update(l,r,rt);
}
int n,m;
int main() {scanf("%d",&n);for (int i = 1;i <= n;i ++) {scanf("%d%d",&a[i].A,&a[i].B);if (a[i].A > a[i].B)swap(a[i].A,a[i].B);}build(1,n,1);scanf("%d",&m);for (int i = 1,u,v;i <= m;i ++) {scanf("%d%d",&u,&v);swap(a[u],a[v]);now = u; modify(1,n,1,a[u]);now = v; modify(1,n,1,a[v]);puts(x[1] < inf || y[1] < inf ? "TAK" : "NIE");}return 0;
}