「集训队互测2018」完美的队列

2020 年 08 月 08 日

你有 $n$ 个队列，每个队列有 $a_i$ 的容量。

$Q$ 次操作，每次给定队列的区间 $[l,r]$ ，push 一个 $x$ 。如果第 $i$ 个队列的元素个数 $>a_i$ ，会自动 pop。

要求每次操作后求出所有序列中本质不同的元素个数。

$n,m,a_i,x \leq 10^5$ 。

题解

建出线段树，那么一个区间操作 $[l,r]$ 能恰好覆盖 $O(\log n)$ 条线段。对于每条线段，考虑统计操作加入的点何时被完全移出该区间。

由于我们只把完全覆盖该线段的操作丢入改线段处理，那么操作的进入和弹出符合单调队列的性质，我们通过一条线段维护。每次对线段进行修改后，我们不断判断并弹出队列头即可保证复杂度。

那么如何判断呢，考虑一个操作插入一条线段 $[l;r]$ 时，初始的限制是形如这一段 $a_{l\ldots r}$ 。进行别的操作经过这条线段时就是把限制的区间或整体 $-1$ 。如果限制全部 $\leq 0$ ，这次操作添加的所有元素被完全弹出改线段对应的队列中。

显然对于每一个（操作，线段）二元组开线段树维护限制，注意到前面说的单调队列性质，一个操作在固定线段上，影响限制的操作可以看做是经过该线段所形成的操作序列的一个区间。我们对线段开线段树（哎妈呀真绕），刚说的操作序列区间的左右端点都是单调增的，维护较为平凡。

还有个复杂度上的小问题，对于每次操作，恰好覆盖一条线段的时候我们就 return 了，而对于该线段树节点的子树内单调队列，可能是有贡献的。需要维护单调队列距离下次弹出需要的懒标记个数，也是较为平凡的。

代码

// n log^2 n solution
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N * 40;
int n, m, tot, nod, ans, a[N], col[N], lc[M], rc[M], val[M], tag[M];
inline void up(int u, int x) { val[u] += x, tag[u] += x; }
inline void down(int u) {
  if (tag[u]) up(lc[u], tag[u]), up(rc[u], tag[u]), tag[u] = 0;
}
void build(int &u, int l, int r) {
  u = ++tot;
  if (l == r) {
    val[u] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(lc[u], l, mid);
  build(rc[u], mid + 1, r);
  val[u] = max(val[lc[u]], val[rc[u]]);
}
void modify(int u, int ql, int qr, int x, int l, int r) {
  down(u);
  if (ql == l && qr == r) {
    up(u, x);
    return;
  }
  int mid = (l + r) >> 1;
  if (qr <= mid) {
    modify(lc[u], ql, qr, x, l, mid);
  } else if (ql > mid) {
    modify(rc[u], ql, qr, x, mid + 1, r);
  } else {
    modify(lc[u], ql, mid, x, l, mid);
    modify(rc[u], mid + 1, qr, x, mid + 1, r);
  }
  val[u] = max(val[lc[u]], val[rc[u]]);
}
struct segment {
  int l, r, mid, rt, d, k, tag, lc, rc;
  pair<int, int> todo, item;
  queue<tuple<int, int, int>> q;
  vector<pair<int, int>> opt;
} p[N << 1];
inline void pushup(int u, int x) { p[u].d += x, p[u].tag += x, p[u].todo.first -= x; }
inline void pushdown(int u) {
  if (p[u].tag && p[u].l != p[u].r) {
    pushup(p[u].lc, p[u].tag);
    pushup(p[u].rc, p[u].tag);
    p[u].tag = 0;
  }
}
inline void maintain(int u) {
  p[u].todo = p[u].item;
  if (p[u].l != p[u].r) {
    pushdown(u);
    if (p[p[u].lc].todo.first < p[u].todo.first) p[u].todo = p[p[u].lc].todo;
    if (p[p[u].rc].todo.first < p[u].todo.first) p[u].todo = p[p[u].rc].todo;
  }
}
int build(int l, int r) {
  int u = ++nod;
  p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
  build(p[u].rt, l, r);
  p[u].item = p[u].todo = {114514, u};
  if (l != r) {
    p[u].lc = build(l, p[u].mid);
    p[u].rc = build(p[u].mid + 1, r);
  }
  return u;
}
void update(int u) {
  static int c, k, d, l, r;
  while (p[u].q.size()) {
    tie(c, k, d) = p[u].q.front();
    while (p[u].k < k) {
      tie(l, r) = p[u].opt[p[u].k++];
      modify(p[u].rt, l, r, 1, p[u].l, p[u].r);
    }
    if (p[u].d - d >= val[p[u].rt]) {
      col[c]--, ans -= !col[c];
      p[u].q.pop();
    } else {
      p[u].item = {val[p[u].rt] + d - p[u].d, u};
      maintain(u);
      return;
    }
  }
  p[u].item = {114514, u};
  maintain(u);
}
void modify(int u, int l, int r, int c) {
  if (p[u].l == l && p[u].r == r) {
    ans += !col[c], col[c]++;
    pushup(u, 1);
    p[u].q.push({c, (int)p[u].opt.size(), p[u].d});
  } else {
    pushdown(u);
    p[u].opt.push_back({l, r});
    modify(p[u].rt, l, r, -1, p[u].l, p[u].r);
    if (r <= p[u].mid) modify(p[u].lc, l, r, c);
    else if (l > p[u].mid)
      modify(p[u].rc, l, r, c);
    else
      modify(p[u].lc, l, p[u].mid, c), modify(p[u].rc, p[u].mid + 1, r, c);
    maintain(u);
  }
  update(u);
}
void resolve(int u, int v) {
  pushdown(u);
  if (u == v) {
    update(u);
    return;
  }
  resolve(p[v].r <= p[u].mid ? p[u].lc : p[u].rc, v);
  update(u);
  maintain(u);
}
int main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  build(1, n);
  for (int i = 1, l, r, x; i <= m; i++) {
    cin >> l >> r >> x;
    modify(1, l, r, x);
    while (!p[1].todo.first) resolve(1, p[1].todo.second);
    cout << ans << '\n';
  }
}

TABLE OF CONTENTS

题解

代码

题解

代码

评论