题目概述

Kuriyama Mirai and Exclusive Or

解题报告

第一种操作没什么好讲的，我们关注第二种。这种加法和异或混合的一般都只能考虑按位统计贡献。

考虑 $[L,R]$ 第 $i$ 位的 $01$ 情况，不难发现周期是 $2^{i+1}$ ，每个周期由最多三段连续 $01$ 构成，并且 $01$ 个数各为 $2^i$ 。

比如从 $3$ 开始，第 $2$ 位的 $01$ 序列为011110000111100001111000...，周期为01111000。

有了周期自然想到取模，因此根据 $2^{i+1}$ 分 $\lceil{n\over 2^{i+1}}\rceil$ 块，每一块中有 $2^{i+1}$ 个元素表示在这块中的位置。

可以将这些块视为矩阵，由于 $1$ 在一个周期中是连续的一段或两段，因此可以看作矩阵覆盖，而矩阵覆盖可以用差分解决。

每次操作可以转化为若干次矩阵覆盖，最后求出差分数组就可以知道每个位置在第 $i$ 位上是否有贡献。

很需要注意边界处理。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=600000,LOG=30;

int n,m,a[maxn+5],sum[maxn+5];bool c[LOG+5][maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
#define ID(d,x,y) ((x)<<(d)+1|(y))
void Add(int i,int L,int R,int x,int y){
    if (y>=n) y=n-1;if (x>y) return;
    if (ID(i,L,x)<n) c[i][ID(i,L,x)]^=1;
    if (ID(i,L,y+1)<n && y<(1<<i+1)-1) c[i][ID(i,L,y+1)]^=1;
    if (ID(i,R+1,x)<n && R<(n-1>>i+1)) c[i][ID(i,R+1,x)]^=1;
    if (ID(i,R+1,y+1)<n && y<(1<<i+1)-1 && R<(n-1>>i+1)) c[i][ID(i,R+1,y+1)]^=1;
}
void Solve(int L,int R,int x){
    for (int i=0;i<30;i++){
        int S=x+((L+(1<<i+1)-1>>i+1)<<i+1)-L;
        int A,B,C,D;
        if (S>>i&1){
            A=0;B=(1<<i)-(S&((1<<i)-1))-1;
            C=B+(1<<i)+1;D=(1<<i+1)-1;
        } else {
            A=(1<<i)-(S&((1<<i)-1));B=A+(1<<i)-1;
            C=(1<<i+1);D=(1<<i+1)-1;
        }
        int l=L>>i+1,r=R>>i+1,a=L&((1<<i+1)-1),b=R&((1<<i+1)-1);
        if (l==r){
            Add(i,l,r,max(A,a),min(B,b));
            Add(i,l,r,max(C,a),min(D,b));
            continue;
        }
        if (l+1<=r-1) Add(i,l+1,r-1,A,B),Add(i,l+1,r-1,C,D);
        Add(i,l,l,max(A,a),min(B,(1<<i+1)-1));
        Add(i,l,l,max(C,a),min(D,(1<<i+1)-1));
        Add(i,r,r,max(A,0),min(B,b));
        Add(i,r,r,max(C,0),min(D,b));
    }
}
int main(){
    readi(n);readi(m);
    for (int i=0;i<n;i++) readi(a[i]);
    for (int i=1,tp,L,R,x;i<=m;i++){
        readi(tp);readi(L);readi(R);readi(x);L--;R--;
        if (!tp) sum[L]^=x,sum[R+1]^=x; else Solve(L,R,x);
    }
    a[0]^=sum[0];for (int i=1;i<n;i++) sum[i]^=sum[i-1],a[i]^=sum[i];
    for (int i=0;i<30;i++)
        for (int x=0;x<=(n-1>>i+1);x++)
            for (int y=0,lim=min(n,1<<i+1);y<lim;y++){
                if (ID(i,x,y)>n) continue;
                if (x) c[i][ID(i,x,y)]^=c[i][ID(i,x-1,y)];
                if (y) c[i][ID(i,x,y)]^=c[i][ID(i,x,y-1)];
                if (x && y) c[i][ID(i,x,y)]^=c[i][ID(i,x-1,y-1)];
                a[ID(i,x,y)]^=c[i][ID(i,x,y)]<<i;
            }
    for (int i=0;i<n;i++) printf("%d",a[i]),i<n-1?putchar(' '):puts("");
    return 0;
}