把每个块用 链表串起来 不知为何会输出n之外的数
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar();}
while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int N = 1e6 + 5;
int n, x;
struct PPP{
int len, v, num; // num 为 头的位置
}p[N];
struct link{
int l, r;
}e[N];// 链表存储 前后块的位置
int cnt;
vector <int> v;
int main() {
n = read();
int last = 1;
for (int i = 1; i <= n; i++) {
x = read();
if (i == 1 || x != last) {
p[++cnt].len = 1;
p[cnt].v = x;
p[cnt].num = i;
}
else {
p[cnt].len++;
}
last = x;
}
if (cnt == 1) e[1].l = e[1].r = -1;
else {
e[1].l = -1, e[1].r = 2;
e[cnt].l = cnt - 1, e[cnt].r = -1;
}
for (int i = 2; i < cnt; i++) {
e[i].l = i - 1, e[i].r = i + 1;
}
int hh = 1;
while (hh != -1) {
for (int i = hh; i != -1; i = e[i].r) {
printf("%d ", p[i].num++);
p[i].len--;
}
for (int i = hh; i != -1; i = e[i].r) {
if (!p[i].len) {
if (i == hh) hh = e[hh].r;
int ll = e[i].l, rr = e[i].r;
if (ll == -1 || rr == -1) {
if (ll == -1 && rr == -1) continue;
if (ll == -1) e[rr].l = -1;
else e[ll].r == -1;
}
else {
if (p[ll].v != p[rr].v)
e[ll].r = rr, e[rr].l = ll;
else {
e[e[ll].l].r = rr;
e[rr].l = e[ll].l;
p[rr].len += p[ll].len;
p[rr].num = p[ll].num;
}
}
}
}
cout << endl;
}
return 0;
}