【题解】异或粽子&加强版

题目链接

不愧是大常数选手，无论原题还是加强都要开 O2 才能过去 TAT

Statement

给定一个长度为 (n) 的序列，求前 (k) 大的区间异或和。 (1leq nleq 5e5,1leq kleq min(frac{n(n-1)}{2}，2e5),0leq a_i<2^{32})

Solution

虽然是十二省联考，但是题不难，也不是很毒瘤。

考虑区间异或和显然可以转化成两个前缀和的异或，那么现在的问题就变成了求前 (k) 大的异或对。由于这里是有序对，我们可以在开头把 (k imes 2) ，最后再让 (ans/=2) ，这样就可以直接统计无序点对了。

题目中有 (a_i<2^{32}) 的限制，容易想到用 Trie 来处理二进制数位。

首先，对于每个右端点，将使异或和取到最大值的左端点位置+异或和放进堆里。

然后，每次显然是取堆顶的一对。考虑如何在取出之后放入该右端点的次大值。一个显然的想法是把之前的删除，但是这样时空和实现都很麻烦。

考虑一个更简单的做法：其实 Trie 上不一定只能查询最值！我们也可以在 Trie 上用类似平衡树查询第 (p) 大的思想来找特定串的第 (k) 大异或和。

具体做法：在向 Trie 中插入的时候顺便统计子树大小。

对于一个原串在 Trie 上走到了 (g[pos][ch]) 的点，找最大值的时候是往 (g[pos][choplus 1]) 走，由于是从高位到低位，所以节点 (g[pos][choplus 1]) 子树中的任何串，和原串的异或和都比 (g[pos][ch]) 中的串要大。

那么如果当前要求第 (p) 大的异或和，而 (siz[g[pos][choplus 1]]<p) ，显然答案应该在 (g[pos][ch]) 中，那么 (pos-=siz[g[pos][choplus 1]]) ，然后向 (g[pos][ch]) 走；

否则加上当前位的贡献 (|=1<<i) ，向 (g[pos][choplus 1]) 走。代码如下：

 if ( siz[g[pos][ch^1]]<p ) p-=siz[g[pos][ch^1]],pos=g[pos][ch];
else res|=1ll<<i,pos=g[pos][ch^1];

这样就只需要记录所有右端点当前用到了第几大 (rk[i]) ，在弹出一个右端点的时候 (rk[i]++) ，并查询对应 (rk[i]) 的异或和，插回堆里面即可。

Code

//Author:RingweEH
const int N=500010,M=N*35;
struct Node
{
    int pos; ll val;
    Node ( int _pos=0,ll _val=0 ) : pos(_pos),val(_val) {}
    bool operator < ( const Node &tmp ) const { return val<tmp.val; }
};
priority_queue<Node> q;
int n,k,tot,rk[N],g[M][2],siz[M];
ll ans,a[N],b[N];
 
void Insert( ll x )
{
    int pos=0;
    for ( int i=33; ~i; i-- )
    {
        int ch=(x>>i)&1;
        if ( !g[pos][ch] ) g[pos][ch]=++tot;
        pos=g[pos][ch]; siz[pos]++;
    }
}
 
ll Query( ll x,int p )
{
    int pos=0; ll res=0;
    for ( int i=33; ~i; i-- )
    {
        int ch=(x>>i)&1;
        if ( siz[g[pos][ch^1]]<p ) p-=siz[g[pos][ch^1]],pos=g[pos][ch];
        else res|=1ll<<i,pos=g[pos][ch^1];
    }
    return res;
}
 
int main()
{
    n=read(); k=read(); k<<=1;
    Insert( 0 );
    b[0]=0;
    for ( int i=1; i<=n; i++ )
    {
        a[i]=read(); b[i]=b[i-1]^a[i];
        Insert( b[i] );
    }

    for ( int i=0; i<=n; i++ )
    {
        ll tmp=Query(b[i],rk[i]=1);
        q.push( Node(i,tmp) );
    }
    ll ans=0;
    while ( k-- )
    {
        ans+=q.top().val;  int p=q.top().pos; q.pop();
        ll tmp=Query(b[p],++rk[p]);
        q.push( Node(p,tmp) );
    }
 
    printf( "%lld
",ans>>1 );
 
    return 0;
}

加强版

Orz Apocrypha 为什么它也出现在了我们的模拟赛里

范围：(nleq 7.5*10^5,kleq frac{n*(n+1)}{2},a_i<2^{32}) . 于是需要一个 (Omicron(nlog n)) 的优秀做法。

Solution

同样做一遍异或前缀和，记为 (b) ，将题目转化为点对异或。有序对和无序对的处理同上。

考虑到 (K) 很大，显然不能枚举，那么可以枚举每一位计算贡献。大致思路就是，找出异或值第 (K) 大的数，然后求所有大于这个数的异或值之和。在 Trie 上找第 (K) 大的思路同上，但是中间要多统计一些东西：

同原题一样，首先我们要记录一个 (siz) 表示 Trie 树上节点的子树大小（注意是有效的结束节点个数），统计方法同上。

设当前节点为 (pos) ，当前这一位的值是 (ch) ，那么只有在 (g[pos][choplus 1]) 这个节点的子树中的 (b) 才能在这一位上产生贡献。

如果出现 (siz[g[pos][choplus 1]]<K) ，即上文需要减去 (siz) 的情况，再在 (g[pos][choplus 1]) 处打一个 (b[i]) 的标记，表示子树中所有的 (b[j]oplus b[i]) 都会对答案产生贡献，记录 (ans[bit]+=siz[g[pos][choplus 1]]) ，表示二进制下这一位上 (1) 的个数。

否则，(ans[bit]+=K) 。

这样做完之后，再 DFS 一遍，处理每个标记，然后加入答案的贡献即可，或者直接顺带统计也行。但是在统计答案的时候，处理标记仍然需要拆位，复杂度 (Omicron(nlog ^2n)) ，还需要优化。

考虑打标记是什么形式。能够在某个点上打上标记的数的集合一定都在某一棵子树里面，那么标记就转化成了两棵子树中所有 (b[i]) 的两两异或和。仍然拆位维护，统计子树中某一位上 (1) 的个数，在插入之前将 (b) 排序，这样每个子树就对应一段区间，比较好处理。

复杂度之所以是 (nlog) 的，是因为标记个数不超过 (Omicron(n)) 个。标记只会在三度点上出现。因此，一个节点 (x) 至多只会和另外一个点打标记。那么就不需要去重。

Code

小范围（但是保证时间复杂度与 (K) 无关）的提交地址：CF241B

这里是正经大范围的代码：数据自己造XD

我要杀了出题人！不知道为什么我的程序在所有数相同的时候会 WA ，然后特判了还是过不去，结果发现就算是这样的部分分也要开 Int128 ！骗个分容易吗。

//Author:RingweEH
#define Int128 __int128
const int N=750010,M=32;
int n,tot=1,g[N*M][2],siz[N*M],bit[N][M],nw[N];
ll lim,a[N],m,cnt;
Int128 sum;
 
void Insert( int x )
{
    int pos=1;
    for ( int i=31; ~i; i-- )
    {
        int ch=x>>i&1;
        if ( !g[pos][ch] ) g[pos][ch]=++tot;
        pos=g[pos][ch]; siz[pos]++;
    }
}
 
void GetLim()
{
    ll las=m;
    for ( int i=1; i<=n; i++ )
        nw[i]=1;
    for ( int i=31; ~i; i-- )
    {
        ll tmp=0;
        for ( int j=1; j<=n; j++ )
        {
            int ch=a[j]>>i&1;
            tmp+=siz[g[nw[j]][ch^1]];
        }
        if ( tmp>=las ) lim|=(1ll<<i);
        else las-=tmp;
        for ( int j=1; j<=n; j++ )
        {
            int ch=(a[j]^lim)>>i&1;
            nw[j]=g[nw[j]][ch];
        }
    }
}
 
void GetSum()
{
    for ( int i=31; ~i; i-- )
    {
        if ( lim>>i&1 ) continue;
        ll now=((lim>>i)<<i)|(1ll<<i);
        for ( int j=1; j<=n; j++ )
        {
            ll l=((a[j]^now)>>i)<<i,r=l|((1ll<<i)-1);
            l=lower_bound( a+1,a+1+n,l )-a;
            r=upper_bound( a+1,a+1+n,r )-a;
            sum+=now*(r-l);
            cnt+=r-l;
            if ( l<=j && j<r ) cnt--;
            for ( int k=i-1; ~k; k-- )
            {
                int tmp=bit[l][k]-bit[r][k];
                if ( (a[j]>>k)&1 ) tmp=r-l-tmp;
                sum+=(1ll<<k)*tmp;
            }
        }
    }
}
 
 
void print( Int128 x)
{
    if ( !x ) return;
    print(x/10);
    putchar( (char)(x%10+'0') );
}
 
void Same()
{
    int cnt=0; ll num=0;
    for ( int i=1; i<=n; i++ )
        if ( a[i]==0 ) num+=(i-1)-cnt,cnt++;
        else num+=cnt;
    m>>=1;
    Int128 res=a[2],mul=min( m,num );
    print( res*mul );
}
 
int main()
{
    n=read()+1; m=read()<<1;  a[1]=0;
    bool fl=1; ll a1;
    for ( int i=2; i<=n; i++ )
    {
        ll x=read(); a[i]=x^a[i-1];
        if ( i==2 ) a1=x;
        else fl&=(a1==x);
    }
 
    if ( fl ) { Same(); return 0; }
 
    sort( a+1,a+1+n );
    for ( int i=n; i; i-- )
    {
        Insert( a[i] );
        for ( int j=0; j<32; j++ )
            bit[i][j]=bit[i+1][j]+((a[i]>>j)&1);
    }
 
    GetLim(); GetSum();
    sum>>=1; cnt>>=1; m>>=1;
    Int128 ans=(sum+(m-cnt)*lim);
 
    print( ans );
 
    return 0;
}