AtCoder-arc227_b Know Your Place 题解

Solution我们从小到大依次枚举值xxx并将所有xxx插入序列。初始时序列为空。设当前值为xxx的数出现了yyy次。由于目前序列里所有数都xxx我们一定会在当前序列的第xxx位后插入yyy个xxx。如果答案序列长度不够则一定无解。模拟上述过程用 FHQ Treap 维护答案序列即可。Code#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)#definels(p)t[p].ls#definers(p)t[p].rsusingnamespacestd;constintN5e55;inta[N],ans[N],rt,n,m,j,len,l,r;structNode{intls,rs,pri,sz,ch;}t[N];inlineintnwnode(intc){returnt[m]{0,0,rand(),1,c},m;}inlinevoidpushup(intp){t[p].szt[ls(p)].szt[rs(p)].sz1;}voiddfs(intp){if(ls(p))dfs(ls(p));coutt[p].ch ;if(rs(p))dfs(rs(p));}voidsplit(intp,intx,intl,intr){if(!p)returnlr0,void();if(t[ls(p)].sz1x)lp,split(rs(p),x-t[ls(p)].sz-1,rs(p),r);elserp,split(ls(p),x,l,ls(p));pushup(p);}intmerge(intl,intr){if(!l||!r)returnl|r;if(t[l].prit[r].pri)returnrs(l)merge(rs(l),r),pushup(l),l;elsereturnls(r)merge(l,ls(r)),pushup(r),r;}signedmain(){cin.tie(0)-sync_with_stdio(0);cinn;rep(i,0,n)cina[i];sort(a,an);a[n]N;rep(i,1,n){if(a[i]^a[j]){// 值为a[j]出现了i-j次if(lena[j])returncoutNo,0;intl,r;split(rt,a[j],l,r);rep(_,0,i-j)lmerge(l,nwnode(a[j]));rtmerge(l,r);leni-j;ji;}}coutYes\n;dfs(rt);return0;}