非常 OI 的一道题
看到这题就往图论的方向去想了，但其实能看出本质与竞赛图有关的话甚至能更快，只可惜事先没有接触过，敏感度不够。
往正常方向推也挺好推的，但其实我在第一步就炸了，我考虑的是怎么利用整个排名表的信息维护一位选手的答案傻逼吗我是，这里两者信息完全不对等，大量信息被浪费。
从这就能看出来应该维护冠军集合，后面冠军集合在表上的分布什么的一下就能推出来，就是原矩阵的前缀嘛。所以维护集合就变成了维护一个位置，满足这个位置前每个人都出现了三次。
很容易用线段树维护，然后线段树二分。
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long;
const int N=1e5+10;
int n,q;
int a[5][N];
int rk[N][5];
struct st{
struct node{
int v,tag;
}d[N<<3|1];
void pushup(int p){
int l=p<<1,r=l|1;
d[p].v=min(d[l].v,d[r].v);
}
void pushdown(int p){
if(d[p].tag){
int l=p<<1,r=l|1;
d[l].tag+=d[p].tag;
d[r].tag+=d[p].tag;
d[l].v+=d[p].tag;
d[r].v+=d[p].tag;
d[p].tag=0;
}
}
void add(int ql,int qr,int k,int p=1,int l=2,int r=2*n){
if(ql>qr)return ;
if(ql<=l&&r<=qr){
d[p].tag+=k;
d[p].v+=k;
return;
}
int mid=l+r>>1;
pushdown(p);
if(ql<=mid)add(ql,qr,k,p<<1,l,mid);
if(qr>mid)add(ql,qr,k,p<<1|1,mid+1,r);
pushup(p);
}
int query(int p=1,int l=2,int r=2*n){
if(l==r)return l;
int mid=l+r>>1;
pushdown(p);
if(!d[p<<1].v)return query(p<<1,l,mid);
else return query(p<<1|1,mid+1,r);
}
void print(int p=1,int l=2,int r=2*n){
if(l==r){
printf("%d ",d[p].v);
return;
}
int mid=l+r>>1;
pushdown(p);
print(p<<1,l,mid);
print(p<<1|1,mid+1,r);
}
}t;
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<=3;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]);
for(int i=1;i<=3;++i)
for(int j=1;j<=n;++j)
rk[a[i][j]][i]=j;
#define min3(c) min(min(c[1],c[2]),c[3])
#define max3(c) max(max(c[1],c[2]),c[3])
for(int i=1;i<=n;++i){
t.add(2*min3(rk[i]),2*n,1),t.add(2*max3(rk[i])+1,2*n,-1);
// t.print();
// printf("\n%d %d\n",2*min3(rk[i]),2*max3(rk[i])+1);
}
while(q--){
int op;
scanf("%d",&op);
if(op==1){
int x;
scanf("%d",&x);
int res=t.query();
if(2*min3(rk[x])<=res)printf("DA\n");
else printf("NE\n");
}
else {
int p,x,y;
scanf("%d%d%d",&p,&x,&y);
t.add(2*min3(rk[x]),2*n,-1),t.add(2*max3(rk[x])+1,2*n,1);
t.add(2*min3(rk[y]),2*n,-1),t.add(2*max3(rk[y])+1,2*n,1);
// swap(a[p][x],a[p][y]);
swap(rk[x][p],rk[y][p]);
t.add(2*min3(rk[x]),2*n,1),t.add(2*max3(rk[x])+1,2*n,-1);
t.add(2*min3(rk[y]),2*n,1),t.add(2*max3(rk[y])+1,2*n,-1);
}
}
return 0;
}
// 4 4
// 1 2 3 4
// 2 1 3 4
// 2 1 3 4
// 2 3 1 4
// 1 4