[AGC028-E][树状数组]High Elements-白红宇

[AGC028-E][树状数组]High Elements

阅读量：120 次

发布时间：2019-02-26

本文共 3589 字，大约阅读时间需要 11 分钟。

翻译

题解

菜逼选手又来报到啦！
对于字典序最小的问题，我们显然是用按位确定的思想
定义几个变量方便使用
$c n t 0$ 表示 $A$ 序列当前有多少个前缀最大值， $c n t 1$ 表示 $B$ 序列当前有多少个前缀最大值
$m x 0$ 表示 $A$ 序列当前的最大值， $m x 1$ 表示 $B$ 序列当前的最大值
对于第 $i$ 位的确定工作，先分析能对序列大小做出贡献的序列的性质
假设我们后面能分成两个前缀最大值序列 $C$ 与 $D$ ，满足 $s i z (A) + s i z (C) = s i z (B) + s i z (D)$ ，且满足 $A C$ 合并与 $B D$ 合并后前缀最大值仍是前缀最大值，显然剩下的数总有方法填入的，故合法
分析序列 $C$ 与 $D$ 的性质
先找出原序列的所有前缀最大值，不妨设这个序列为 $E$
给出结论就是 $C, D$ 之中至少有一个序列满足是 $E$ 的完全子集，证明考虑反证
即 $C, D$ 中均存在至少一个数非原序列前缀最大值，则交换两数后 $C, D$ 的前缀最大值个数均减少 $1$ ，因为能制裁他们的都在对面的序列。连续做如上过程，我们总能使得其中至少一个序列成为 $E$ 的完全子集
不妨枚举哪个序列成为了完全子集，以 $C$ 为例
如果 $D$ 序列中存在 $E$ 的 $x$ 个元素，存在非 $E$ 序列中的 $m$ 个元素，且第 $i$ 位之后存在 $T$ 个 $E$ 中的元素，我们可以列出方程
$c n t 0 + T - x = c n t 1 + x + m$
移项可知是
$c n t 0 - c n t 1 + T = 2 * x + m$
左边是常数，我们仅需要知道右边能构成这样的序列即可
将是 $E$ 序列中的元素的权设为 $2$ ，其他的元素权设为 $1$ ，则我们需要知道一个上升序列且其权能够组成 $2 * x + m$
分奇偶讨论，我们发现如果一个数 $u$ 能够组成，则 $u - 2$ 也能够组成
维护两个 $b i t$ ，支持最大值查询即可

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #define LL long long#define mp(x,y) make_pair(x,y)#define pll pair
              
               #define pii pair
               
                using namespace std;inline int read(){ int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f;}int stack[20];inline void write(int x){ if(x<0){ putchar('-');x=-x;} if(!x){ putchar('0');return;} int top=0; while(x)stack[++top]=x%10,x/=10; while(top)putchar(stack[top--]+'0');}inline void pr1(int x){ write(x);putchar(' ');}inline void pr2(int x){ write(x);putchar('\n');}const int MAXN=200005;int n;int lowbit(int x){ return x&-x;}struct bittree{ int s[MAXN]; void modify(int x,int c){ for(;x<=n;x+=lowbit(x))s[x]=max(s[x],c);} int qry(int x){ int ret=0;for(;x>=1;x-=lowbit(x))ret=max(ret,s[x]);return ret;}}bi[2];int L[MAXN],R[MAXN],a[MAXN];int is[MAXN],sum;int re[2][MAXN][20];void rebuild(int i){ int u=n-a[i]+1; for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)bi[0].s[x]=re[0][i][cnt]; for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)bi[1].s[x]=re[1][i][cnt];}void getit(int i){ int u=n-a[i]+1; for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)re[0][i][cnt]=bi[0].s[x]; for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)re[1][i][cnt]=bi[1].s[x];}void init(){ int mx=0; for(int i=1;i<=n;i++)if(a[i]>mx)is[i]=1,mx=a[i],sum++; for(int i=n;i>=1;i--) { int u=n-a[i]+1; int u1=bi[0].qry(u-1),u2=bi[1].qry(u-1); if(is[i])u1+=2,u2+=2; else u1+=1,u2+=1; getit(i); bi[u1&1].modify(u,u1);bi[u2&1].modify(u,u2); }}int ans[MAXN];int mx[2],cnt[2];bool ok(int i,int o){ cnt[o]+=(a[i]>mx[o]); int u=n-mx[o^1]+1,c1=bi[0].qry(u-1),c2=bi[1].qry(u-1); int cal=cnt[o]-cnt[o^1]+sum; cnt[o]-=(a[i]>mx[o]); if(cal>=0) { if((cal&1)&&cal<=c2)return true; if((!(cal&1))&&cal<=c1)return true; } int ls=mx[o]; cnt[o]+=(a[i]>mx[o]);mx[o]=max(mx[o],a[i]); u=n-mx[o]+1,c1=bi[0].qry(u-1),c2=bi[1].qry(u-1); cal=cnt[o^1]-cnt[o]+sum; mx[o]=ls;cnt[o]-=(a[i]>mx[o]); if(cal>=0) { if((cal&1)&&cal<=c2)return true; if((!(cal&1))&&cal<=c1)return true; } return false;}int main(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(); init(); for(int i=1;i<=n;i++) { rebuild(i);sum-=is[i]; if(ok(i,0))ans[i]=0,cnt[0]+=(a[i]>mx[0]),mx[0]=max(mx[0],a[i]); else if(ok(i,1))ans[i]=1,cnt[1]+=(a[i]>mx[1]),mx[1]=max(mx[1],a[i]); else return puts("-1"),0; } for(int i=1;i<=n;i++)putchar(ans[i]+'0'); puts(""); return 0;}