题目链接：P3569 [POI2014] KAR-Cards
来自同机房大佬 @L_ndyz 的奇特想法。
首先，这道题目询问能否构成一个不下降序列，这显然可以设计一个状态转移方程，如果符合不下降，就给数组加上一，这实际上是在统计转移的次数，最终只需要询问下标为 \(n\) 的数组，若小于 \(n\) 说明无法满足整个序列都满足不下降。
这题又添加了一张卡牌有正反面，就需要分情况了。
定义 \(f\) 数组第一维存牌的标号，第二维存正面或者反面朝上。
代码如下：
f[i][0] = max(f[i - 1][0] + (a[i] >= a[i-1]), f[i - 1][0] + (a[i] >= b[i-1]));
f[i][1] = max(f[i - 1][1] + (b[i] >= a[i-1]), f[i - 1][1] + (b[i] >= b[i-1]));
我们发现，每张牌都只有可能被他由一张牌转移，不难想到用矩阵加速。
怎么构建矩阵呢？构建什么矩阵呢？
下面给出转移矩阵：
for(int i = 2; i <= n; i++){
s[i].st[0][0] = (a[i] >= a[i-1]);
s[i].st[1][0] = (a[i] >= b[i-1]);
s[i].st[0][1] = (b[i] >= a[i-1]);
s[i].st[1][1] = (b[i] >= b[i-1]);
}
然后自定义矩阵运算为取最大值，岂不是完美完成了上面的转移操作啦？
现在考虑更换两张卡片，对于转移矩阵，会对谁有影响？不难想到，只会对更换的这两张和每一张的后面一张（总共四张）卡片有影响，这些我们就重新构造一下转移矩阵就好了。然后用线段树进行计算，求值。经过这些优化（再吸个氧），上面的暴力做法就变得非常华丽啦，收工！
见代码：
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
struct pp{
int st[2][2];//矩阵
pp(){ memset(st,0,sizeof(st));}
pp operator*(pp a){
pp c;
for(int i = 0;i < 2; i++){
for(int j = 0;j < 2; j++){
for(int k = 0;k < 2; k++){
c.st[i][j] = max(c.st[i][j],st[i][k] + a.st[k][j]);//广义矩阵乘法
}
}
}
return c;
}
};
int n,m;
int a[200100],b[200100];
pp s[200100];
void change_point(int i){//改点值
if(i == 1) return ;//初始矩阵不用改
s[i].st[0][0] = (a[i] >= a[i - 1]); s[i].st[1][0] = (a[i] >= b[i - 1]);
s[i].st[0][1] = (b[i] >= a[i - 1]); s[i].st[1][1] = (b[i] >= b[i - 1]);
}
struct tree{ int l,r; pp sum; }t[800100];
void build(int p,int L,int R){
t[p].l = L; t[p].r = R;
if(L == R){ t[p].sum = s[L];return ;}
int mid = (L + R) >> 1;
build(p * 2,L,mid);build(p * 2 + 1,mid + 1,R);
t[p].sum = t[p * 2].sum * t[p * 2 + 1].sum;
}
void change_tree(int p,int x){
if(t[p].l == t[p].r){
t[p].sum = s[t[p].l]; return ;
}
int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) change_tree(p * 2,x);
else change_tree(p * 2 + 1,x);
t[p].sum = t[p*2].sum * t[p * 2 + 1].sum;
}
inline int read(){
int x = 0,f = 1; char ch=getchar();
while (ch < '0' || ch > '9'){if (ch == '-') f = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}
return x * f;
}
void swap(int &x,int &y){
int t=x; x=y; y=t;
}
signed main(){
cin>>n;
for(int i = 1; i <= n; i++){
a[i] = read();b[i] = read();
}
s[1].st[0][0]=1;s[1].st[0][1]=1;//构造初始状态矩阵
for(int i = 2; i <= n; i++){//根据转移方式构造每一步的矩阵
s[i].st[0][0] = (a[i] >= a[i-1]);
s[i].st[1][0] = (a[i] >= b[i-1]);
s[i].st[0][1] = (b[i] >= a[i-1]);
s[i].st[1][1] = (b[i] >= b[i-1]);
}
build(1,1,n);//建线段树
cin>>m;
for(int i = 1; i <= m; i++){
int x, y; x = read(); y = read();
swap(a[x],a[y]); swap(b[x],b[y]);
//更换两张卡，这两张卡只会对 x，x+1，y，y+1的矩阵有影响
if(x != 1) change_point(x), change_tree(1,x);
if(x + 1 <= n) change_point(x + 1),change_tree(1,x + 1);
if(y != 1) change_point(y), change_tree(1,y);
if(y + 1 <= n) change_point(y + 1),change_tree(1,y + 1);
pp ans = t[1].sum;
if(ans.st[0][0] < n && ans.st[0][1] < n) puts("NIE");//无法构成长度为 n 的不下降序列
else puts("TAK");
}
return 0;
}