P8500 [NOI2022] 冒泡排序 题解

Description

最近，小 Z 对冒泡排序产生了浓厚的兴趣。

下面是冒泡排序的伪代码：

输入: 一个长度为 n 的序列 a[1...n]
输出: a 从小到大排序后的结果
for i = 1 to n do:
    for j = 1 to n - 1 do
        if (a[j] > a[j + 1])
            交换 a[j] 与 a[j + 1] 的值

冒泡排序的交换次数被定义为在排序时进行交换的次数，也就是上面冒泡排序伪代码第六行的执行次数。他希望找到一个交换次数尽量少的序列。

小 Z 所研究的序列均由非负整数构成。它的长度为 $n$，且必须满足 $m$ 个附加条件。其中第 $i$ 个条件为：下标在 $[L_i, R_i]$ 中的数，即 $a_{L_i}, a_{L_{i+1}},\dots,a_{R_i}$ 这些数，其最小值恰好为 $\boldsymbol{V_i}$。

他知道冒泡排序时常会超时。所以，他想要知道，在所有满足附加条件的序列中，进行冒泡排序的交换次数的最少值是多少。

$n,m\leq 10^6$。

Solution

首先有两个显然的性质：

1. 最终的 $a_i$ 一定是某个 $v_j$，如果不是则调整一定更优。
2. 如果 $i<j,a_i>a_j$，则能交换一定交换。

现在考虑 B 性质怎么做。

这个特殊性质是有一些位置已经确定，那么我们从前往后枚举 $a_i$，用线段树维护当前位置取每个值与一开始已经确定的位置的贡献最小值。每次选择最小值即可。由于修改过程长这样：

sgt.update(1, 1, n, a[i] + 1, n, -1);
sgt.update(1, 1, n, 1, a[i] - 1, 1);

所以每次的最优决策单调不降，也就没有一开始没有确定的点之间的贡献了，答案也就达到了最小。

---

然后考虑 C 性质怎么做。

这个特殊性质是说有很多个不交的区间，区间 $[l,r]$ 内的数有个下界 $v$，且 $[l,r]$ 中至少有一个数取到了下界 $v$。

根据性质 2，把 $v$ 放在 $l$ 处一定不劣。那么问题变为有一些确定的位置，没确定的位置都有一个下界，最小化逆序对。

如果直接按照 B 性质的做，由于存在下界，最终选出来的数不一定能够满足没有相互的影响。

我们考虑在从前往后扫的过程中把前面新确定的数的贡献也加进线段树中，每次取当前位置满足下界的最优答案，如果有多个最优的选值最小的那个。

证明就设选出来的是 $x$，如果 $y>x$，那么 $y$ 对前面和后面都不会比 $x$ 更优。如果 $y<x$ 且存在一个让 $y$ 最优的方案，让后面新确定的数在 $[y,x]$ 范围内的都变为 $x$ 一定能够减少后面新确定的贡献。对于当前位置的贡献，由于 $x$ 是当前位置与已经确定的数的贡献最优值，所以当前位置选 $x$ 一定最优。

---

最后是一般情况的做法。

容易发现我们只需要确定每个区间取到下界的位置就行了，上面的做法只依赖于已确定的值和每个位置能取到的下界。

先设 $b_i$ 表示位置 $i$ 的下界，那么对于一个限制 $(l,r,v)$，要找到一个 $i\in[l,r]$ 且 $b_i=v$ 的去钦定答案。

对每个 $b_i$ 维护一个 set，然后按照 $l$ 从大到小地确定，如果已经有 $[l,r]$ 内且钦定为 $v$ 的了就不用管，否则选择大于等于 $l$ 的且最小的 $b_i=v$ 的位置钦定即可。

时间复杂度：$O((n+m)\log n)$。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e6 + 5;

int n, m, mm, ans;
int a[kMaxN], lim[kMaxN], l[kMaxN], r[kMaxN], v[kMaxN], unq[kMaxN];
std::set<int> st1[kMaxN], st2[kMaxN];

struct BIT {
  int c[kMaxN];
  void clear() { std::fill_n(c + 1, n, 0); }
  void upd(int x, int v) {
    for (; x <= n; x += x & -x) c[x] += v;
  }
  int qry(int x) {
    int ret = 0;
    for (; x; x -= x & -x) ret += c[x];
    return ret;
  }
} bit;

struct SGT {
  std::pair<int, int> mi[kMaxN * 4];
  int tag[kMaxN * 4];
  void pushup(int x) { mi[x] = std::min(mi[x << 1], mi[x << 1 | 1]); }
  void addtag(int x, int v) { mi[x].first += v, tag[x] += v; }
  void pushdown(int x) {
    if (tag[x]) addtag(x << 1, tag[x]), addtag(x << 1 | 1, tag[x]), tag[x] = 0;
  }
  void build(int x, int l, int r) {
    mi[x] = {0, l}, tag[x] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
  }
  void update(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql) return;
    else if (l >= ql && r <= qr) return addtag(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update(x << 1, l, mid, ql, qr, v), update(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }
  std::pair<int, int> query(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql) return {(int)1e9, 0};
    else if (l >= ql && r <= qr) return mi[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    return std::min(query(x << 1, l, mid, ql, qr), query(x << 1 | 1, mid + 1, r, ql, qr));
  }
} sgt;

void discrete() {
  for (int i = 1; i <= m; ++i) unq[i] = v[i];
  std::sort(unq + 1, unq + 1 + m);
  mm = std::unique(unq + 1, unq + 1 + m) - (unq + 1);
  for (int i = 1; i <= m; ++i) {
    v[i] = std::lower_bound(unq + 1, unq + 1 + mm, v[i]) - unq;
  }
}

void getlim() {
  std::vector<int> vec;
  for (int i = 1; i <= m; ++i) vec.emplace_back(i);
  std::sort(vec.begin(), vec.end(), [&] (int i, int j) { return v[i] > v[j]; });
  std::set<int> st;
  for (int i = 1; i <= n; ++i) st.emplace(i);
  for (auto i : vec) {
    for (auto it = st.lower_bound(l[i]); it != st.end() && *it <= r[i]; it = st.lower_bound(l[i])) {
      lim[*it] = v[i], st.erase(it);
    }
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  std::fill_n(a + 1, n, -1);
  std::fill_n(lim + 1, n, 1);
  for (int i = 1; i <= m; ++i) std::cin >> l[i] >> r[i] >> v[i];
  discrete(), getlim();
  // for (int i = 1; i <= m; ++i) {
  //   for (int j = l[i]; j <= r[i]; ++j)
  //     lim[j] = std::max(lim[j], v[i]);
  // }
  std::vector<int> vec;
  for (int i = 1; i <= m; ++i) vec.emplace_back(i);
  std::sort(vec.begin(), vec.end(), [&] (int i, int j) { return l[i] > l[j]; });
  for (int i = 1; i <= n; ++i) st1[i].clear(), st2[i].clear();
  for (int i = 1; i <= n; ++i) st1[lim[i]].emplace(i);
  for (auto i : vec) {
    // bool fl = 0;
    // for (int j = l[i]; j <= r[i]; ++j) {
    //   if (a[j] == v[i]) {
    //     fl = 1; break;
    //   }
    // }
    // if (!fl) {
    //   for (int j = l[i]; j <= r[i]; ++j) {
    //     if (lim[j] == v[i]) {
    //       a[j] = v[i], fl = 1; break;
    //     }
    //   }
    //   if (!fl) return void(std::cout << "-1\n");
    // }
    auto it1 = st1[v[i]].lower_bound(l[i]);
    auto it2 = st2[v[i]].lower_bound(l[i]);
    if (it2 != st2[v[i]].end() && *it2 <= r[i]) continue;
    if (it1 != st1[v[i]].end() && *it1 <= r[i]) {
      a[*it1] = v[i], st2[v[i]].emplace(*it1), st1[v[i]].erase(it1);
    } else {
      return void(std::cout << "-1\n");
    }
  }
  sgt.build(1, 1, n);
  for (int i = 1; i <= n; ++i)
    if (a[i] != -1)
      sgt.update(1, 1, n, a[i] + 1, n, 1);
  for (int i = 1; i <= n; ++i) {
    if (a[i] == -1) {
      a[i] = sgt.query(1, 1, n, lim[i], n).second;
      sgt.update(1, 1, n, 1, a[i] - 1, 1);
    } else {
      sgt.update(1, 1, n, a[i] + 1, n, -1);
      sgt.update(1, 1, n, 1, a[i] - 1, 1);
    }
    // std::cerr << i << ' ' << a[i] << ' ' << lim[i] << ' ' << mm << '\n';
  }
  bit.clear();
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans += bit.qry(n) - bit.qry(a[i]);
    bit.upd(a[i], 1);
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}