P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking 题解

思路分析：

考虑排名在前的向排名在后的连边，那么“优越于”即可达，“模糊对”即强联通。设区间内第

i

个 SCC 的大小分别为

S_i

，答案为

\sum \dfrac{S_i\cdot(S_i-1)}{2}

。

Kosaraju 或 Tarjan 跑一边求出每个点所在的 SCC，发现这个问题变成了经典的莫队板题，但强制在线。可以分块大力维护，但直觉上都图论建模了大概率是有性质的。输出每个点 SCC 的编号发现每个 SCC 都是连续的一段，可以多随几组数据看看。

证明：每次建边都是相邻点，即合并相邻的 SCC，一开始都是独立的，不难归纳出这个结论。

于是分成 SCC 整体和区间左右的散块分别做即可，前缀和维护，注意开 long long。

AC Code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int t[N],c[N];
bitset<N>vis;
vector<int>a[N],e[N],l[N],r[N];
vector<long long>s[N];
void dfs(int u,int col){
	vis[u]=1,c[u]=col;
	for(int v:e[u])if(!vis[v])dfs(v,col);
}
void solve(){
	int n,k,q;cin>>n>>k>>q;
	for(int i=1;i<=n;i++)e[i].clear();
	for(int i=1;i<=k;i++){
		a[i].resize(n+2);
		for(int j=1;j<=n;j++)cin>>a[i][j];
		for(int j=1;j<n;j++)e[a[i][j+1]].push_back(a[i][j]);
	}
	vis.reset();
	for(int j=1;j<=n;j++)if(!vis[a[1][j]])dfs(a[1][j],j);
	for(int i=1;i<=k;i++){
		l[i].resize(n+2),r[i].resize(n+2),s[i].resize(n+2);
		int L=l[i][1]=1,R=r[i][n]=n;
		for(int j=1;j<=n;j++)
			s[i][j]=0;
		for(int j=2;j<=n;j++){
			if(c[a[i][j]]!=c[a[i][j-1]])
				s[i][j-1]+=1ll*(j-L)*(j-L-1)/2,L=j;
			l[i][j]=L,s[i][j]+=s[i][j-1];
		}
		for(int j=n-1;j;j--){
			if(c[a[i][j]]!=c[a[i][j+1]])R=j;
			r[i][j]=R;
		}
	}
	long long ans=0;
	while(q--){
		int id,L,R;cin>>id>>L>>R;id=(id+ans)%k+1;
		L=(L+ans)%n+1;R=(R+ans)%n+1;if(L>R)swap(L,R);
		if(c[a[id][L]]==c[a[id][R]])ans=1ll*(R-L+1)*(R-L)/2;
		else ans=s[id][l[id][R]-1]-s[id][r[id][L]]+
				1ll*(r[id][L]-L+1)*(r[id][L]-L)/2+
				1ll*(R-l[id][R]+1)*(R-l[id][R])/2;
		cout<<ans<<'\n';
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;while(T--)solve();
	return 0;
}

P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking 题解

文章操作

思路分析：

AC Code:

相关推荐

评论

P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking 题解