感觉及其好玩的题目
Rubidium_Chloride · · 题解
第一眼看上去以为是神仙分块题/根号分治，没想到
听说 hohodef 写了个类春节十二响的启发式合并还是啥，然后常数被我吊起来打了。
一开始以为是什么奇怪玄学复杂度，最后发现是
事实上可以稍作调整做到
做法
大概就是说，找到每一个块的块头，然后和一个虚拟点建立“父子关系”，这些就是下次要删掉的点。同时用链表维护一下在序列中的前后继，以及这些点删的顺序。
删的话很方便，如果一个点没有儿子了，那么直接删掉就可以了。
如果这个点还有儿子那么把儿子接到下一次要删的点上。
然后这两个过程中都需要同时在链表上进行修改。
当你把一个块删完的时候判一下前后两个块颜色是不是一样，如果一样那么直接把后面那个块块头连到前面那个块块尾上面去。
只需要链表操作，速度快的一批（
所以为啥只有
代码
#include<bits/stdc++.h>
#define N 200009
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0',c=getchar();}
return x*f;
}
ll n,a[N],son[N],nxt[N],pre[N],Son[N],cnt,p[N],tot=1;
void init(){
n=read();
a[0]=a[n+1]=-1;
for(int i=1;i<=n;i++) a[i]=read(),nxt[i]=i+1,pre[i]=i-1;
for(int i=1;i<=n;i++)
if(a[i]==a[i-1]) son[i-1]=i;
else Son[++cnt]=i;
}
void get(){
while(tot){
tot=0;
for(int i=1;i<=cnt;i++){
if(Son[i]==0) continue;
p[++tot]=Son[i];
nxt[pre[Son[i]]]=nxt[Son[i]];
pre[nxt[Son[i]]]=pre[Son[i]];
if(son[Son[i]]!=0) Son[i]=son[Son[i]];
else Son[i]=0;
}
for(int i=1;i<=cnt;i++)
if(Son[i]==0) swap(Son[i],Son[cnt]),cnt--;
for(int i=1;i<=cnt;i++){
if(Son[i]==0) continue;
if(a[pre[Son[i]]]==a[Son[i]]) son[pre[Son[i]]]=Son[i],Son[i]=0;
}
if(tot==0) break;
sort(p+1,p+tot+1);
for(int i=1;i<tot;i++) printf("%lld ",p[i]);
printf("%lld\n",p[tot]);
}
}
int main(){
//freopen("fruit.in","r",stdin);
//freopen("fruit.out","w",stdout);
init();
get();
return 0;
}复杂度分析
复杂度分析一下，令