P5105 不强制在线的动态快速排序 题解

· · 题解

给一发有证明过程的题解：

考虑 S=[1,n] 的情况。

结论：

0 &n\equiv 0 \pmod 4\\ 2n-1 &n\equiv 1 \pmod 4\\ 2 &n\equiv 2 \pmod 4\\ 2n+1 &n\equiv 3 \pmod 4 \end{cases}

证明：

设 f(x,y) 为区间 [x,y] 中所有奇数的异或和。

Sort(S)&=\bigoplus\limits_{i=1}^n(a_i^2-a_{i-1}^2)\\ &=\bigoplus\limits_{i=1}^n(i^2-(i-1)^2)\\ &=\bigoplus\limits_{i=1}^n(2i+1)\\ &=f(1,2n-1) \end{aligned}

考虑 把每个数写成二进制形式 ，小的在上，大的在下，排在一块。从右至左，以 0 开始，依次给位数编号。

因为对于 k\geq 1 ，f(2^k,2^{k+1}-1) 中有偶数个奇数，这些奇数的异或和中，最高位 k 经过了偶数次异或，被消去，原式的值取决于 [0,k-1] 位的异或和，所以有

f(2^k,2^{k+1}-1)=f(1,2^k-1)

从而

f(1,2^{k+1}-1)&=f(1,2^k-1)\oplus f(2^k,2^{k+1}-1)\\ &=f(1,2^k-1)\oplus f(1,2^k-1)\\ &=0 \end{aligned}

再来看 Sort(S)=f(1,2n-1) ，令 k 为满足 2^k \leq 2n-1 的最大整数，此时我们发现

f(1,2n-1)&=f(1,2^k-1) \oplus f(2^k,2n-1)\\ &=0 \oplus f(2^k,2n-1)\\ &= f(2^k,2n-1) \end{aligned}

运用和上文同样的思想，

“对于 k\geq 1 ，f(2^k,2^{k+1}-1) 中有偶数个奇数，这些奇数的异或和中，最高位 k 经过了偶数次异或，被消去。”

我们分类讨论：

当 n 为偶数时， f(2^k,2n-1) 中有偶数个奇数。同理，最高位 k 被消去。接下来求解 (1,2n-1-2^{k-1}) ，而它又等于 (2^{k-1},2n-1-2^{k-1}) , k-1 位又会被消去……如此循环，最后在 k=1 时，此性质不再能推导出 k=0 的情况，最后得到了偶数个值为 01 或 11 的二进制数。这些数求异或和，四个数成一组消去。所以当 n 为偶数时，若 n\equiv 0 \pmod 4 ，那么所有数都被消去，总结果为 0 ；若 n\equiv 2 \pmod 4 ，那么还剩下一个 01 和一个 11 ，异或起来是 2 ，总结果也就是 2 。

当 n 为奇数时， f(2^k,2n-1) 中有奇数个奇数，不管 2n-1 在当前位上是 0 还是 1 ，除了它之外的奇数都有偶数个，都会全部消去， 当前位有且仅有 2n-1 这个项的贡献 。依然循环求解 f(2^{k-1},2n-1-2^{k-1}) ，直到 k=1 时，讨论:若 n\equiv 1 \pmod 4 ，那么又只剩下 2n-1 它自己项的贡献，总结果自然就是 2n-1 ;若 n\equiv 3 \pmod 4 ,那么还会剩下两个 01 和一个 11 ，它们异或和是 11 ，是 2n-1 此时的贡献 01 再加了 2 ，而之前所有位的结果都等于 2n-1 在该位上的贡献，所以总结果就是 2n-1 再加 2 ，即 2n+1 。

综上，

0 &n\equiv 0 \pmod 4\\ 2n-1 &n\equiv 1 \pmod 4\\ 2 &n\equiv 2 \pmod 4\\ 2n+1 &n\equiv 3 \pmod 4 \end{cases}

证毕。

进一步地，对于询问 f(l,r) ，都有 f(l,r)=f(1,r)\oplus f(1,l) 。注意不是 f(1,l-1) ，因为要删除 l 和 l-1 之间的贡献 l^2-(l-1)^2 。

然后用线段树维护，把每一次区间修改下放到若干节点中，每个节点都是满的，解决了不连续的问题。再采用动态开点，解决了定义域过大的问题。

最后附上代码：

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define ls (tr[tr[u].l])
#define rs (tr[tr[u].r])
using namespace std;
const int N=3e5+5,INF=1e9;////1e9
typedef long long ll;
struct queryer{
    int l,r,type;
}qry[N];
struct treer{
    int l,r,min,max;
    ll val;
    bool vis;
}tr[35*N];
int q,cnt,rt;

ll calc(int p){
    if(p%4==0) return 0;
    if(p%4==1) return 2*p-1;
    if(p%4==2) return 2;
    else return 2*p+1;
}

void pushup(int u,int l,int r){
    if(!tr[u].l)
        return (void)(tr[u].val=rs.val,tr[u].min=rs.min,tr[u].max=rs.max);
    if(!tr[u].r)
        return (void)(tr[u].val=ls.val,tr[u].min=ls.min,tr[u].max=ls.max);
    tr[u].val=ls.val^rs.val^((ll)rs.min*rs.min-(ll)ls.max*ls.max);
    tr[u].min=ls.min,tr[u].max=rs.max;
}

void update(int &u,int l,int r,int st,int ed){
    if(l>ed || r<st || tr[u].vis) return;
    if(!u) u=++cnt;
    if(l>=st && r<=ed)  return (void)(tr[u]=(treer){0,0,l,r,calc(r)^calc(l),1});
    update(tr[u].l,l,mid,st,ed),update(tr[u].r,mid+1,r,st,ed);
    pushup(u,l,r);
}

int main(){
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d",&qry[i].type);
        if(qry[i].type==2) continue;
        scanf("%d%d",&qry[i].l,&qry[i].r);
    }
    for(int i=1;i<=q;i++){
        if(qry[i].type==2) printf("%lld\n",tr[rt].val);
        else update(rt,1,INF,qry[i].l,qry[i].r);
    }
    return 0;
}

ps:这题差点被你谷管理员CYJian从黑题改成蓝题，原因是太简单