题解：P7298 [USACO21JAN] Dance Mooves G

· · 题解

Sol

不难想到 k 轮一组按组处理。可以用 set 存下一组结束后每个点能走到的位置，由于只是进行了 k 次互换，因此总数据量是 O(n+k) 的。容易发现，每个点向一组结束之后这个点所在位置连边，将会形成若干个环，因为每个点入度与出度要么均为零（也就是未曾交换）要么均为一（总有一个别的数来填这个位置）。

那么我们大可以分别独立地处理每个环。令一条边存储这个点这次变化中经过的所有位置，一个关键的性质是，所有边存储的位置总量也是 O(n+k) 的。如果 \lfloor\frac{m}{k}\rfloor 不小于环长，那么直接暴力合并整个环的位置信息给环上节点赋值即可。否则，每个点能走的都是相同一段长度的区间，双指针即可，开个桶记录各个位置出现次数，每次暴力枚举 set 内所有位置改即可。这里我代码实现得比较奶龙用了 multiset 见谅。

最后还有一个不完整的散段，在上述过程之前先预处理出每个点在最后这个散段会经过的所有位置，然后存答案的时候把每个点各自的信息合并进去即可。这部分信息总量显然也是 O(n+k) 的。

感觉应该比较详细了。视 n,k 等同阶复杂度 O(n\log n)。

Code

const int N=1e5+5,K=2e5+5,T=40;

ll n,k,m;
int a[K],b[K],plc[N],to[N],ne[N][T];
set<int> st[N],st2[N];
multiset<int> mst;
int ans[N];

bool vis[N];
vec<int> v;
void dfs(int x){
    v.pub(x);vis[x]=1;
    if(!vis[to[x]])dfs(to[x]);
}

inline void Main(){
    cin>>n>>k>>m;
    rep(i,1,n)plc[i]=i,st[i].insert(i),st2[i].insert(i);
    rep(i,1,k){
        cin>>a[i]>>b[i];
        st[plc[a[i]]].insert(b[i]);
        st[plc[b[i]]].insert(a[i]);
        swap(plc[a[i]],plc[b[i]]);
    }
    rep(i,1,n)to[plc[i]]=i,ne[plc[i]][0]=i;
    rep(i,1,n)plc[i]=i;
    rep(i,1,m%k){
        st2[plc[a[i]]].insert(b[i]);
        st2[plc[b[i]]].insert(a[i]);
        swap(plc[a[i]],plc[b[i]]);
    }
    repl(t,1,T)rep(i,1,n)ne[i][t]=ne[ne[i][t-1]][t-1];
    ll tm=m/k;
    rep(i,1,n){
        plc[i]=i;
        per(t,T-1,0)if(tm>>t&1)plc[i]=ne[plc[i]][t];
    }
    rep(i,1,n)if(!vis[i]){
        v.clear();
        dfs(i);
        mst.clear();
        int sum=0;
        if(tm>=v.size()){
            repl(i,0,v.size())for(auto j:st[v[i]]){
                if(mst.find(j)==mst.end())++sum;
                mst.insert(j);
            }
            for(auto i:v){
                for(auto j:st2[plc[i]]){
                    if(mst.find(j)==mst.end())++sum;
                    mst.insert(j);
                }
                ans[i]=sum;
                for(auto j:st2[plc[i]]){
                    mst.erase(mst.lower_bound(j));
                    if(mst.find(j)==mst.end())--sum;
                }
            }
        }else{
            repl(i,0,tm)for(auto j:st[v[i]]){
                if(mst.find(j)==mst.end())++sum;
                mst.insert(j);
            }
            for(auto j:st2[plc[v[0]]]){
                if(mst.find(j)==mst.end())++sum;
                mst.insert(j);
            }
            ans[v[0]]=sum;
            for(auto j:st2[plc[v[0]]]){
                mst.erase(mst.lower_bound(j));
                if(mst.find(j)==mst.end())--sum;
            }
            repl(i,0,v.size()-1){
                int k=(i+tm)%v.size();
                for(auto j:st[v[k]]){
                    if(mst.find(j)==mst.end())++sum;
                    mst.insert(j);
                }
                for(auto j:st[v[i]]){
                    mst.erase(mst.lower_bound(j));
                    if(mst.find(j)==mst.end())--sum;
                }
                for(auto j:st2[plc[v[i+1]]]){
                    if(mst.find(j)==mst.end())++sum;
                    mst.insert(j);
                }
                ans[v[i+1]]=sum;
                for(auto j:st2[plc[v[i+1]]]){
                    mst.erase(mst.lower_bound(j));
                    if(mst.find(j)==mst.end())--sum;
                }
            }
        }
    }
    rep(i,1,n)put(ans[i]);
}