自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:06:34，当前版本为作者最后更新于2024-12-31 23:18:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

今年做的最后一道题了 /kel

如果 $i$ 某一维度比 $j$ 强，则 $i \to j$ 建立有向边。

这个东西的边数是严格包含一个竞赛图的，所以 $\rm SCC$ 缩点后会变成这样的形态：

因此最上面那个 $\rm SCC$ 满足：设集合为 $S$，则 $\forall 1 \le i \le 3$，$u \in S$，$v \notin S$，$p_{i,u} > p_{i,v}$，其中 $p$ 表示的是一个人在这个场地上的能力。

这又等价于：三个能力从大到小排列的最小前缀，使得三个前缀元素构成的集合相同。设前缀长度为 $len$。

等价于：设 $r_{i,j}$ 为 $j$ 在 $i$ 场上的排名，则 $\max\{r_{1,i},r_{2,i},r_{3,i}\} \le len$ 的 $i$ 有 $len$ 个。

显然可以使用线段树维护这个东西，复杂度 $O(q \log n)$。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int n,q,rnk[MAXN][4],tag[MAXN<<2],mn[MAXN<<2];
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
void push_down(int k,int l,int r) {return tag[lson]+=tag[k],tag[rson]+=tag[k],mn[lson]+=tag[k],mn[rson]+=tag[k],tag[k]=0,void();}
void update(int k,int l,int r,int x,int y,int v) {
	if(x<=l&&r<=y) return tag[k]+=v,mn[k]+=v,void();
	push_down(k,l,r);
	if(x<=mid) update(lson,l,mid,x,y,v);
	if(y>mid) update(rson,mid+1,r,x,y,v);
	return mn[k]=min(mn[lson],mn[rson]),void();	
}
int bfind(int k,int l,int r) {
	if(mn[k]>0) return -1;
	if(l==r) return l;
	push_down(k,l,r);
	int ans=bfind(lson,l,mid);
	if(ans!=-1) return ans;
	return bfind(rson,mid+1,r);
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	ffor(i,1,n) {int v;cin>>v,rnk[v][1]=i;}
	ffor(i,1,n) {int v;cin>>v,rnk[v][2]=i;}
	ffor(i,1,n) {int v;cin>>v,rnk[v][3]=i;}
	ffor(i,1,n) update(1,1,n,i,n,1);
	ffor(i,1,n) update(1,1,n,max({rnk[i][1],rnk[i][2],rnk[i][3]}),n,-1);
	ffor(i,1,q) {
		int op;
		cin>>op;
		if(op==1) {
			int x;
			cin>>x;
			if(bfind(1,1,n)>=rnk[x][1]) cout<<"DA\n";
			else cout<<"NE\n";
		}
		else {
			int p,a,b;
			cin>>p>>a>>b;
			update(1,1,n,max({rnk[a][1],rnk[a][2],rnk[a][3]}),n,1);
			update(1,1,n,max({rnk[b][1],rnk[b][2],rnk[b][3]}),n,1);
			swap(rnk[a][p],rnk[b][p]);
			update(1,1,n,max({rnk[a][1],rnk[a][2],rnk[a][3]}),n,-1);
			update(1,1,n,max({rnk[b][1],rnk[b][2],rnk[b][3]}),n,-1);
		}
	}
	return 0;
}