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:

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