bzoj 5361 [Lydsy1805月赛]对称数

bzoj 5361 [Lydsy1805月赛]对称数

​​ begin.lydsy.com/JudgeOnline/upload/201805.pdf

mdzz真是气疯了 一开写的时候还想 有没有可能全部数字都是出现奇数次啊 那怎么没让我输出-1啊 claris 一定是非常好让我们少麻烦

md然后调试了几个小时 如果都没有说明答案是2e5+1

考虑如何快速判断异或 我们可以unsigned long long随便随机一些数字 然后假设为x1,x2,x3

那么他们异或出来的数基本都是独一无二的所以我们可以考虑在主席数上的区间把这些值记录下来 那么我就可以用这些值快速判断一个区间内是否所有的数都出现了奇数次 只需要主席树建立根到这个节点的信息 然后 用lca fa[lca],x,y互相异或下出结果即可

#include#include#include#include#define lc (x<<1)#define rc (x<<1|1)#define ll unsigned long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2e5+20;inline ll rd(){ return rand()<<15|rand();}ll sd[N<<2],v[N];struct node{ int left,right;ll x;}tree[N*22];struct node1{ int y,next;}data[N<<1];int T,fa[N][20],dep[N],q[5],num,h[N],Log[N],n,m,a[N],rt[N];inline void build(int x,int l,int r){ if (l==r) {sd[x]=v[l]=rd();return;}int mid=l+r>>1; build(lc,l,mid);build(rc,mid+1,r);sd[x]=sd[lc]^sd[rc];}inline void insert1(int &x,int l,int r,int p,ll v){ tree[++num]=tree[x];x=num;tree[x].x^=v; int mid=l+r>>1;if (l==r) return; if (p<=mid) insert1(tree[x].left,l,mid,p,v); else insert1(tree[x].right,mid+1,r,p,v);}inline void dfs(int x){ rt[x]=rt[fa[x][0]];insert1(rt[x],1,2e5+1,a[x],v[a[x]]); for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if(y==fa[x][0]) continue;fa[y][0]=x; dep[y]=dep[x]+1;for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1];dfs(y); }}inline int lca(int x,int y){ if (dep[x]>1;ll tmp=0; for (int i=1;i<=4;++i) tmp^=tree[tree[q[i]].left].x; if (tmp==sd[lc]) { for (int i=1;i<=4;++i) q[i]=tree[q[i]].right; return query(rc,mid+1,r); } for (int i=1;i<=4;++i) q[i]=tree[q[i]].left; return query(lc,l,mid);}int main(){ freopen("bzoj5361.in","r",stdin); srand(20010820);Log[0]=-1;build(1,1,2e5+1); T=read();for (int i=1;i<=2e5+1;++i) Log[i]=Log[i>>1]+1; while(T--){ n=read();m=read();memset(fa,0,sizeof(fa)); for (int i=1;i<=n;++i) a[i]=read();num=0;memset(h,0,sizeof(h)); for (int i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。