Problem Statement
Given an array $a$ of $n$ integers, find out the contents of the array after $k$ bubble sort rounds.
$1 \leq n \leq 2 \times 10^5, 0 \leq k \leq 10^9, 1 \leq a_i \leq 10^9$
Tutorial
Note that if $k = 10^9$, then the array becomes fully sorted. Hence the problem is strictly stronger than regular sorting.
First, observe that if we perform one round of bubble sort on array $a$, for each index $i$, the number of indices $j$ such that $j < i$ and $a_j > a_i$ will decrease by one. This means we can compute how many values greater than $a_i$ are to its left after $k$ bubble sort rounds.
So, the problem is transformed into the following:
We have an array
$$p_i = \max\left(0, -k + \sum\limits_{1 \leq j < i} \left[a_j > a_i\right]\right)$$
and we are asked to reorder the array $a$ into array $b$ such that:
$$p_i = \sum\limits_{1 \leq j < i} \left[b_j > b_i\right]$$
then, $b$ is the final answer.
We can sort $(a_i, p_i)$ in decreasing order, then insert each $a_i$ at position $p_i$, but this takes $O\left(n^2\right)$ in total. We can optimize it using a balanced tree to achieve $O\left(n \log n\right)$, which is fast enough.
// rbtree (https://rbtr.ee)
// n@rbtr.ee
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;
public class Main {
static final boolean MULTI_TESTS = false;
static final boolean SPECIAL_TESTS = false;
static final Bin bin;
static final int INF32 = 1073741823;
static final long INF64 = 4611686018427387903L;
static final Random rng = new Random();
static int n, k;
static int[] a, all;
static HashMap<Integer, Integer> id;
static Fenwick<Integer, Opt> o;
static pair<Integer, Integer>[] q;
static class TNode {
int val;
int size;
long priority;
TNode left, right;
TNode(int val) {
this.val = val;
size = 1;
priority = rng.nextLong();
}
}
static int size(TNode t) {
return t == null ? 0 : t.size;
}
static void updateSize(TNode t) {
if (t != null) t.size = size(t.left) + size(t.right) + 1;
}
static TNode[] split(TNode t, int key) {
if (t == null) return new TNode[]{null, null};
int cur = size(t.left);
if (key <= cur) {
TNode[] leftSplit = split(t.left, key);
t.left = leftSplit[1];
updateSize(t);
return new TNode[] { leftSplit[0], t };
} else {
TNode[] rightSplit = split(t.right, key - cur - 1);
t.right = rightSplit[0];
updateSize(t);
return new TNode[] { t, rightSplit[1] };
}
}
static TNode merge(TNode left, TNode right) {
if (left == null) return right;
if (right == null) return left;
if (left.priority > right.priority) {
left.right = merge(left.right, right);
updateSize(left);
return left;
} else {
right.left = merge(left, right.left);
updateSize(right);
return right;
}
}
static TNode insert(TNode root, int pos, int val) {
TNode newNode = new TNode(val);
TNode[] splitNodes = split(root, pos);
TNode merged = merge(splitNodes[0], newNode);
return merge(merged, splitNodes[1]);
}
static void inorder(TNode t) {
if (t == null) return;
inorder(t.left);
bin.print(all[t.val] + " ");
inorder(t.right);
}
public static int ENGINE(int TEST_NUMBER) {
n = bin.Int();
k = bin.Int();
a = new int[n];
for (int i = 0; i < n; ++i) a[i] = bin.Int();
all = Arrays.copyOf(a, n);
Arrays.sort(all);
all = Arrays.stream(all).distinct().toArray();
id = new HashMap<>();
for (int i = 0; i < all.length; ++i) id.put(all[i], i);
for (int i = 0; i < n; ++i) a[i] = id.get(a[i]);
o = new Fenwick<>(all.length, new Opt());
q = new pair[n];
for (int i = 0; i < n; ++i) {
q[i] = new pair<>(a[i], Math.max(0, o.prod(all.length - 1) - o.prod(a[i]) - k));
o.apply(a[i], 1);
}
Arrays.sort(q, Comparator.reverseOrder());
TNode root = null;
for (int i = 0; i < n; ++i) root = insert(root, q[i].y, q[i].x);
inorder(root);
bin.println();
return 0;
}
public static class Opt implements Fen_Opt<Integer> {
public Integer op(Integer a, Integer b) { return a + b; }
public Integer e() { return 0; }
}
public static void main(String[] args) {
int t = 1;
if (MULTI_TESTS && !SPECIAL_TESTS) t = bin.Int();
for (int i = 1; i <= t || SPECIAL_TESTS; ++i)
if (ENGINE(i) != 0) break;
bin.close();
}
static {
try {
bin = new Bin();
} catch (IOException e) { throw new RuntimeException(e); }
}
static final class pair<Ty1 extends Comparable<Ty1>, Ty2 extends Comparable<Ty2>>
implements Comparable<pair<Ty1, Ty2>> {
public Ty1 x;
public Ty2 y;
public pair() {}
public pair(Ty1 a, Ty2 b) {
x = a;
y = b;
}
public int compareTo(pair<Ty1, Ty2> c) {
if (x.compareTo(c.x) != 0) return x.compareTo(c.x);
return y.compareTo(c.y);
}
}
static final class Bin extends PrintWriter {
private final BufferedReader in;
private StringTokenizer token;
public Bin() throws IOException { this(System.in, System.out); }
public int Int() { return Integer.parseInt(next()); }
public double Double() { return Double.parseDouble(next()); }
public long Long() { return Long.parseLong(next()); }
public BigInteger Big() { return new BigInteger(next()); }
public BigDecimal BigDecimal() { return new BigDecimal(next()); }
public Bin(InputStream input, OutputStream output) throws IOException {
super(output);
in = new BufferedReader(new InputStreamReader(input));
}
public Bin(String input, String output) throws IOException {
super(output);
in = new BufferedReader(new FileReader(input));
}
public String next() {
try {
while (token == null || !token.hasMoreTokens()) token = new StringTokenizer(in.readLine());
return token.nextToken();
} catch (Exception e) { return null; }
}
}
public static class Fenwick<Ty, Opt extends Fen_Opt<Ty>> {
private Object[] data;
private int n;
private Opt o;
public Fenwick(int n, Opt op) {
data = new Object[n];
this.n = n;
o = op;
Arrays.fill(data, o.e());
}
void apply(int x, Ty v) {
while (x < n) {
data[x] = o.op((Ty)data[x], v);
x |= x + 1;
}
}
Ty prod(int x) {
Ty e = o.e();
++x;
while (x > 0) {
e = o.op(e, (Ty)data[x - 1]);
x &= x - 1;
}
return e;
}
}
public interface Fen_Opt<Ty> {
Ty op(Ty a, Ty b);
Ty e();
}
}Besides, we can solve this problem in another simple way.
We can imagine doing $k$ bubble sort rounds in parallel. This means we only maintain the values of first $k$ largest elements.
Code
// rbtree (https://rbtr.ee)
// n@rbtr.ee
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;
public class Main {
static final boolean MULTI_TESTS = false;
static final boolean SPECIAL_TESTS = false;
static final Bin bin;
static final int INF32 = 1073741823;
static final long INF64 = 4611686018427387903L;
static final Random rng = new Random();
static int n, k;
static int[] a;
static PriorityQueue<Integer> q;
public static int ENGINE(int TEST_NUMBER) {
n = bin.Int();
k = bin.Int();
a = new int[n];
for (int i = 0; i < n; ++i) a[i] = bin.Int();
q = new PriorityQueue<>();
for (int i = 0; i < n; ++i) {
q.add(a[i]);
if (q.size() > k) {
bin.print(q.poll());
bin.print(' ');
}
}
while (!q.isEmpty()) {
bin.print(q.poll());
bin.print(' ');
}
bin.println();
return 0;
}
public static class Opt implements Fen_Opt<Integer> {
public Integer op(Integer a, Integer b) { return a + b; }
public Integer e() { return 0; }
}
public static void main(String[] args) {
int t = 1;
if (MULTI_TESTS && !SPECIAL_TESTS) t = bin.Int();
for (int i = 1; i <= t || SPECIAL_TESTS; ++i)
if (ENGINE(i) != 0) break;
bin.close();
}
static {
try {
bin = new Bin();
} catch (IOException e) { throw new RuntimeException(e); }
}
static final class pair<Ty1 extends Comparable<Ty1>, Ty2 extends Comparable<Ty2>>
implements Comparable<pair<Ty1, Ty2>> {
public Ty1 x;
public Ty2 y;
public pair() {}
public pair(Ty1 a, Ty2 b) {
x = a;
y = b;
}
public int compareTo(pair<Ty1, Ty2> c) {
if (x.compareTo(c.x) != 0) return x.compareTo(c.x);
return y.compareTo(c.y);
}
}
static final class Bin extends PrintWriter {
private final BufferedReader in;
private StringTokenizer token;
public Bin() throws IOException { this(System.in, System.out); }
public int Int() { return Integer.parseInt(next()); }
public double Double() { return Double.parseDouble(next()); }
public long Long() { return Long.parseLong(next()); }
public BigInteger Big() { return new BigInteger(next()); }
public BigDecimal BigDecimal() { return new BigDecimal(next()); }
public Bin(InputStream input, OutputStream output) throws IOException {
super(output);
in = new BufferedReader(new InputStreamReader(input));
}
public Bin(String input, String output) throws IOException {
super(output);
in = new BufferedReader(new FileReader(input));
}
public String next() {
try {
while (token == null || !token.hasMoreTokens()) token = new StringTokenizer(in.readLine());
return token.nextToken();
} catch (Exception e) { return null; }
}
}
public static class Fenwick<Ty, Opt extends Fen_Opt<Ty>> {
private Object[] data;
private int n;
private Opt o;
public Fenwick(int n, Opt op) {
data = new Object[n];
this.n = n;
o = op;
Arrays.fill(data, o.e());
}
void apply(int x, Ty v) {
while (x < n) {
data[x] = o.op((Ty)data[x], v);
x |= x + 1;
}
}
Ty prod(int x) {
Ty e = o.e();
++x;
while (x > 0) {
e = o.op(e, (Ty)data[x - 1]);
x &= x - 1;
}
return e;
}
}
public interface Fen_Opt<Ty> {
Ty op(Ty a, Ty b);
Ty e();
}
}- Category: 做题笔记
- Last update: 2025-06-09 08:02:08UTC+8
- Tags: Data Structures