睿智场
T1 不知道哪来的神仙题，机房集体咕咕了
T2 因为是随机的所以搞类似缓冲区的东西放在中间
不想写了 看i207M的吧
或者直接平衡树维护中间大概1e4个也行
Upd：orz lhw
T3 打表找SG的规律，发现p是奇数是奇偶性，p是偶数除了模p+1是p的是2，其他的都是奇偶性
前者线段树，后者分块
分块麻烦(其实是只剩半个小时没时间了)，考场循环展开+优化水过
1 #pragma GCC optimize("O2,Ofast,inline") 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<algorithm> 6 #include<unordered_map> 7 #define uint unsigned int 8 using namespace std; 9 const int N=400005; 10 uint n,m,p,k,op,tot; 11 uint a[N],val[N],laz[N],ans[N]; 12 13 char BF[1<<23],*P1=BF,*P2=BF; 14 char Gc(){return (P1==P2&&(P2=(P1=BF)+fread(BF,1,1<<21,stdin),P1==P2)?EOF:*P1++);} 15 void Read(uint &x) 16 { 17 x=0; char ch=Gc(); 18 while(!isdigit(ch)) ch=Gc(); 19 while(isdigit(ch)) x=((x<<3)+(x<<1)+(ch^48))%(p+1),ch=Gc(); 20 } 21 void R(uint &x) 22 { 23 x=0; char ch=Gc(); 24 while(!isdigit(ch)) ch=Gc(); 25 while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=Gc(); 26 } 27 char OBF[1<<23],*Ot=OBF; 28 void W(uint x) 29 { 30 if(x>9) W(x/10); 31 *Ot++=x%10|48; 32 } 33 34 void Create(int nde,int l,int r) 35 { 36 if(l==r) 37 val[nde]=a[l]; 38 else 39 { 40 int mid=(l+r)>>1,ls=2*nde,rs=2*nde+1; 41 Create(ls,l,mid),Create(rs,mid+1,r); 42 val[nde]=val[ls]^val[rs]; 43 } 44 } 45 void Release(int nde,int l,int r) 46 { 47 if(laz[nde]) 48 { 49 uint &lz=laz[nde]; 50 int mid=(l+r)>>1,ls=2*nde,rs=2*nde+1; 51 val[ls]^=((mid-l+1)&1),val[rs]^=((r-mid)&1); 52 laz[ls]^=1,laz[rs]^=1,lz=0; 53 } 54 } 55 void Modify(int nde,int l,int r,int ll,int rr) 56 { 57 if(l>rr||r<ll) 58 return; 59 else if(l>=ll&&r<=rr) 60 val[nde]^=((r-l+1)&1),laz[nde]^=1; 61 else 62 { 63 int mid=(l+r)>>1,ls=2*nde,rs=2*nde+1; Release(nde,l,r); 64 Modify(ls,l,mid,ll,rr),Modify(rs,mid+1,r,ll,rr),val[nde]=val[ls]^val[rs]; 65 } 66 } 67 uint Query(int nde,int l,int r,int ll,int rr) 68 { 69 if(l>rr||r<ll) 70 return 0; 71 else if(l>=ll&&r<=rr) 72 return val[nde]; 73 else 74 { 75 int mid=(l+r)>>1,ls=2*nde,rs=2*nde+1; Release(nde,l,r); 76 return Query(ls,l,mid,ll,rr)^Query(rs,mid+1,r,ll,rr); 77 } 78 } 79 void Sol1() 80 { 81 uint t1,t2,t3; 82 const int nn=n,mm=m; 83 for(int i=1;i<=nn;i++) R(a[i]),a[i]&=1; 84 Create(1,1,nn); 85 for(int i=1;i<=mm;i++) 86 { 87 R(op); 88 if(!op) 89 { 90 R(t1),R(t2),R(t3); 91 if(t3&1) Modify(1,1,n,t1,t2); 92 } 93 else 94 { 95 R(t1),R(t2); 96 ans[++tot]=Query(1,1,n,t1,t2); 97 } 98 } 99 } 100 101 void Sol2() 102 { 103 register int i,j; 104 const int nn=n,mm=m; 105 const uint mod=p+1,md=p; 106 for(i=1;i<=nn;i++) Read(a[i]); 107 for(i=1;i<=mm;i++) 108 { 109 R(op); 110 if(!op) 111 { 112 uint t1,t2,ad; 113 R(t1),R(t2),Read(ad); 114 const int lim=t2,lm=t2-8; const uint t3=ad; 115 for(j=t1;j<=lm;j+=8) 116 { 117 int n1=j+1,n2=j+2,n3=j+3,n4=j+4,n5=j+5,n6=j+6,n7=j+7; 118 a[j]=(a[j]+t3>=mod)?(a[j]+t3-mod):(a[j]+t3); 119 a[n1]=(a[n1]+t3>=mod)?(a[n1]+t3-mod):(a[n1]+t3); 120 a[n2]=(a[n2]+t3>=mod)?(a[n2]+t3-mod):(a[n2]+t3); 121 a[n3]=(a[n3]+t3>=mod)?(a[n3]+t3-mod):(a[n3]+t3); 122 a[n4]=(a[n4]+t3>=mod)?(a[n4]+t3-mod):(a[n4]+t3); 123 a[n5]=(a[n5]+t3>=mod)?(a[n5]+t3-mod):(a[n5]+t3); 124 a[n6]=(a[n6]+t3>=mod)?(a[n6]+t3-mod):(a[n6]+t3); 125 a[n7]=(a[n7]+t3>=mod)?(a[n7]+t3-mod):(a[n7]+t3); 126 } 127 while(j<=lim) 128 { 129 a[j]+=t3; 130 if(a[j]>=mod) a[j]-=mod; ++j; 131 } 132 } 133 else 134 { 135 uint t1,t2; 136 R(t1),R(t2); 137 const int lim=t2,lm=t2-8; 138 uint ss=0,s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,s7=0; 139 for(j=t1;j<=lm;j+=8) 140 { 141 int n1=j+1,n2=j+2,n3=j+3,n4=j+4,n5=j+5,n6=j+6,n7=j+7; 142 ss^=((a[j]^md)?(a[j]&1):2); 143 s1^=((a[n1]^md)?(a[n1]&1):2); 144 s2^=((a[n2]^md)?(a[n2]&1):2); 145 s3^=((a[n3]^md)?(a[n3]&1):2); 146 s4^=((a[n4]^md)?(a[n4]&1):2); 147 s5^=((a[n5]^md)?(a[n5]&1):2); 148 s6^=((a[n6]^md)?(a[n6]&1):2); 149 s7^=((a[n7]^md)?(a[n7]&1):2); 150 } 151 while(j<=lim) {ss^=((a[j]==md)?2:(a[j]&1));++j;} 152 ans[++tot]=(bool)(ss^s1^s2^s3^s4^s5^s6^s7); 153 } 154 } 155 } 156 157 int main() 158 { 159 register uint i; 160 R(n),R(m),R(p); 161 if(p&1) Sol1(); else Sol2(); 162 for(i=1;i<=tot;i++) 163 { 164 W(ans[i]); 165 if(i!=tot) *Ot++=' '; 166 } 167 fwrite(OBF,Ot-OBF,1,stdout); 168 return 0; 169 }