题解：P11278 绝世丑角

· · 题解

普及选手爆切黑题，没打这场后悔了。

首先我们看到 a_i \gets a_i \otimes a_i，不用想，这种不是有势能就是有规律。

简单打表后就会发现，这东西是带循环的，对于任何一个数它都有 32 位的循环（从值域 2^{32} 中也可以猜到）。

但是即便如此，我们对它暴力预处理仍然不行，达到了 O(n^2 \log n)。

用我们惊人的注意力可以注意到一个对于 f(x)=x \otimes x,a=x&-x。

有：f(x)=f(a) \oplus f(x \oplus a)。

于是我们提前做出所有的 f(2^x)，然后就可以 O(\log n) 求出 f(n) 了。

具体的，对于求 f(2^x) 其实很简单，由 Nim 积的性质：

x \otimes 2^{2^y}=2^{2^y} \times x，2^{2^z} \otimes 2^{2^z}= 3 \times 2^{2^z-1}

注意 2^{2^y}>x，可以得到：

若 k 是最小的满足 2t>x 并且 2t>y 的整数，其中 t=2^{2^k}。

则令 x=a \times t+b,y=c \times t+d，得到：

x \otimes y=(b \oplus a \otimes t) \otimes (d \oplus c \otimes t)

再由 Nim 积所满足的交换律加上上面给出的性质得：

x \otimes y=(b \otimes d) \oplus [ (a \oplus b) \otimes (c \oplus d) \oplus (b \otimes d)] \times t \oplus (\frac{t}{2} \otimes a \otimes c)

可以用类似分治的方法递归求出，对于一次计算，复杂度是 O(\log x \times \log y)。

这样的话，就容易预处理了。

预处理代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int nim(int x,int y,int p) 
{
    if(x*y<=min(x,y))return x*y;
    int a=x>>p,b=((1ll<<p)-1)&x,c=y>>p,d=((1ll<<p)-1)&y,res=nim(b,d,p>>1);
    return ((nim(a^b,c^d,p>>1)^res)<<p)^nim(nim(a,c,p>>1),(1ll<<p)>>1,p>>1)^res;
}
int p[35];
signed main()
{
    for(int i=1,x=1;i<=32;i++,x<<=1)cout<<(p[i]=nim(x,x,32))<<'\n';
    return 0;
}

复杂度是 O(\log^3n) 的。

只有 32 个数，我们直接把结果粘在代码里就行。

操作 2,3 基本等价，用线段树维护一下对于不同操作次数的值就可以了，只是基本操作。

虽然只用了 1 个，但还是要感谢出题人的 7 个样例。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 250005
using namespace std;
int p[35]={1,3,6,13,24,52,103,222,384,832,1648,3552,6237,13563,26511,56906,98304,212992,421888,909312,1596672,3472128,6786816,14567936,25190110,54589881,108036850,232800673,408783316,888883132,1737454078,3729449897};
int n,q,a[N];
inline int f(int x)
{
    int res=0;
    for(int i=0;i<=31;x>>=1,i++)res^=(p[i]*(x&1));
    return res;
}
struct node
{
    int tr[2][32],lazy;
    inline void init(int x)
    {
        tr[0][0]=tr[1][0]=x;
        for(int i=1;i<=31;i++)tr[0][i]=tr[1][i]=f(tr[0][i-1]);
    }
}tr[N<<2],tmp;
inline void pushup(int id)
{
    for(int i=0;i<=31;i++)
    {
        tr[id].tr[0][i]=tr[id<<1].tr[0][i]+tr[id<<1|1].tr[0][i];
        tr[id].tr[1][i]=tr[id<<1].tr[1][i]^tr[id<<1|1].tr[1][i];
    }
}
inline void add(int id,int t)
{
    tmp=tr[id],tr[id].lazy+=t;
    for(int i=0;i<=31;i++)
    {
        tr[id].tr[0][i]=tmp.tr[0][(i+t)%32];
        tr[id].tr[1][i]=tmp.tr[1][(i+t)%32];
    }
}
inline void pushdown(int id)
{
    if(tr[id].lazy)add(id<<1,tr[id].lazy),add(id<<1|1,tr[id].lazy),tr[id].lazy=0;
}
void build(int id,int l,int r)
{
    if(l==r)
    {
        tr[id].lazy=0,tr[id].init(a[l]);
        return;
    }
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
void update(int id,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)
    {
        add(id,1);
        return;
    }
    int mid=l+r>>1;pushdown(id);
    if(x<=mid)update(id<<1,l,mid,x,y);
    if(mid<y)update(id<<1|1,mid+1,r,x,y);
    pushup(id);
}
int query0(int id,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return tr[id].tr[1][0];
    int mid=l+r>>1,res=0;pushdown(id);
    if(x<=mid)res^=query0(id<<1,l,mid,x,y);
    if(mid<y)res^=query0(id<<1|1,mid+1,r,x,y);
    return res;
}
int query1(int id,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return tr[id].tr[0][0];
    pushdown(id);
    int mid=l+r>>1,res=0;
    if(x<=mid)res+=query1(id<<1,l,mid,x,y);
    if(mid<y)res+=query1(id<<1|1,mid+1,r,x,y);
    return res;
}
signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(q--)
    {
        int op,l,r;cin>>op>>l>>r;
        if(op==1)update(1,1,n,l,r);
        if(op==2)cout<<query0(1,1,n,l,r)<<"\n";
        if(op==3)cout<<query1(1,1,n,l,r)<<"\n";
    }
    return 0;
}

复杂度 O(n \log^2 n+q \log^2 n)，完全不卡常，没有读写优化代码所有的点都在 1 秒内。