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

· · 题解

分析

现在本题仅存的题解未给出详细证明，故稍微写一下。

对于 \forall i<j \land id\in[1,k]，建立一条 p_{id,i}\rightarrow p_{id,j} 的有向边，自然一个 scc 中任选两个点都是一对 fuzzy pair。

定义两个序列本质相同当且仅当将其中一个任意重排可以得到另一个，考虑证明区间 [l,r] 的导出子图是 scc 当且仅当所有 k 个排列中 [l,r] 区间本质相同且不存在位置 w 满足前缀 [l,w] 本质相同。我们使用反证法，若这样的区间不是 scc，设两个点 x,y 满足不存在 y\rightarrow x 的路径，由于任意两个点均有偏序关系，故必然存在 x\rightarrow y 的路径，则所有排列中该区间均形如 \{\cdots,x,\cdots,y,\cdots\}，我们将位于 x 前面的数称为前面部分，中间部分和后面部分以此类推。由于存在 y 到后面部分的任何一个点的路径，故所有排列中的后面部分在其它排列中都不位于前面部分。所以对于一个新的排列，我们可以将它看做将某一些后面部分的数和中间部分的数做了交换得到的。设被交换至最左侧的数是 s，则排列形如 \{\cdots,x,\cdots,s,\cdots,y,\cdots\}，位于 s,y 中间的部分显然不可能来自原排列的前面部分，否则设该数为 z，则有 y\rightarrow s\rightarrow z\rightarrow x 的路径。这样一来 s 开头的后缀是本质相同的，意味着 [l,pos_s-1] 这段前缀本质相同，与一开始的假设矛盾。故原命题成立。

现在我们令一个断点 x 是满足 \displaystyle\left|\bigcup_{i=1}^kp_i[1,x]\right|=x 的数，即所有排列的大小为 x 的前缀本质相同，不难发现根据上述命题，相邻两断点的导出子图是 scc。那么一段询问区间必定由若干个完整的 scc 与至多两个不完整的 scc 组成，则可以前缀和预处理。

AC Code


#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int c(int x)
{
    return x*(x-1)/2;
}
void solve()
{
    int n,k,q;
    cin>>n>>k>>q;
    vector<vector<int>> a(k+1);
    for(int i=1;i<=k;i++)
    {
        a[i].push_back(0);
        int x;
        for(int j=1;j<=n;j++) cin>>x,a[i].push_back(x);
    }
    set<int> st;
    vector<int> pos,d(n+1);
    pos.push_back(0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++) st.insert(a[j][i]);
        if(st.size()==i) d[i]=pos.size(),pos.push_back(i);
    }
    vector<int> sum;
    sum.push_back(0);
    for(int i=1;i<pos.size();i++) sum.push_back(sum[sum.size()-1]+c(pos[i]-pos[i-1]));
//  for(int i=1;i<sum.size();i++) cout<<"sum["<<i<<"]="<<sum[i]<<'\n';
    int lastans=0; 
    while(q--)
    {
        int id,l,r;
        cin>>id>>l>>r;
        id=(id+lastans)%k+1;l=(l+lastans)%n+1;r=(r+lastans)%n+1;
        int ans=0;
        int nl=*lower_bound(pos.begin(),pos.end(),l);
        if(nl>=r)
        {
            cout<<(lastans=c(r-l+1))<<'\n';
            continue;
        }
        int nr=*(--upper_bound(pos.begin(),pos.end(),r));
        cout<<(lastans=(c(nl-l+1)+c(r-nr)+sum[d[nr]]-sum[d[nl]]))<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--) solve();
}