[ABC350G] Mediator 题解

FFTotoro · 2024-04-21 19:24:45 · 题解

有人问 G 的根号做法。那就随便写点。

简单地将点按照度数是否超过 \sqrt{n} 进行分类，\deg_u>\sqrt{n} 的 u 称为大点，反之称为小点。容易得知大点数量 \le\sqrt{n}。所以对于大点提前处理出所有答案，用 std::map 存储，询问时直接查询已经求得的答案；对于小点遍历所有出边直接暴力查，存边使用 std::set。

每次合并时简单判断一个点是否成为大点即可。如果是这个点第一次成为大点就直接进行搜索，否则就更新新加进来的点即可。

时间复杂度 O(n\sqrt{n}\log n)，但是实际上跑起来常数很小，10^5 稳稳跑进 400ms。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P=998244353;
main(){
  ios::sync_with_stdio(false);
  int n,q,l=0,sq; cin>>n>>q,sq=sqrt(n);
  vector<int> d(n);
  vector<set<int> > g(n);
  map<pair<int,int>,int> t;
  auto I=[&](int u,int v,int w){
    t[make_pair(min(u,v),max(u,v))]=w;
  }; // 大点提前预处理答案
  auto Q=[&](int u,int v)->int{
    if(u>v)swap(u,v);
    if(t.find(make_pair(u,v))==t.end())return -1;
    return t[make_pair(u,v)];
  }; // 查询大点的答案
  while(q--){
    int a,b,c; cin>>a>>b>>c;
    a=((l+1)*a%P&1)+1,b=(l+1)*b%P%n,c=(l+1)*c%P%n;
    if(a==1){
      d[b]++,d[c]++,g[b].emplace(c),g[c].emplace(b);
      if(d[b]==sq) // 第一次成为大点
        for(int i:g[b])
          for(int j:g[i])I(b,j,i);
      else if(d[b]>sq) // 不是第一次，只加新的
        for(int j:g[c])I(b,j,c);
      if(d[c]==sq)
        for(int i:g[c])
          for(int j:g[i])I(c,j,i);
      else if(d[c]>sq)
        for(int j:g[b])I(c,j,b);
    }
    else{
      if(d[b]>d[c])swap(b,c);
      if(d[b]<=sq){ // 小点直接暴力
        bool f=false;
        for(int i:g[b])
          if(g[c].find(i)!=g[c].end()){
            cout<<(l=i+1)<<'\n',f=true; break;
          }
        if(!f)cout<<(l=0)<<'\n';
      }
      else cout<<(l=Q(b,c)+1)<<'\n';
    }
  }
  return 0;
}