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

· · 题解

首先考虑如何刻画题目中提到的优越关系，发现对于一个榜，将前面的元素向后面的元素连单向边边，则 A 优越于 B 当且仅当存在一条 A 到 B 的路径。那么两个大学是模糊的当且仅当两个大学位于同一个强连通分量里。

题意转化为了给你一个无向图，每一次从无向图中抽出一条链，链的前一个元素向后一个元素连边，问你有多少对数在同一条链里。

发现这个链上每一个强连通分量的区域是连续的。证明就是强连通分量里任意两个点都有互相到对方的路径，这是充要的。如果一条链上连续三个点分别为 A,B,C 且 A 与 C 在同一个连通分量里，则 A 可以直接到达 B，且 B 可以到达 C，C 可以到达 A，故 B 能够到达 A。所以 A 与 B 在同一个连通分量里。

这样就好做了。对于每一个榜，我们把每一个强连通分量的区间找出来，一个长度为 len 的区间贡献显然为 {len\times (len-1)}\over 2，给它做前缀和。然后询问的时候整块前缀和，散块二分它所属于的端点，能做到 O(nk+q\log n)。对于每一个位置处理出来它所对应的区间左右端点能消掉这个 \log，做到 nk+q。

我写的二分做法。


// 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;
}