洛谷P5592 美德的讲坛

对于 \(x\)，存在 \(p\)，满足 \(2^p \leqslant x < 2^{p+1}\)，对于所有 \(a_i\) 按 \(\left\lfloor \frac{a_i}{2^p} \right\rfloor\) 的值分组，得每组内的两两异或值都 \(<x\)。

然后就只需考虑组与组之间的情况了，将其转化为最小割，源点向第一个组的每个点连容量为 \(1\) 的边，第二组的每个点向汇点连容量为 \(1\) 的边，两组间异或和 \(\geqslant x\) 的点对连容量为 \(\infty\) 的边。

直接跑最小割复杂度无法接受，先将最小割转为最大流，对所有权值建立 \(01\ Trie\)。

设 \(a_0\) 和 \(a_1\) 为 \(a\) 的左右子树，\(solve(a,b)\) 为以 \(a,b\) 为根的子树的最大匹配，得：

当 \(x\) 在对应深度为 \(1\) 时，得其值为 \(solve(a_0,b_1)+solve(a_1,b_0)\)。

当 \(x\) 在对应深度为 \(0\) 时，进行分类讨论：

还需注意 \(a=b\) 的情况，设 \(v_0=solve(a_0,a_0),v_1=solve(a_1,a_1)\)，其值为 \(v_0+v_1+\min(|a_0|-v_0,|a_1|-v_1)\)。

因为每次修改的节点个数为 \(O(\log n)\)，所以每次询问记忆化即可。

#include<bits/stdc++.h>
#define maxn 100010
#define maxm 10000010
#define s(x,k) siz[ch[x][k]]
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
    x=0;char c=getchar();bool flag=false;
    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    if(flag)x=-x;
}
int n,q,tot=1,root=1;
ll lim;
int ch[maxm][3],siz[maxm],val[maxm],dep[maxm];
ll a[maxn];
bool vis[maxm];
void insert(ll x,int v)
{
    int p=root;
    siz[p]+=v,dep[p]=60;
    for(int i=60;i>=0;--i)
    {
        int c=(x>>i)&1;
        vis[p]=false;
        if(!ch[p][c]) ch[p][c]=++tot;
        siz[p=ch[p][c]]+=v,dep[p]=i-1;
    }
}
int solve(int x,int y)
{
    if(!siz[x]||!siz[y]) return 0;
    if(vis[x]&&vis[y]) return val[x];
    vis[x]=vis[y]=true;
    if(dep[x]==-1) return val[x]=min(siz[x],siz[y]);
    if((lim>>dep[x])&1) return val[x]=solve(ch[x][0],ch[y][1])+solve(ch[x][1],ch[y][0]);
    int v0=solve(ch[x][0],ch[y][0]),v1=solve(ch[x][1],ch[y][1]);
    if(x==y) return val[x]=v0+v1+min(s(x,0)-v0,s(x,1)-v1);
    if(s(x,0)<=s(y,1)&&s(x,1)<=s(y,0)) return val[x]=siz[x];
    if(s(x,0)>=s(y,1)&&s(x,1)>=s(y,0)) return val[x]=siz[y];
    if(s(x,0)>=s(y,1)&&s(x,1)<=s(y,0))
        return val[x]=min(v0,min(s(y,0)-s(x,1),s(x,0)-s(y,1)))+s(x,1)+s(y,1);
    if(s(x,0)<=s(y,1)&&s(x,1)>=s(y,0))
        return val[x]=min(v1,min(s(y,1)-s(x,0),s(x,1)-s(y,0)))+s(x,0)+s(y,0);
}
int main()
{
    read(n),read(q),read(lim);
    for(int i=1;i<=n;++i) read(a[i]),insert(a[i],1);
    printf("%d\n",max(n-solve(root,root),1));
    while(q--)
    {
        int x;
        read(x),insert(a[x],-1);
        read(a[x]),insert(a[x],1);
        printf("%d\n",max(n-solve(root,root),1));
    }   
    return 0;
}