博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 4333: JSOI2012 智者的考验
阅读量:5103 次
发布时间:2019-06-13

本文共 3263 字,大约阅读时间需要 10 分钟。

辣鸡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;}

转载于:https://www.cnblogs.com/cghAndy/p/6707332.html

你可能感兴趣的文章
IT项目经验和难点分享
查看>>
那些黑刘翔的人,你们的良心被狗吃了
查看>>
图片延迟加载(lazyload)的实现原理
查看>>
TreeMap和TreeSet在排序时如何比较元素?Collections工具类中的sort()方法如何比较元素?...
查看>>
Redis系列--内存淘汰机制(含单机版内存优化建议)
查看>>
最小二乘法
查看>>
iptables端口转发
查看>>
金融三问
查看>>
HTML5新API记录
查看>>
Android 8 AudioPolicy 分析
查看>>
IRT模型的参数估计方法(EM算法和MCMC算法)
查看>>
总账介绍
查看>>
建模各阶段以及相关UML构造笔记
查看>>
MS SQL Server查询优化方法
查看>>
《STL源码剖析》笔记
查看>>
linux命令及实例说明一:cd、ls、rmdir、rm、mkdir
查看>>
一、了解JavaScript
查看>>
出现( linker command failed with exit code 1)错误总结
查看>>
div水平垂直居中的几种方法(面试问题)
查看>>
AutoResetEvent类的使用
查看>>