辣鸡CSDN要我绑定手机才能登陆。上学有个P手机啊
JSOI吼劲啊= =
这道题其实就是线段树 (咦 听起来很简单? 可是蒟蒻的我不会啊。。。 然后就找dalao们问了问。。。首先 用异或来搞 这个很显然吧 本蒟蒻都知道
其实维护的东西还是挺正常的 我们维护区间中的前缀和每个种类的数量以及区间异或和
查询的时候就把厄运星和1...l-1的异或和 异或起来 查询l...r区间内有多少个前缀异或和是这个数就好了
那修改呢? 打标记是没有问题的 注意到区间修改成一样的 可以两两抵消 是可以O(1)算出区间内那些要维护的东西的 比较麻烦的就是前后合并 其实貌似弄个结构体 码起来并不麻烦。(orz男神) 具体可见代码 merge函数 很短。
最后 你可能会问这样搞不会T吗? 其实不会的 由于最多只有5个按键 不难发现按出来的状态是有重复而且不多的 经过dfs就可以得出其实只有16种
顾时间复杂度约为 O(MlogN*16) 别不会T我的代码并不快啊 QAQ (可能略丑
#include#define me(a,x) memset(a,x,sizeof a)using namespace std;inline int read(){ char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();} return x*f;}const int d[6]={1,2,4,8,16,32},N=1000005;int E,z[6],p[16],pl,n,m,v[65],tot;int tag[N<<1],lc[N<<1],rc[N<<1];struct node{int w[16],g;node(){me(w,0);}}s[N<<1];node merge(node x,node y){ node w; w.g=v[p[x.g]^p[y.g]]; for(int i=0;i n+m){ if(v[c]<0)p[pl]=c,v[c]=pl++; return; } dfs(x+1,c),dfs(x+1,c^z[x]);}void pushdown(int x,int l,int r){ if(!lc[x])lc[x]=++tot; if(!rc[x])rc[x]=++tot; int mid=(l+r)>>1,u=tag[x]; tag[x]=-1; tag[lc[x]]=tag[rc[x]]=u; me(s[lc[x]].w,0),me(s[rc[x]].w,0); s[lc[x]].w[0]=(mid-l+1)/2,s[lc[x]].w[u]=(mid-l+2)/2; s[rc[x]].w[0]=(r-mid)/2, s[rc[x]].w[u]=(r-mid+1)/2; s[lc[x]].g=(mid-l+1)&1?u:0,s[rc[x]].g=(r-mid)&1?u:0;}void change(int &x,int l,int r,int ql,int qr,int u){ if(!x)x=++tot; if(l==ql && r==qr){ tag[x]=u; s[x].g=(r-l+1)&1?u:0; me(s[x].w,0); s[x].w[0]=(r-l+1)/2,s[x].w[u]=(r-l+2)/2; return; } if(tag[x]!=-1)pushdown(x,l,r); int mid=(l+r)>>1; if(ql>mid) change(rc[x],mid+1,r,ql,qr,u); else if(qr<=mid) change(lc[x],l,mid,ql,qr,u); else change(lc[x],l,mid,ql,mid,u),change(rc[x],mid+1,r,mid+1,qr,u); s[x]=merge(s[lc[x]],s[rc[x]]);}int get(int x,int l,int r,int ql,int qr){ if(ql>qr)return 0; if(l==ql && r==qr)return s[x].g; if(tag[x]!=-1)pushdown(x,l,r); int mid=(l+r)>>1; if(ql>mid) return get(rc[x],mid+1,r,ql,qr); else if(qr<=mid) return get(lc[x],l,mid,ql,qr); return v[ p[get(lc[x],l,mid,ql,mid)]^p[get(rc[x],mid+1,r,mid+1,qr)] ];}node query(int x,int l,int r,int ql,int qr){ if(l==ql && r==qr)return s[x]; if(tag[x]!=-1)pushdown(x,l,r); int mid=(l+r)>>1; if(ql>mid) return query(rc[x],mid+1,r,ql,qr); else if(qr<=mid) return query(lc[x],l,mid,ql,qr); return merge(query(lc[x],l,mid,ql,mid),query(rc[x],mid+1,r,mid+1,qr));}int main(){ n=read(),m=read(); int i,j,u,l,r,w,q,x; E=0; for(i=1;i<=n;i++)for(j=1;j<=m;j++) E+=d[(i-1)*m+j-1]*read(); for(i=1;i<=n;i++)for(j=1;j<=m;j++)z[i]+=d[(i-1)*m+j-1]; for(i=1;i<=n;i++)for(j=1;j<=m;j++)z[n+j]+=d[(i-1)*m+j-1]; me(v,-1); dfs(1,0); w=read(),q=read(); int rt=0; tot=0; me(tag,-1); change(rt,1,w,1,w,v[z[1]]); while(q--) { int u=read(); if(!u) x=read(),u=read(),change(rt,1,w,x,x,v[z[u]]); else if(u==1){ l=read(),r=read(),u=get(rt,1,w,1,l-1); printf("%d\n",query(rt,1,w,l,r).w[ v[p[u]^E] ]); } else l=read(),r=read(),x=read(),change(rt,1,w,l,r,v[z[x]]); } return 0;}