数据结构专题 1
worldvanquisher
·
·
个人记录
图论狗都不写。宁可写数据结构也不想写图论了。写吐了。牛子老师说这套题的后半全是正经数据结构，而且无 Ynoi。
所以啥时候开多项式。
由于写题解主要是合集，因此打算分拆一下水点社贡。目前停留在打算阶段。
日，为什么明天考试。
CF1039D You Are Given a Tree
很久以前看到过。这题主要在想到这玩意可以根号分治。
卡常，要预处理 dfs 序，还要记忆化。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n,sq;
struct node{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int num,dfn[100010],fa[100010];
void dfs(int x,int f){
dfn[++num]=x;fa[x]=f;
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f)dfs(edge[i].v,x);
}
}
int dep[100010],ans[100010];
map<int,int>mp;
int check(int k){
if(k==1)return n;
if(mp.find(k)!=mp.end())return mp[k];
for(int i=1;i<=n;i++)dep[i]=1;
int ans=0;
for(int i=n;i>=1;i--){
int x=dfn[i];
if(fa[x]&&dep[fa[x]]&&dep[x]){
if(dep[x]+dep[fa[x]]>=k)ans++,dep[fa[x]]=0;
else dep[fa[x]]=max(dep[fa[x]],dep[x]+1);
}
}
return mp[k]=ans;
}
int main(){
scanf("%d",&n);sq=sqrt(n*__lg(n));
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(1,0);
for(int i=1;i<=sq;i++)ans[i]=check(i);
for(int i=sq;i>=1;i--){
int l=1,r=n+1,L,R;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)<=i)r=mid;
else l=mid+1;
}
if(l==1||l==n+1)continue;
L=l;
l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)>=i)l=mid;
else r=mid-1;
}
R=r;
for(int j=L;j<=R;j++)ans[j]=i;
}
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
```
## CF983E NN country
牛子老师说是水题。
首先套路倍增一个 $f_{i,j}$ 表示 $i$ 点跳 $j$ 条链能到哪里，然后根据是否有链经过 lca 来 $-1$。这是个套路二维数点，冲啥都行。
那好像真是水题，但是不是很想写。算了闲着也是闲着，写一发。
交了三发。主席树都写不清楚了！越来越菜了！
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iostream>
using namespace std;
int n,m,q;
struct gra{
int v,next;
}edge[200010];
int tot,head[200010];
void add(int u,int v){
edge[++tot].v=v;edge[tot].next=head[u];head[u]=tot;
}
int num,dfn[200010],sz[200010],fa[200010],top[200010],son[200010],dep[200010];
void dfs1(int x,int f){
sz[x]=1;dep[x]=dep[f]+1;
for(int i=head[x];i;i=edge[i].next){
dfs1(edge[i].v,x);
sz[x]+=sz[edge[i].v];
if(sz[son[x]]<sz[edge[i].v])son[x]=edge[i].v;
}
}
void dfs2(int x,int f,int tp){
dfn[x]=++num;top[x]=tp;
if(son[x])dfs2(son[x],x,tp);
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=son[x])dfs2(edge[i].v,x,edge[i].v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
struct node{
#define lson tree[rt].ls
#define rson tree[rt].rs
int ls,rs,val;
}tree[400010<<5];
int t,rt[200010];
void pushup(int rt){
tree[rt].val=tree[lson].val+tree[rson].val;
}
void update(int &rt,int pre,int L,int R,int pos){
rt=++t;tree[rt]=tree[pre];
if(L==R){
tree[rt].val++;return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,tree[pre].ls,L,mid,pos);
else update(rson,tree[pre].rs,mid+1,R,pos);
pushup(rt);
}
int query(int x,int y,int L,int R,int l,int r){
if(tree[y].val-tree[x].val==0)return 0;
if(l<=L&&R<=r)return tree[y].val-tree[x].val;
int mid=(L+R)>>1,val=0;
if(l<=mid)val+=query(tree[x].ls,tree[y].ls,L,mid,l,r);
if(mid<r)val+=query(tree[x].rs,tree[y].rs,mid+1,R,l,r);
return val;
}
vector<int>g[200010];
int f[200010][20];
pair<int,int> getfa(int x,int fa){
int ans=0;
for(int i=__lg(n);i>=0;i--)if(f[x][i]>fa)x=f[x][i],ans+=1<<i;
return make_pair(x,ans);
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d",&fa[i]);
add(fa[i],i);
}
dfs1(1,0);dfs2(1,0,1);
for(int i=1;i<=n;i++)f[i][0]=i;
scanf("%d",&m);
while(m--){
int u,v;scanf("%d%d",&u,&v);
int lc=lca(u,v);
f[u][0]=min(f[u][0],lc);f[v][0]=min(f[v][0],lc);
g[dfn[u]].push_back(dfn[v]);g[dfn[v]].push_back(dfn[u]);
}
for(int i=n;i>=1;i--)f[fa[i]][0]=min(f[fa[i]][0],f[i][0]);
for(int x=1;x<=n;x++){
for(int i=1;i<=__lg(n);i++)f[x][i]=f[f[x][i-1]][i-1];
}
for(int i=1;i<=n;i++){
rt[i]=rt[i-1];
for(int x:g[i])update(rt[i],rt[i],1,n,x);
}
scanf("%d",&q);
while(q--){
int u,v;scanf("%d%d",&u,&v);
int lc=lca(u,v),ans=0;
if(f[u][__lg(n)]>lc||f[v][__lg(n)]>lc){
puts("-1");continue;
}
if(lc==u){
printf("%d\n",getfa(v,lc).second+1);continue;
}
if(lc==v){
printf("%d\n",getfa(u,lc).second+1);continue;
}
pair<int,int>p=getfa(u,lc);
u=p.first;ans+=p.second;
p=getfa(v,lc);
v=p.first;ans+=p.second;
if(query(rt[dfn[u]-1],rt[dfn[u]+sz[u]-1],1,n,dfn[v],dfn[v]+sz[v]-1))ans++;
else ans+=2;
printf("%d\n",ans);
}
return 0;
}
```
## AGC001F Wide Swap
板刷 AGC 产物。详见 https://www.cnblogs.com/gtm1514/p/16878893.html。
## CF1578B Building Forest Trails
NOIP 时代的考试题，但我没改，现在还是不会。该来的还是要来的。
Delov，然和 Kaguya 都改了。
首先断环成链，令每个点向下一个同连通块的点连边，那么任意两个连通块不会相交。设 $p_i$ 为覆盖位置 $i$ 的边个数（即左端点小于 $i$，右端点大于 $i$），那么相邻两点的 $p_i$ 相差不超过 $1$。
考虑如何连边。不妨假设 $u<v$，两种情况：
1. $p_u\neq p_v$，假设 $p_u>p_v$。找到 $u$ 右边第一个点 $pos$ 满足 $p_{pos}<p_u$，那 $pos$ 所在的连通块一定覆盖了 $x$ 所在连通块，因此可以合并。
2. $p_u=p_v$：找到上述 $pos$，若 $pos<y$ 仍按上述操作，若 $pos\ge y$ 则说明 $x,y$ 可以直接合并。
合并只有 $O(n)$ 次，找 $pos$ 可以线段树上二分，合并两个连通块时根据有无交来区间加减 $p$，并查集多维护个连通块左右端点即可。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int n,m;
struct node{
#define lson rt<<1
#define rson rt<<1|1
int min,lz;
}tree[800010];
void pushup(int rt){
tree[rt].min=min(tree[lson].min,tree[rson].min);
}
void pushtag(int rt,int val){
tree[rt].min+=val;tree[rt].lz+=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);
pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
pushup(rt);
}
int query(int rt,int L,int R,int pos){
if(L==R)return tree[rt].min;
pushdown(rt);
int mid=(L+R)>>1;
if(pos<=mid)return query(lson,L,mid,pos);
else return query(rson,mid+1,R,pos);
}
int queryL(int rt,int L,int R,int pos,int val){
if(R<=pos){
if(tree[rt].min>=val)return 0;
if(L==R)return L;
pushdown(rt);
int mid=(L+R)>>1;
if(tree[rson].min<val)return queryL(rson,mid+1,R,pos,val);
else return queryL(lson,L,mid,pos,val);
}
pushdown(rt);
int mid=(L+R)>>1,ans=0;
if(mid<pos)ans=queryL(rson,mid+1,R,pos,val);
if(!ans)ans=queryL(lson,L,mid,pos,val);
return ans;
}
int queryR(int rt,int L,int R,int pos,int val){
if(pos<=L){
if(tree[rt].min>=val)return n+1;
if(L==R)return L;
pushdown(rt);
int mid=(L+R)>>1;
if(tree[lson].min<val)return queryR(lson,L,mid,pos,val);
else return queryR(rson,mid+1,R,pos,val);
}
pushdown(rt);
int mid=(L+R)>>1,ans=n+1;
if(pos<=mid)ans=queryR(lson,L,mid,pos,val);
if(ans==n+1)ans=queryR(rson,mid+1,R,pos,val);
return ans;
}
int fa[200010],l[200010],r[200010];
int find(int x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x);y=find(y);
if(r[x]<l[y])update(1,1,n,r[x]+1,l[y]-1,1);
else update(1,1,n,max(l[x],l[y]),min(r[x],r[y]),-1);
l[x]=min(l[x],l[y]);r[x]=max(r[x],r[y]);
fa[y]=x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=l[i]=r[i]=i;
while(m--){
int od,u,v;scanf("%d%d%d",&od,&u,&v);
if(od==1){
if(u>v)swap(u,v);
int val1=query(1,1,n,u),val2=query(1,1,n,v);
while(find(u)!=find(v)){
if(val1>val2){
merge(u,queryR(1,1,n,u,val1));
val1--;
}
else if(val1<val2){
merge(v,queryL(1,1,n,v,val2));
val2--;
}
else{
int pos=queryR(1,1,n,u,val1);
if(pos<v)merge(u,pos),val1--;
else merge(u,v);
}
}
}
else putchar((find(u)==find(v))+'0');
}
puts("");
return 0;
}
```
## CF1129D Isolation
小清新。这题目名称让我想起来一句歌词：
>Provoking black clouds in isolation
但是数据结构真就啥题都有。算了没 Ynoi 就行。
首先显然是扫描线然后拿个什么数据结构维护的。然后设 $a_i$ 上一次出现在 $pre_i$，那么每个地方是 $[pre_{pre_i}+1,pre_i]$ 减 $1$，$[pre_i+1,i]$ 加 $1$，然后要查询所有 $\le k$ 位置的 $dp_i$ 和。这个没法 polylog，直接分块，每个块开个桶维护是这个值的 $dp$ 值之和，修改可以整体打标记然后给答案加减一个位置的值。
写的意愿不是很大，于是贺了。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
const int mod=998244353;
int n,k,sq,ans,a[100010],L[320],R[320],belong[100010],f[320][100010],lz[320],cnt[100010];
int dp[100010],pre[100010],pos[100010];
void build(){
for(int i=1;i<=sq;i++){
L[i]=R[i-1]+1;R[i]=L[i]+sq-1;
}
R[sq]=n;
for(int i=1;i<=sq;i++){
for(int j=L[i];j<=R[i];j++)belong[j]=i;
}
}
void upd(int x,int val){
cnt[x]-=lz[belong[x]];
ans=(ans+val)%mod;
f[belong[x]][cnt[x]]=(f[belong[x]][cnt[x]]+val)%mod;
}
void pushdown(int x,int val){
f[belong[x]][cnt[x]]=(f[belong[x]][cnt[x]]-dp[x-1]+mod)%mod;
if(cnt[x]+lz[belong[x]]<=k)ans=(ans-dp[x-1]+mod)%mod;
cnt[x]+=val;
f[belong[x]][cnt[x]]=(f[belong[x]][cnt[x]]+dp[x-1])%mod;
if(cnt[x]+lz[belong[x]]<=k)ans=(ans+dp[x-1])%mod;
}
void update(int l,int r,int val){
if(l>r)return;
if(belong[l]==belong[r]){
for(int i=l;i<=r;i++)pushdown(i,val);
return;
}
for(int i=l;i<=R[belong[l]];i++)pushdown(i,val);
for(int i=L[belong[r]];i<=r;i++)pushdown(i,val);
for(int i=belong[l]+1;i<belong[r];i++){
if(val==1)ans=(ans-f[i][k-lz[i]]+mod)%mod;
else ans=(ans+f[i][k-lz[i]+1])%mod;
lz[i]+=val;
}
}
int main(){
scanf("%d%d",&n,&k);sq=sqrt(n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),pre[i]=pos[a[i]],pos[a[i]]=i;
dp[0]=1;build();
for(int i=1;i<=n;i++){
upd(i,dp[i-1]);
update(pre[pre[i]]+1,pre[i],-1);
update(pre[i]+1,i,1);
dp[i]=ans;
}
printf("%d\n",dp[n]);
return 0;
}
```
## AGC015E Mr.Aoki Incubator
板刷 AGC，但是刚刚做到所以没题解。
先考虑如果染一个 $i$ 那么哪些会被染。显然是前边比后缀最小值走的快的和后边比前缀最大值走的慢的。这俩都是单调的，所以若设 $dp_i$ 为选 $i$ 的方案数，枚举上一次染 $j$，从 $dp_j$ 转移过来，那么只有 $(j,i)$ 间速度在 $[premax_j,sufmin_i]$ 中的人不会被染色，这俩都是单调的，可以双指针维护。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int mod=1000000007;
int n,lsh[200010],dp[200010],sum[200010];
struct node{
int x,v;
bool operator<(const node&s)const{
return x<s.x;
}
}a[200010];
int l=1,r,L=1,R,cnt,mx[200010],mn[200010],pos[200010];
bool check(int l1,int r1,int L1,int R1){
if(l1>r1||L1>R1)return false;
while(r<r1){
r++;
if(a[r].v>=L&&a[r].v<=R)cnt++;
}
while(l<l1){
if(a[l].v>=L&&a[l].v<=R)cnt--;
l++;
}
while(R<R1){
R++;
if(pos[R]>=l&&pos[R]<=r)cnt++;
}
while(L<L1){
if(pos[L]>=l&&pos[L]<=r)cnt--;
L++;
}
return cnt;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].v),lsh[i]=a[i].v;
sort(a+1,a+n+1);sort(lsh+1,lsh+n+1);
for(int i=1;i<=n;i++)a[i].v=lower_bound(lsh+1,lsh+n+1,a[i].v)-lsh,pos[a[i].v]=i;
for(int i=1;i<=n;i++)mx[i]=max(mx[i-1],a[i].v);
mn[n+1]=n+1;
for(int i=n;i>=1;i--)mn[i]=min(mn[i+1],a[i].v);
dp[0]=sum[0]=1;
for(int i=1,l=0;i<=n+1;i++){
while(check(l+1,i-1,mx[l],mn[i]))l++;
dp[i]=(sum[i-1]-(l?sum[l-1]:0)+mod)%mod;
sum[i]=(sum[i-1]+dp[i])%mod;
}
printf("%d\n",dp[n+1]);
return 0;
}
```
## AGC007E Shik and Travel
板刷 AGC 产物。详见 https://www.cnblogs.com/gtm1514/p/16897422.html。
## CF1446D2 Frequency Problem (Hard Version)
超级 CF 结论题。
首先有结论：原序列的众数 $x$ 一定是答案区间的众数之一。反证：如果不是，那每次扩展一个，由于 $x$ 出现次数最多，那么一定有一次扩展使得 $x$ 和另一个众数出现次数相等。（类似介值定理？）
然后 Easy Verson 直接枚举另一个众数前缀和开个桶就做完了。Hard Verson 值域大所以 8 太行。
这玩意看着就很不 polylog，直接考虑根号做法。根号做法：序列分块，值域分块，根号分治，操作分块。24 直接 pass，1 看 Easy Verson 就和序列半点关系没有，考虑根号分治。
超过根号次的不超过根号个，按照 Easy Verson 的做法暴力枚举。然后考虑剩下的。一开始想的是找所有出现位置跑双指针，有点假。实际上枚举出现次数然后使所有数出现次数都不超过这个数就能跑了，也是双指针。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;
int n,sq,mx,ans,a[200010],cnt[200010],sum[200010],s[400010];
void solve1(int x){
for(int i=0;i<=2*n;i++)s[i]=0;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1];
if(a[i]==mx)sum[i]++;
if(a[i]==x)sum[i]--;
if(sum[i]&&!s[sum[i]+n])s[sum[i]+n]=i;
}
for(int i=1;i<=n;i++)ans=max(ans,i-s[sum[i]+n]);
}
void solve2(int x){
for(int i=1;i<=n;i++)cnt[i]=s[i]=0;
for(int l=1,r=0;l<=n;){
while(r<n&&cnt[a[r+1]]<x){
r++;
s[cnt[a[r]]]--;
cnt[a[r]]++;
s[cnt[a[r]]]++;
if(s[cnt[mx]]>1)ans=max(ans,r-l+1);
}
s[cnt[a[l]]]--;
cnt[a[l]]--;
s[cnt[a[l]]]++;
l++;
}
}
int main(){
scanf("%d",&n);sq=sqrt(n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;
for(int i=1;i<=n;i++)if(cnt[i]>=cnt[mx])mx=i;
for(int i=1;i<=n;i++)if(cnt[i]==cnt[mx]&&i!=mx){
printf("%d\n",n);return 0;
}
for(int i=1;i<=n;i++)if(cnt[i]>=sq&&i!=mx)solve1(i);
for(int i=1;i<=sq;i++)solve2(i);
printf("%d\n",ans);
return 0;
}
```
## CF765F Souvenirs
典题。
先只考虑 $j<i,a_j<a_i$ 的二元组 $(j,i)$，然后值域翻过来再做一遍。对右端点考虑可能成为答案的 $j$，那么设上一个贡献的是 $j_0$，它左边的 $j_1$ 可能有贡献则 $a_i-a_{j_1}\le\dfrac 12(a_i-a_{j_0})$，于是暴跳只会跳 $O(\log a_i)$ 次，复杂度是对的。因此扫描线，权值线段树维护 $a$，查询套上个树状数组维护后缀最大值就行了。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int inf=1000000000;
int n,m,ans[300010],a[100010];
vector<pair<int,int> >q[300010];
struct node{
#define lson tree[rt].ls
#define rson tree[rt].rs
int ls,rs,max;
}tree[100010<<5];
int t,rt;
void pushup(int rt){
tree[rt].max=max(tree[lson].max,tree[rson].max);
}
void update(int &rt,int L,int R,int pos,int val){
if(!rt)rt=++t;
if(L==R){
tree[rt].max=val;return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,val);
else update(rson,mid+1,R,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int l,int r){
if(!rt)return 0;
if(l<=L&&R<=r)return tree[rt].max;
int mid=(L+R)>>1,val=0;
if(l<=mid)val=max(val,query(lson,L,mid,l,r));
if(mid<r)val=max(val,query(rson,mid+1,R,l,r));
return val;
}
struct BIT{
int c[100010];
#define lowbit(x) (x&-x)
void update(int x,int val){
while(x)c[x]=min(c[x],val),x-=lowbit(x);
}
int query(int x){
int sum=inf;
while(x<=n)sum=min(sum,c[x]),x+=lowbit(x);
return sum;
}
}c;
void solve(){
for(int i=1;i<=n;i++)c.c[i]=inf;
for(int i=1;i<=n;i++){
int pre=0;
while(pre<=a[i]){
int pos=query(rt,0,inf,pre,a[i]);
if(!pos)break;
c.update(pos,a[i]-a[pos]);
pre=(a[pos]+a[i]+2)>>1;
}
for(pair<int,int>p:q[i])ans[p.second]=min(ans[p.second],c.query(p.first));
update(rt,0,inf,a[i],i);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;scanf("%d%d",&l,&r);
q[r].push_back(make_pair(l,i));ans[i]=inf;
}
solve();
for(int i=1;i<=n;i++)a[i]=inf-a[i];
for(int i=1;i<=t;i++)tree[i].ls=tree[i].rs=tree[i].max=0;t=0;rt=0;
solve();
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
```
## CF1458D Flip and Reverse
《数据结构》
欧拉回路都能在数据结构专题里边了，那你咋不塞个多项式进去呢？哦我懂了，他看见 CF 有 data structure 标签就塞进去了。
按照原串建图，$0$ 为 $-1$，$1$ 为 $1$ 做前缀和 $s$，连 $s_i\rightarrow s_{i+1}$ 的边。然后考虑翻转干了什么事。发现翻转的区间 $l,r$ 满足 $s_{l-1}=s_r$，那就是把一个环倒过来，于是连无向边跑一发字典序最小的欧拉路就完。你甚至都不用建图。
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int n,cnt[1000010][2];
char s[500010];
int main(){
int tim;scanf("%d",&tim);
while(tim--){
scanf("%s",s+1);n=strlen(s+1);
int p=0;
for(int i=1;i<=n;i++){
cnt[n+p][s[i]-'0']++;
if(s[i]=='0')p--;
else p++;
}
p=0;
for(int i=1;i<=n;i++){
if(cnt[n+p][0]&&cnt[n+p-1][1])putchar('0'),cnt[n+p][0]--,p--;
else if(cnt[n+p][1]&&cnt[n+p+1][0])putchar('1'),cnt[n+p][1]--,p++;
else if(cnt[n+p][0])putchar('0'),cnt[n+p][0]--,p--;
else if(cnt[n+p][1])putchar('1'),cnt[n+p][1]--,p++;
}
puts("");
}
return 0;
}
```