专栏文章

题解：P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking

BBinah_cyc
P14192题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkbcvj
此快照首次捕获于
2025/12/02 03:48
3 个月前
此快照最后确认于
2025/12/02 03:48
3 个月前
查看原文
首先考虑如何刻画题目中提到的优越关系，发现对于一个榜，将前面的元素向后面的元素连单向边边，则 AA 优越于 BB 当且仅当存在一条 AA 到 BB 的路径。那么两个大学是模糊的当且仅当两个大学位于同一个强连通分量里。
题意转化为了给你一个无向图，每一次从无向图中抽出一条链，链的前一个元素向后一个元素连边，问你有多少对数在同一条链里。
发现这个链上每一个强连通分量的区域是连续的。证明就是强连通分量里任意两个点都有互相到对方的路径，这是充要的。如果一条链上连续三个点分别为 A,B,CA,B,C 且 AA 与 CC 在同一个连通分量里，则 AA 可以直接到达 BB，且 BB 可以到达 CC，CC 可以到达 AA，故 BB 能够到达 AA。所以 AA 与 BB 在同一个连通分量里。
这样就好做了。对于每一个榜，我们把每一个强连通分量的区间找出来，一个长度为 lenlen 的区间贡献显然为 len×(len−1)2{len\times (len-1)}\over 2，给它做前缀和。然后询问的时候整块前缀和，散块二分它所属于的端点，能做到 O(nk+qlog⁡n)O(nk+q\log n)。对于每一个位置处理出来它所对应的区间左右端点能消掉这个 log⁡\log，做到 nk+qnk+q。
我写的二分做法。
C

// Problem: P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14192
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define retunr return
bool startmb;
constexpr itn N=2e5+5;
int _,n,m,q;
vector<int> a[N],sum[N];

int head[N],to[N];

int dfn_tot,scc_tot,dfn[N],low[N],scc[N];
bool vis[N];
vector<int> vec;
void tarjan(int now,int fa)
{
	dfn[now]=low[now]=++dfn_tot,vec.push_back(now),vis[now]=1;
	for(int i=head[now];i<head[now+1];i++)
	{
		if(!dfn[to[i]]) tarjan(to[i],now),low[now]=min(low[now],low[to[i]]);
		else if(vis[to[i]]) low[now]=min(low[now],dfn[to[i]]);
	}
	if(dfn[now]==low[now])
	{
		scc_tot++;
		while(vec.back()!=now) scc[vec.back()]=scc_tot,vis[vec.back()]=0,vec.pop_back();
		scc[now]=scc_tot,vec.pop_back(),vis[now]=0;
	}
}

bool endmb;
main()
{
	cerr<<((&startmb-&endmb)/1024.0/1024)<<endl;
	cin>>_;
	while(_--)
	{
		cin>>n>>m>>q;
		for(int i=1;i<=m;i++)
		{
			a[i].resize(n+2),sum[i].resize(n+2);
			for(int j=1;j<=n;j++) cin>>a[i][j];
		}
		for(int i=1;i<=m;i++) for(int j=1;j<n;j++) head[a[i][j]]++;
		for(int i=1;i<=n;i++) head[i+1]+=head[i];
		for(int i=1;i<=m;i++) for(int j=1;j<n;j++) to[--head[a[i][j]]]=a[i][j+1];
		for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
		for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) sum[i][scc[a[i][j]]]++;
		for(int i=1;i<=m;i++) for(int j=1;j<=scc_tot;j++) sum[i][j]=sum[i][j]*(sum[i][j]-1)/2;
		for(int i=1;i<=m;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(scc[a[i][j]]!=scc[a[i][j-1]]) sum[i][scc[a[i][j]]]+=sum[i][scc[a[i][j-1]]];
			}
		}
		int lstans=0;
		while(q--)
		{
			int id,l,r;
			cin>>id>>l>>r;
			id=(id+lstans)%m+1,l=(l+lstans)%n+1,r=(r+lstans)%n+1;
			if(l>r) return 0;
			if(scc[a[id][l]]==scc[a[id][r]]) cout<<(lstans=(r-l+1)*(r-l)/2)<<'\n';
			else
			{
				int lp=l,rp=n,lans=0,rans=0;
				while(lp<=rp)
				{
					int mid=(lp+rp)>>1;
					if(scc[a[id][l]]==scc[a[id][mid]]) lp=mid+1,lans=mid;
					else rp=mid-1;
				}
				lp=1,rp=r;
				while(lp<=rp)
				{
					int mid=(lp+rp)>>1;
					if(scc[a[id][r]]==scc[a[id][mid]]) rp=mid-1,rans=mid;
					else lp=mid+1;
				}
				cout<<(lstans=(lans-l+1)*(lans-l)/2+(r-rans+1)*(r-rans)/2+sum[id][scc[a[id][rans-1]]]-sum[id][scc[a[id][l]]])<<'\n';
			}
		}
		for(int i=1;i<=n+1;i++) head[i]=0,vis[i]=dfn[i]=low[i]=scc[i]=0;
		for(int i=1;i<=m;i++) a[i].clear(),sum[i].clear(),a[i].shrink_to_fit(),sum[i].shrink_to_fit();
		dfn_tot=scc_tot=0;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...