#include<bits/stdc++.h>
#include<queue>
#include<stack>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define Fi first
#define Se second
inline int input(){int x;return cin>>x,x;}
const int inf = 30;
const int N = 1012345;
bool ST;
int n,k,a[N];
vector<int> ans[N];
stack<P> st;
bitset<N> vst;
void Solve(){
For(i,1,n){
while(st.size() && st.top().Fi<a[i]){
int x=st.top().Fi,id=st.top().Se;st.pop();
ans[id].emplace_back(x);
int psh=x+1;
while(st.size() && st.top().Fi==psh){
st.pop();psh++;
}st.push({psh,id});
}
int psh=a[i];
while(st.size() && st.top().Fi==psh){
st.pop();psh++;
}st.push({psh,i});
}
while(st.size() && st.top().Fi!=30){
int x=st.top().Fi,id=st.top().Se;st.pop();
ans[id].emplace_back(x);
int psh=x+1;
while(st.size() && st.top().Fi==psh){
st.pop();psh++;
}st.push({psh,id});
}
}
queue<int> que;
bool ED;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
string str("index");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
cin>>n>>k;For(i,1,n) a[i]=input();
//找到所有元素
Solve();
//拆分
For(i,1,n) k-=ans[i].size();
For(i,1,n){
cout<<a[i]<<' ';
for(auto x:ans[i]){
que.push(x);
while(que.front()!=0 && k){
int y=que.front();que.pop();
que.push(y-1),que.push(y-1);
k--;
}while(que.size()) cout<<que.front()<<' ',que.pop();
}
}return 0;
}
题解代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vint;
typedef vector<vint> vvint;
int read() {
int a = 0, b = 0;
char c = getchar();
while (c < '0' || c > '9')
b ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9')
a = a * 10 - 48 + c, c = getchar();
return b ? -a : a;
}
const int N = 1000005;
int n, k, a[N];
vint in[N];
struct dat {
int v, l, r;
};
void ot(int v) {
if (v == 0 || k == 0) {
cout << v << ' ';
return;
}
--k;
ot(v - 1);
ot(v - 1);
}
int main() {
freopen("index.in","r",stdin);
freopen("index.out","w",stdout);
n = read(), k = read();
for (int i = 0; i < n; ++i)
a[i] = read();
vector<dat> d(n);
for (int i = 0; i < n; ++i)
d[i] = {a[i], i, i};
for (int t = 0; t < 30; ++t) {
int m = d.size();
vector<dat> nd;
for (int i = 0, c = 0; i < m; ++i) {
c += d[i].v == t;
if (d[i].v != t)
nd.push_back(d[i]);
if (d[i].v == t && (i + 1 == m || d[i + 1].v != t)) {
int L = i - c + 1;
for (int j = L; j + 1 <= i; j += 2)
nd.push_back({t + 1, d[j].l, d[j + 1].r});
if (c & 1) {
nd.push_back({t + 1, d[i].l, d[i].r});
in[d[i].r].push_back(t);
--k;
}
c = 0;
}
}
d.swap(nd);
}
assert(k >= 0);
for (int i = 0; i < n; ++i) {
cout << a[i] << ' ';
for (int v : in[i])
ot(v);
}
cout << '\n';
assert(k == 0);
return 0;
}
