• Upd on 2022.9.5：换成可以在 UOJ 上 通过 的代码。

D2T2. P8500 [NOI2022] 冒泡排序

我太爱这道题目了！

首先对题目进行初步观察：

• 冒泡排序交换次数就是逆序对数，只能说这个皮套得很离谱。
• $V_i$ 可以离散化，因为在最终方案中若存在 $a_i$ 不等于任何 $V_j$，则将其调整到大于它的最小的 $V_j$ 或小于它的最大的 $V_j$ 均不使得逆序对数量变多。

受到 P4229 某位歌姬的故事 的影响，我在考场上以为这题是神仙 DP 题，不会做，摆烂了。但仔细想想就会发现 P4229 只要考虑最后一个满足条件的位置，但是本题逆序对数需要考虑当前位置和之前所有位置产生的联合贡献，看起来不太能做。

从部分分入手，这题部分分设置得真好。

考虑 特殊性质 B。除去无解的情况，一些位置的值已经固定，其余位置可以任意取值。

性质 1：任意取值的位置必然不产生逆序对。

证明：若 $i < j$ 且 $a_i > a_j$，交换 $a_i, a_j$ 显然不劣。

据此，从后往前枚举所有任意取值的位置 $i$，每次选择使得与固定取值位置之间贡献最少的值作为 $a_i$。设 $c_v$ 表示当前位置选择 $v$ 产生的贡献，则 $a_i = \mathrm{argmin}_{v = 1} ^ m c_v$。这样决策 $a_i$，可证任意取值位置之间不产生逆序对：从后往前扫的过程中，若遇到固定取值位置 $j$，则我们的操作是将 $c$ $[1, a_j - 1]$ 区间减 $1$，$[a_j + 1, m]$ 区间加 $1$，因此若 $i < j$ 且 $c_i \leq c_j$，那么接下来任意时刻均有 $c_i\leq c_j$，因此具有 决策单调性。

注意尽管具有决策单调性，但 $c$ 不具有凸性，不可以直接用指针维护。用线段树区间加全局 $\mathrm{argmin}$ 维护 $c$ 即可 $\mathcal{O}(n\log n)$ 性质 B。代码。

进一步地，考虑 特殊性质 C。限制相对独立，我们找一些贪心思想。逆序对数相关，我们希望 较小的数尽可能排在前面。这就启发我们得到如下结论：对于限制 $(l, r, V)$，将 $V$ 尽可能往前放，即必然有 $a_l = V$。因为观察 $a_l \sim a_r$，如果 $a_l > V$，那么必然存在 $p\in (l, r]$ 满足 $a_p = V$，$a_l$ 与 $a_p$ 之间形成逆序对，交换更优。这样一来，恰好等于 的要求就被搞定了，$(l, r, V)$ 对 $a_{l + 1}\sim a_r$ 的限制仅仅是不小于 $V$。

借鉴性质 B 的思路，我们有如下算法：设 $b_i$ 表示 $a_i$ 被限制 $\geq b_i$。对于所有限制 $(l, r, V)$，将 $c_1 \sim c_{V - 1}$ 区间加上 $r - l + 1$，表示如果选择小于 $V$ 的数，则会和 $a_l \sim a_r$ 形成 $r - l + 1$ 个逆序对，并令 $b_i\gets V(i\in [l, r])$。仍然从后往前考虑所有位置，对于位置 $i$，若其被限制 $\geq b_i$，则将 $c_1\sim c_{b_i - 1}$ 区间减 $1$，这和性质 B 一样。接下来，若 $a_i$ 还没有被固定取值，即 $i$ 不是某限制的 $l$，则令 $a_i = \mathrm{argmin}_{v = b_i} ^ m c_v$。注意这里不是令 $a_i$ 为全局 $\mathrm{argmin}$ 再和 $b_i$ 取 $\max$，因为 $c$ 没有凸性，我在考场上这么写过不了样例 5，以为是结论假了，寄。最后令 $c_{a_i + 1} \sim c_r$ 区间加 $1$，意义显然。时间复杂度 $\mathcal{O}(n\log n)$。代码。

这个做法正确性证明有点难，大家根据性质 B 做法感性理解即可。

接下来考虑 特殊性质 A。若 $V = 1$，显然 $a_l\sim a_r$ 均为 $1$，否则将所有 $V = 0$ 的限制拎出来，仍然是从后往前考虑所有位置。因为我们希望较小的数尽可能排在前面，所以我们 当且仅当再不放 $0$ 就会出现无解的时候，我们才选择固定当前位为 $0$，这其实和性质 C 的贪心有异曲同工之妙。贪心过程容易维护：

• 进行处理使得区间不相互包含（但注意若 $I_1 \subseteq I_2$，那么是 $I_1$ 限制更紧，要保留 $I_1$ 而非 $I_2$），然后用指针维护最后一个未满足的区间，扫一遍所有未被填入 $1$ 的位置。
• 或者将所有区间按照左端点从大到小排序后考虑，用 set 维护已经选中和未被选中的位置。若不存在已经选中的位置属于 $I$ 则在未被选中的位置集合中查询 $l$ 的后继，若不存在或大于 $r$ 则无解，否则选中该后继。

固定一些位置等于 $0$ 之后做一遍特殊性质 B 即可。时间复杂度 $\mathcal{O}(n\log n)$。

贪心正确性证明：考虑 $V = 0$ 的限制区间集 $S$，考虑左端点最大的任意限制 $I\in S$，我们在 $l_I$ 处固定 $a_{l_I} = 0$。因为不存在左端点比 $I$ 更靠右的区间，再根据 $I$ 的限制，在 $\geq l_I$ 的位置必须至少一个位置固定为 $0$，而选择 $l_I$ 可以让尽可能多的其它区间被满足，选择其它位置通过调整总是不优于选择 $l_I$，证毕。

正解考虑结合特殊性质 A 和特殊性质 C 的做法，对每个值 $v$，将所有 $b_i = v$ 的位置拎出来（$b_i > v$ 的位置不能放 $v$），所有 $V = v$ 的限制区间拎出来，对这些位置和区间做性质 A，最终得到一些已经固定的 $a$，结合 $b_i$ 做性质 C 即可。时间复杂度 $\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
namespace IO {
  char buf[1 << 21], *p1 = buf, *p2 = buf;
  #define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
  inline int read() {
    int x = 0; bool sgn = 0; char s = gc;
    while(!isdigit(s)) sgn |= s == '-', s = gc;
    while(isdigit(s)) x = x * 10 + s - '0', s = gc;
    return sgn ? -x : x;
  }
}
using namespace IO;
bool Mbe;
constexpr int N = 1e6 + 5;
int n, m, d[N], fa[N], val[N], low[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
struct BIT {
  int c[N];
  void clear() {for(int i = 1; i <= m; i++) c[i] = 0;}
  void add(int x, int v) {while(x) c[x] += v, x -= x & -x;}
  int query(int x) {int s = 0; while(x <= m) s += c[x], x += x & -x; return s;}
} tr;
struct limit {
  int l, r, v;
} c[N];
set<int> pos[N];
vector<limit> buc[N];
struct Segtree1 {
  struct dat {
    int mn, pos;
    dat operator + (const dat &x) const { // ensure that pos < x.pos
      return mn <= x.mn ? *this : x;
    }
  } val[N << 2];
  int laz[N << 2];
  void build(int l, int r, int x) {
    laz[x] = 0;
    if(l == r) return val[x] = {0, l}, void();
    int m = l + r >> 1;
    build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
    val[x] = val[x << 1] + val[x << 1 | 1];
  }
  void tag(int x, int v) {val[x].mn += v, laz[x] += v;}
  void down(int x) {
    if(laz[x]) {
      tag(x << 1, laz[x]);
      tag(x << 1 | 1, laz[x]);
      laz[x] = 0;
    }
  }
  void modify(int l, int r, int ql, int qr, int x, int v) {
    if(ql > qr) return;
    if(ql <= l && r <= qr) return tag(x, v);
    int m = l + r >> 1;
    down(x);
    if(ql <= m) modify(l, m, ql, qr, x << 1, v);
    if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
    val[x] = val[x << 1] + val[x << 1 | 1];
  }
  dat query(int l, int r, int ql, int qr, int x) {
    if(ql <= l && r <= qr) return val[x];
    int m = l + r >> 1;
    down(x);
    dat ans = {N, 0};
    if(ql <= m) ans = ans + query(l, m, ql, qr, x << 1);
    if(m < qr) ans = ans + query(m + 1, r, ql, qr, x << 1 | 1);
    return ans;
  }
} sgt1;
void solve() {
  n = read(), m = read();
  for(int i = 1; i <= n + 1; i++) fa[i] = i, val[i] = low[i] = 0;
  for(int i = 1; i <= m; i++) {
    c[i].l = read(), c[i].r = read();
    d[i] = c[i].v = read();
  }
  sort(d + 1, d + m + 1);
  for(int i = 1; i <= m; i++) c[i].v = lower_bound(d + 1, d + m + 1, c[i].v) - d;
  for(int i = 1; i <= m; i++) buc[i].clear(), pos[i].clear();
  for(int i = 1; i <= m; i++) buc[c[i].v].push_back(c[i]);
  for(int i = m; i; i--)
    for(auto it : buc[i]) {
      while(1) {
        int p = find(it.l);
        if(p > it.r) break;
        fa[p] = p + 1, low[p] = i, pos[i].insert(p);
      }
    }
  for(int i = 1; i <= m; i++) {
    sort(buc[i].begin(), buc[i].end(), [&](limit x, limit y) {return x.l > y.l;});
    set<int> settle;
    for(auto it : buc[i]) {
      auto pt = settle.lower_bound(it.l);
      if(pt != settle.end() && *pt <= it.r) continue;
      pt = pos[i].lower_bound(it.l);
      if(pt == pos[i].end() || *pt > it.r) return puts("-1"), void();
      settle.insert(*pt);
      val[*pt] = i;
      pos[i].erase(pt);
    }
  }
  sgt1.build(1, m, 1);
  for(int i = 1; i <= n; i++) if(low[i]) sgt1.modify(1, m, 1, low[i] - 1, 1, 1);
  for(int i = n; i; i--) {
    if(low[i]) sgt1.modify(1, m, 1, low[i] - 1, 1, -1);
    if(!val[i]) val[i] = sgt1.query(1, m, low[i], m, 1).pos;
    sgt1.modify(1, m, val[i] + 1, m, 1, 1);
  }
  ll ans = 0;
  tr.clear();
  for(int i = 1; i <= n; i++) ans += tr.query(val[i] + 1), tr.add(val[i], 1);
  cout << ans << "\n";
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("bubble6.in", "r", stdin);
    FILE* OUT = freopen("e.out", "w", stdout);
  #endif
  int T;
  cin >> T;
  while(T--) solve();
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/8/29
author: Alex_Wei
start coding at 16:34
finish debugging at 20:20
*/