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

· · 题解

模拟赛 T3，考试的时候写红温了没有注意到强制在线。

爽爽挂分，我生气了。

优越关系可以看成一条单向边，(x,y) 是模糊对等价于 x,y 在同一个强连通分量里。

排名更靠前是可以传递的，因此只需要每个数向后一个连边即可。

手玩几组数据可以得到每个强连通分量中的点在每份排名中是一段连续的区间，证明也很简单。

每次建边都是相邻点，另外的排名中的建边有贡献的只有反向边，就等价于合并了中间的若干强连通分量。

没注意到这个性质也能做，我同学直接莽了个分块上去。

这样每次查询就等价于两个不完整区间和中间若干完整区间，前缀和维护完整区间即可。

考场代码，有点混乱，仅供参考。

#include<bits/stdc++.h>
using namespace std;
typedef long long lo;
/*为了阅读体验省略了快读快写*/
const int N=2.5e5+5;
lo T,n,k,q,dfn[N],low[N],dfsn,stk[N],tp,scc,lsres;
bool op;
vector<lo>a[N],ve[N],id[N],pre[N],bel[N];
vector<pair<lo,lo>>area[N];
bitset<N>vis,ins;
void CheckMin(lo&x,lo y){x=min(x,y);}
void CheckMax(lo&x,lo y){x=max(x,y);}
void Tarjan(lo u)
{
  dfn[u]=low[u]=++dfsn;
  stk[++tp]=u;ins.set(u);
  vis.set(u);
  for(lo v:ve[u])
  {
    if(!vis.test(v))Tarjan(v),CheckMin(low[u],low[v]);
    else if(ins.test(v))CheckMin(low[u],dfn[v]);
  }
  if(low[u]==dfn[u])
  {
    scc++;lo x;
    do
    {
      x=stk[tp--];
      for(lo i=1;i<=k;i++)
        CheckMin(area[i][scc].first,id[i][x]),
        CheckMax(area[i][scc].second,id[i][x]);
      ins.reset(x);
    }while(x!=u);
  }
}
void gm(lo&ii,lo&l,lo&r)
{
  lo tmpi=ii,tmpl=l,tmpr=r;
  ii=((tmpi+lsres)%k)+1;
  l=min((tmpl+lsres)%n,(tmpr+lsres)%n)+1;
  r=max((tmpl+lsres)%n,(tmpr+lsres)%n)+1;
}
lo calc(lo l,lo r){lo len=r-l+1;return len*(len-1)/2;}
void solve()
{
  read(n,k,q);
  vis.reset();ins.reset();
  dfsn=scc=tp=lsres=0;
  for(lo i=1;i<=n;i++)ve[i].clear(),dfn[i]=low[i]=0;
  for(lo i=1;i<=k;i++)
  {
    a[i].resize(n+1);id[i].resize(n+1);
    area[i].resize(n+1);pre[i].resize(n+1);
    bel[i].resize(n+1);
    for(lo j=1;j<=n;j++)read(a[i][j]),id[i][a[i][j]]=j,area[i][j]={n+1,0};
    for(lo j=1;j<n;j++)ve[a[i][j]].push_back(a[i][j+1]);
  }
  for(lo i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
  for(lo i=1;i<=k;i++)
  {
    sort(area[i].begin(),area[i].end());
    for(lo j=1;j<=scc;j++)pre[i][j]=pre[i][j-1]+calc(area[i][j].first,area[i][j].second);
    for(lo j=1;j<=scc;j++)for(lo k=area[i][j].first;k<=area[i][j].second;k++)
      bel[i][k]=j;
  }
  for(lo ii,l,r;q--;)
  {
    read(ii,l,r);gm(ii,l,r);
    lo L=bel[ii][l],R=bel[ii][r];lsres=0;
    if(L==R)lsres=calc(l,r);
    else
    {
      if(l!=area[ii][L].first)lsres+=calc(l,area[ii][L++].second);
      if(r!=area[ii][R].second)lsres+=calc(area[ii][R--].first,r);
      if(L<=R)lsres+=pre[ii][R]-pre[ii][L-1];
    }
    write(lsres,'\n');
  }
}
int main(){read(T);while(T--)solve();}
/*
_|       _|_|_|_| _|_|_|_|
_|           _|   _|    _|
_|         _|     _|  _|_|
_|_|_|_| _|_|_|_| _|_|_|_|_|
*/