题解：P12758 [POI 2017 R3] 奇偶路口 Crossroads of parity

· · 题解

算法1

k=1,q=0

现在只需要查询原图最小答案。

由于边权是 2^i，这告诉我们是按照编号字典序来排序。

考虑一条大边能不能被小边路径替代，如果能替代，是不是等价于翻转小边路径状态。

这个小边比大边先加入的结构感觉像什么？最小生成树。

不过我们现在只需要考虑最小的答案，那也只需要考虑最小生成树上的边。

考虑树上怎么判断一条边是否被选，想到说如果一个叶子 v 有 p_v=1，那它向它父亲 u 的边 (v,u) 一定会被选，同时反转 p_u，那向上递归可以发现一条从儿子 x 向父亲 y 的边被选当且仅当 x 的子树异或和为 1。无解情况简单，即为整个子树异或和为 1。

那我只需要跑一颗最小生成树然后去深搜一遍即可。

现在你会了 32\text{pts}。

算法2

q=0

第 k 小，发现还有非树边没有用，考虑非树边加入会怎么样，是不是翻转了非树边两端的 p。

所以一种选非树边的方式唯一对应一种选全边方法，而每一个非树边显然只会覆盖比他小的树边，也就是不会影响编号比它大的树边，那现在选择的非树边的字典序排名就正好是答案字典序排名。

那非树边的字典序显然就是 k-1 的二进制分解，我把那 \log{k} 条边的 p 翻转做算法 1 即可。

现在你会了 57\text{pts}。

算法3

你都想到这了，接下来的数据结构优化就理所当然。

我们现在等价于要支持动态单点修，动态查子树异或和，不难想到用树状数组和 dfn 序来优化它。

复杂度 O(q\log k\log n)，实现精细足以通过。

现在你会了 100\text{pts}。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
struct BIT{
    int t[N];
    inline int lowbit(int x){
        return x&(-x);
    }
    inline void add(int x){
        for(int i=x;i<N;i+=lowbit(i))t[i]^=1;
    }
    inline int ask(int x){
        int ret=0;
        for(int i=x;i;i-=lowbit(i))ret^=t[i];
        return ret;
    }
    inline int query(int l,int r){
        return ask(r)^ask(l-1);
    }
}T;
struct edge{
    int x,y,id;
}E[N],E2[N];
int ec=0,tr=0,ip[N];
int fa[N];
int par[N];
int n,m,q,k,oj[N];
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
vector<int>mp[N];
int dep[N],siz[N],dfn[N],tot;
int xr=0;
inline bool valid(int K){
    if(ec>=60)return true;
    return K<(1ll<<ec);
}
inline void flip(int K){
    int lim=min(ec,60ll);
    for(int i=1;i<=lim;i++){
        if((K>>(i-1))&1){
            T.add(dfn[E2[i].x]);
            T.add(dfn[E2[i].y]);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        E[i]={x,y,i};
        if(find(x)==find(y)){
            E2[++ec]={x,y,i};
            ip[i]=-ec;
            continue;
        }
        ip[i]=++tr;
        fa[find(x)]=find(y);
        mp[x].push_back(y);
        mp[y].push_back(x);
    }
    vector<int>order;
    stack<int>st;
    st.push(1);
    par[1]=0;
    dep[1]=1;
    while(!st.empty()){
        int u=st.top();st.pop();
        dfn[u]=++tot;
        order.push_back(u);
        for(int v:mp[u]){
            if(v==par[u])continue;
            par[v]=u;
            dep[v]=dep[u]+1;
            st.push(v);
        }
    }
    for(int i=1;i<=n;i++)siz[i]=1;
    for(int i=(int)order.size()-1;i>=0;i--){
        int u=order[i];
        if(par[u])siz[par[u]]+=siz[u];
    }
    for(int i=1;i<=n;i++){
        cin>>oj[i];
        xr^=oj[i];
        if(oj[i])T.add(dfn[i]);
    }
    cin>>k;
    k--;
    if(valid(k))flip(k);
    for(int i=1;i<=m;i++){
        if(ip[i]>0){
            int son=dep[E[i].x]>dep[E[i].y]?E[i].x:E[i].y;
            cout<<T.query(dfn[son],dfn[son]+siz[son]-1)<<' ';
        }
        else{
            int idx=-ip[i];
            int val=0;
            if(idx<=60&&((k>>(idx-1))&1))val=1;
            cout<<val<<' ';
        }
    }
    cout<<'\n';
    cin>>q;
    for(int Case=1;Case<=q;Case++){
        char op;cin>>op;
        if(op=='M'){
            int x;cin>>x;
            xr^=1;
            T.add(dfn[x]);
        }
        else if(op=='K'){
            if(valid(k))flip(k);
            cin>>k;
            k--;
            if(valid(k))flip(k);
        }
        else{
            int i;cin>>i;
            if(xr||!valid(k)){
                cout<<-1<<'\n';
                continue;
            }
            if(ip[i]>0){
                int son=dep[E[i].x]>dep[E[i].y]?E[i].x:E[i].y;
                cout<<T.query(dfn[son],dfn[son]+siz[son]-1)<<'\n';
            }
            else{
                int idx=-ip[i];
                int val=0;
                if(idx<=60&&((k>>(idx-1))&1))val=1;
                cout<<val<<'\n';
            }
        }
    }
    return 0;
}