原题链接：Problem - C2 - Codeforces
题意：给出长度为n的数组p，这是一个1~n的排列，含义是第i个位置站着第p[i]号人。给出长度为m的数组q，含义是第i个幻灯片被第p[i]号人讲解，那么就是完美的，每个幻灯片都需要有人来讲解，每次讲解的人必须是数组p的第一个人，当某个人讲解完成之后，他可以去数组p的任何位置，有k次询问每次会改变q数组，每次给出q和w，让q[x]=w，每次改变都是永久的。输出k+1行，判断初始情况是否可以完成讲解和每次询问是否可以完成讲解，完成讲解的定义是每个幻灯片都被完美讲解。
思路：通过模拟可以知道，如果某个人讲解完成了之后，那么这个人就是自由的，他一定可以去需要他的位置，所以只要幻灯片需要的人正好是第一个或者这个人是自由的，那么就是完美的。如果不修改q数组，那么只要让q数组中不同数出现的相对位置和p数组中相同就可以了。可以观察到，如果完成讲解p数组中的数在q数组里面第一次出现的下标一定是升序的，用f数组来代表p数组里面每个数第一次在q数组里面出现的位置，完成讲解的情况下一定满足f[p[i]]<f[p[i+1]]。每次询问可能改变的是q[x]和w第一次出现的位置，如何判断改变后的状态和改变前的状态是否不同，那么可以用cnt来表示f[p[i]]>f[p[i+1]]的个数，如果是0那么就是完成讲解。因为要找到每个数第一次出现的位置，所以需要一个有序的容器来装每个数的位置，使用set。
//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll p[N],id[N],q[N];
set<ll> st[N];
ll f[N];
ll cnt,n,m,sb;
void updata(ll x,ll op)
{//如果这个数，在p数组中左右还有数的情况下，那么就先考虑删除这个数变化之前的影响。//id[q[x]]是q[x]在p中的位置p[id[q[x]]是q[x],p[id[q[x]]-1]是q[x]在p中位置的左边的数，f[p[id[q[x]]-1]]是左边数第一次出现的位置 if(id[q[x]]-1>0)cnt=cnt-(f[p[id[q[x]]-1]]>f[p[id[q[x]]]]);if(id[q[x]]+1<=n)cnt=cnt-(f[p[id[q[x]]]]>f[p[id[q[x]]+1]]);if(op)st[q[x]].insert(x);else st[q[x]].erase(x);f[q[x]]=*st[q[x]].begin();//更新f数组之后，重新加上x这个位置的影响。 if(id[q[x]]-1>0)cnt=cnt+(f[p[id[q[x]]-1]]>f[p[id[q[x]]]]);if(id[q[x]]+1<=n)cnt=cnt+(f[p[id[q[x]]]]>f[p[id[q[x]]+1]]);
}
void Jiuyuan()
{cnt=0;cin>>n>>m>>sb;for(int i=1;i<=n;i++)//读入p[i]，映射p[i]这个数的位置，清空之前的set，插入一个很大的数 {cin>>p[i];id[p[i]]=i;st[i].clear(); st[i].insert(1e9);}for(int i=1;i<=m;i++){cin>>q[i];st[q[i]].insert(i);}for(int i=1;i<=n;i++)//f数组含义是这个数第一次出现的位置 {f[p[i]]=*st[p[i]].begin();}for(int i=1;i<n;i++) {cnt=cnt+(f[p[i]]>f[p[i+1]]);}if(cnt==0){cout<<"YA"<<endl;}else cout<<"TIDAK"<<endl;while(sb--){ll x,w;cin>>x>>w;updata(x,0);q[x]=w;updata(x,1);if(cnt==0){cout<<"YA"<<endl;}else cout<<"TIDAK"<<endl;}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}
