P9970
闲话
膜你赛刚做过类似的 trick，结果马上就用上了/jy
场上一下子就切了，没吃罚时，很爽！
Solution
结论
先说一个经典（？结论：
方便起见，先下一个定义：
我们称满足
\text{mex}(l,r)=x 的区间为x\text{-mex} 区间。对于一个
x\text{-mex} 区间[l,r] ，如果不存在另一个x\text{-mex} 区间[l',r']\subset[l,r] ，则称[l,r] 为『极小的 mex 区间』。
-
则有结论：极小的 mex 区间只有
\Theta(n) 个；具体的，一个上界是2n 。 -
证明：对于一个满足条件的『极小的 mex 区间』
[l,r] 显然满足a_l\ne a_r ，否则删任意一个不影响答案，不妨假设a_l>a_r ，则a_r 和a_l 的加入先后影响了\text{mex}(l,r) 的答案，则可以得到的是：\text{mex}(l+1,r-1)=a_r ，由于当l 固定时\text{mex} 单调不降，且有多个满足他条件的r 只取最左边那个，所以对于任意的l 只有一个r 满足条件；同理，对于a_l<a_r 的情况，对于每个r 也至多只有一个l 满足条件，故最多只有2n 个『极小的 mex 区间』。
求『极小的 mex 区间』
然后我们考虑知道了这么一个性质只会要怎么做。
那么我们首先要把所有极小的 mex 区间给掏出来，这个好像说是有什么『阶梯状』的东西，和同学们讨论了一下，不是很懂（或者说感觉不是很好维护），这里讲一个比较脑瘫的求法。如果说你会比较优雅的求法，那么可以选择跳过。
假设我们已经求出
那么一个比较显然的结论是：
然后我们就得到了一个求『极小的 mex 区间』的算法：
- 预处理出极小的
0\text{-mex} 和1\text{-mex} 区间。 - 对于每一个极小的
(x-1)\text{-mex} 区间分别求出其距离左端点最近的x-1 出现位置，和距离右端点最近的x-1 出现位置，形成两个新的区间，算一下两个区间的\text{mex}=x' ，然后丢到对应的存储x'\text{-mex} 区间的vector里。 - 对于存储
x\text{-mex} 区间的vector求极小区间。
由于最终答案是
对于实现细节：
-
求在某个点左/右侧最近的
=x 的点：开n 个vector，分别存储每个数的出现位置，vector上二分即可。 -
在线求区间 mex：这个也就是 P4137，主席树即可，不再赘述。
计算答案
我们考虑对于每个『极小的
则对于任意
然后对于最终为
则我们倒着枚举
至于区间推平，ODT 即可。
需要注意的是，这里 ODT 复杂度不依赖于随机，而依赖于均摊。
具体的，每次未被推平成
最终复杂度
常数看起来很大，但是实际上跑得很快，不是很懂。
Code
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
bool M1;
void file_IO() {
// freopen("mushroom.in","r",stdin);
// freopen("mushroom.out","w",stdout);
}
const int N=1e5+5;
int a[N],n,q;
vector<int> vec[N];
vector<PII> g[N];
inline int pre(const vector<int> &vec,const int& x) {
auto p=upper_bound(vec.begin(),vec.end(),x);
if(p!=vec.begin())
return *(--p);
return -1;
}
inline int nxt(const vector<int> &vec,const int& x) {
auto p=lower_bound(vec.begin(),vec.end(),x);
if(p!=vec.end())
return *p;
return -1;
}
struct PSGT {
struct node {
int lson,rson,val;
}; node tree[N*20];
int p;
inline int new_node(const int& k) {
tree[++p]=tree[k];
return p;
}
inline void push_up(const int& k) {
tree[k].val=min(tree[tree[k].lson].val,tree[tree[k].rson].val);
}
void update(int &k,const int& l,const int& r,const int& qx,const int& val) {
k=new_node(k);
if(l==r) {
tree[k].val=val;
return;
}
int mid=(l+r)>>1;
if(qx<=mid)
update(tree[k].lson,l,mid,qx,val);
if(qx>=mid+1)
update(tree[k].rson,mid+1,r,qx,val);
push_up(k);
}
int query(const int& k,const int& l,const int& r,const int& ql,const int& qr) {
if(l==r)
return l;
int mid=(l+r)>>1,val=tree[tree[k].lson].val;
if(val<ql)
return query(tree[k].lson,l,mid,ql,qr);
return query(tree[k].rson,mid+1,r,ql,qr);
}
int root[N],cnt;
inline void ins(const int& x) {
++cnt;
root[cnt]=root[cnt-1];
update(root[cnt],0,n,x,cnt);
}
}; PSGT T2;
inline int mex(const int& l,const int& r) {
return T2.query(T2.root[r],0,n,l,r);
}
struct ODT {
struct node {
int l,r;
mutable int val;
node() {
l=r=val=0;
}
node(int _l,int _r,int _val) {
l=_l; r=_r; val=_val;
}
bool operator < (const node &tmp) const {
return l<tmp.l;
}
}; set<node> s;
ODT() {
s.clear();
s.insert(node{1,n,0});
}
auto split(int pos) {
auto p=s.lower_bound(node(pos,0,0));
if(p!=s.end()&&(*p).l==pos)
return p;
--p;
if((*p).r<pos)
return s.end();
int l=(*p).l,r=(*p).r,val=(*p).val;
s.erase(p);
s.insert(node(l,pos-1,val));
auto t=s.insert(node(pos,r,val));
return t.first;
}
void assign(int l,int r,int val) {
auto _r=split(r+1),_l=split(l);
s.erase(_l,_r);
s.insert(node(l,r,val));
}
auto ins(int p,int val) {
auto t=s.insert(node(p,p,val));
return t.first;
}
}; ODT T,T1;
int ans[N];
inline void solve() {
scanf("%d",&n);
rep(i,1,n) {
scanf("%d",&a[i]);
vec[a[i]].push_back(i);
T2.ins(a[i]);
}
rep(i,1,n) {
if(a[i])
g[0].push_back({i,i});
else
g[1].push_back({i,i});
}
rep(i,1,n) {
for(auto x:g[i-1]) {
int l=x.first,r=x.second;
int pl=pre(vec[i-1],l),pr=nxt(vec[i-1],r);
if(pl!=-1)
g[mex(pl,r)].push_back({pl,r});
if(pr!=-1)
g[mex(l,pr)].push_back({l,pr});
}
sort(g[i].begin(),g[i].end(),[](const PII &a,const PII &b) {
return a.first>b.first||(a.first==b.first&&a.second<b.second);
});
vector<PII> tmp;
int last=INF;
for(auto x:g[i]) {
if(last>x.second)
tmp.push_back(x);
chkmin(last,x.second);
}
swap(g[i],tmp);
}
T1=ODT();
per(i,n+1,0) {
T=ODT();
for(auto x:g[i]) {
int l=x.first,r=x.second;
int pl=pre(vec[i],l),pr=nxt(vec[i],r);
if(pl==-1)
pl=1;
else
++pl;
if(pr==-1)
pr=n;
else
--pr;
T.assign(r-l+1,pr-pl+1,1);
}
for(auto x:T.s) {
int l=x.l,r=x.r,val=x.val;
if(!val)
T1.assign(l,r,i);
}
}
for(auto x:T1.s) {
int l=x.l,r=x.r,val=x.val;
rep(i,l,r)
printf("%d ",val);
}
}
bool M2;
signed main() {
file_IO();
int testcase=1;
//scanf("%d",&testcase);
while(testcase--)
solve();
// cerr<<"used time = "<<1000.0*clock()/CLOCKS_PER_SEC<<"ms\n";
// cerr<<"used memory = "<<(&M1-&M2)/1024/1024<<"MB\n";
return 0;
}