题解 P5592 【美德的讲坛】

_QAQ · 2019-10-14 23:15:48 · 题解

结合了最小割，贪心，甚至还有点模拟费用流的贪心思想(((

首先有最小割模型，将所有 (i,j)有 e_i \oplus e_j \geq k 的点对连边作最小割。

对应到 \operatorname{Trie} 上的 2 个节点 x,y，如何计算其子树内的点连边后得到的最小割。

注意到最小割即为网络流，若 k 当前位权值为 1，意味着 x_0 与 y_0 无法匹配，x_1 与 y_1 无法匹配。

否则，若当前位权值为 0，意味着 x_0 与 y_1 一定能完全匹配，x_1 与 y_0 一定能完全匹配。

若 |x_0|<|y_1|,|x_1|<|y_0|，则答案为 |x_0|+|x_1|

若 |y_0|<|x_1|,|y_1|<|x_0|，则答案为 |y_0|+|y_1|

否则，以 |x_0|<|y_1|,|x_1|>|y_0| 为例，答案显然为\min(\operatorname{merge(x_1,y_1)},|y_1|-|x_0|,|x_1|-|y_0|)+|x_0|+|y_0|

注意到修改时只会修改 \log n 个节点的权值，类似记搜防止递归计算，保证复杂度。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7,M=1e7+7; bool fl[M];
int n,q,tot,dep[M],siz[M],ans[M],ch[M][2];
long long k,w[N];
inline long long read(){
    long long num=0; char g=getchar(); while(g<48||57<g) g=getchar();
    while(47<g&&g<58) num=(num<<1)+(num<<3)+g-48,g=getchar(); return num;
}
inline void write(int u){
    if(u>9) write(u/10); putchar(u%10+'0');
}
inline void ins(int u,long long k){
    siz[u]++,fl[u]=0; if(dep[u]<0) return;
    if(k&(1ll<<dep[u])){
        if(!ch[u][1]) ch[u][1]=++tot,dep[tot]=dep[u]-1; ins(ch[u][1],k);
    }
    else{
        if(!ch[u][0]) ch[u][0]=++tot,dep[tot]=dep[u]-1; ins(ch[u][0],k);
    }
}
inline void del(int u,long long k){
    siz[u]--,fl[u]=0; if(dep[u]<0) return;
    if(k&(1ll<<dep[u])) del(ch[u][1],k); else del(ch[u][0],k);
}
inline int getans(int u,int v){
    if(!siz[u]||!siz[v]) return 0;

    if(dep[u]<0){
        if(u==v) return ans[u]=siz[u]-(siz[u]&1); return ans[u]=min(siz[u],siz[v]);
    }
    if(fl[u]&&fl[v]) return ans[u]; fl[u]=1,fl[v]=1;
    if(k&(1ll<<dep[u])){
        if(u==v) ans[u]=ans[v]=getans(ch[u][0],ch[v][1]);
        else ans[u]=ans[v]=getans(ch[u][0],ch[v][1])+getans(ch[u][1],ch[v][0]);
        return ans[u];
    }
    else{
        int fq=getans(ch[u][0],ch[v][0]),fw=getans(ch[u][1],ch[v][1]);
        if(u==v) ans[u]=fq+fw+min(siz[ch[u][0]]-fq,siz[ch[v][1]]-fw);
        else if(siz[ch[u][0]]<=siz[ch[v][1]]&&siz[ch[u][1]]<=siz[ch[v][0]]) ans[u]=siz[ch[u][0]]+siz[ch[u][1]];
        else if(siz[ch[u][0]]>=siz[ch[v][1]]&&siz[ch[u][1]]>=siz[ch[v][0]]) ans[u]=siz[ch[v][0]]+siz[ch[v][1]];
        else if(siz[ch[u][0]]<=siz[ch[v][1]]&&siz[ch[u][1]]>=siz[ch[v][0]]){
            fw=min(min(fw,siz[ch[v][1]]-siz[ch[u][0]]),siz[ch[u][1]]-siz[ch[v][0]]);
            ans[u]=fw+siz[ch[u][0]]+siz[ch[v][0]];
        }
        else{
            fq=min(min(fq,siz[ch[v][0]]-siz[ch[u][1]]),siz[ch[u][0]]-siz[ch[v][1]]);
            ans[u]=fq+siz[ch[u][1]]+siz[ch[v][1]];
        }
        ans[v]=ans[u]; return ans[u];
    }
}
int main(){
    n=read(),q=read(),k=read(),dep[1]=60,tot=1; int c;
    for(int i=1;i<=n;i++) w[i]=read(),ins(1,w[i]);
    write(max(n-getans(1,1),1)),putchar('\n');
    for(int i=1;i<=q;i++)
        c=read(),del(1,w[c]),w[c]=read(),ins(1,w[c]),write(max(n-getans(1,1),1)),putchar('\n');
    return 0;
}