题解 |牛客11254I 栗山未来和异或

之前学了下dls的题解，二维差分的思路看懂了，但是各种细节好麻烦啊orz，写了半个下午写不出来，然后去看别人怎么写的
看了看逆十字巨佬们的代码，似乎简洁且明了……
于是学习了一下，这题续了一个下午，难受

先考虑一个子问题：给定起点和，要求给分别异或上
这个可以通过先打好标记，然后从高往低分裂标记，并且进行异或差分解决，具体而言，就是先打个标记记作，表示一下从开始异或上这么一个，那么全部标记打完之后就可以从高到低遍历把这个标记取掉，每次取掉就相当于给数组这段打上区间异或（可以通过差分解决），然后把这个标记分裂成,，单次复杂度是，所以边打边推肯定不现实，肯定是全部打好一起推。

标记怎么推讲清楚了，看看之后怎么做，假设目前起点是，要加的值是，并且的最低位是，那么这一段上的其实可以转换成，那么其实可以拆开，先在这段区间上异或上x，然后在中间再依次异或上，那么就是上面的子问题了，只要区间打好标记，就完事了。

然后这个区间解决了，下一个区间是起点是，要加的值是。这个问题显然和上面是一样的，于是同样做法一直做到，再反过来填充空隙，就能把标记都打上了，最后按上面说的从高到低开始推标记就完事了

代码（就是逆十字的，侵删）：

#include<bits/stdc++.h>
using namespace std;

int n,q;
int a[600010],tg[600010];
bool b[600010][22];

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    while(q--)
    {
        int kd,l,r,x;
        scanf("%d%d%d%d",&kd,&l,&r,&x);
        if(!kd)
        {
            tg[l]^=x,tg[r+1]^=x;
        }
        else
        {
            for(int i=0;i<=19;i++)
            {
                if(x&(1<<i)&&(l+(1<<i)-1)<=r)
                {
                    b[l][i]^=1;
                    tg[l]^=(x>>i)<<i;
                    tg[l+(1<<i)]^=(x>>i)<<i;
                    l+=(1<<i);
                    x+=(1<<i);
                }
            }
            for(int i=19;i>=0;i--)
            {
                if((l+(1<<i)-1)<=r)
                {
                    b[l][i]^=1;
                    tg[l]^=(x>>i)<<i;
                    tg[l+(1<<i)]^=(x>>i)<<i;
                    l+=(1<<i);
                    x+=(1<<i);
                }
            }
        }
    }
    for(int i=19;i>=1;i--)
    {
        for(int j=1;j<=n;j++)
        {
            if(!b[j][i]) continue;
            b[j][i-1]^=1;
            if(j+(1<<(i-1))<=n)
            {
                b[j+(1<<(i-1))][i-1]^=1;
                tg[j+(1<<(i-1))]^=(1<<(i-1));
                if(j+(1<<i)<=n)
                {
                    tg[j+(1<<i)]^=(1<<(i-1));
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        tg[i]^=tg[i-1];
        printf("%d ",a[i]^tg[i]);
    }
}