排序

题意概述

给定一个$1$到$n$的全排列。有$m$次操作,每次操作将第$l$项到第$r$项之间的数按升序或降序排序。求所有操作完成后第$q$项的值。
数据范围:$1 \le n, m \le 10^5$。

算法分析

用set维护所有有序的区间,每个区间用一棵权值线段树来维护。这样就把排序操作变成了区间的分裂与合并(即线段树的分裂与合并)。
看起来线段树的复杂度很玄学,但可以大致证明一下:

初始时,线段树有$O(n\log n)$个节点。
分裂操作需要找到第$k$大的数,并把路径上的节点拆到两棵树上。一次分裂操作的时间复杂度为$O(\log n)$,新增节点数为$O(\log n)$。
合并操作每调用一次,都会删除一个节点。因此合并操作的总时间复杂度与最大点数相关,为$O((n+m)\log n)$。

由此得证。

代码

/*
 * Try to have as good a life as you can under the circumstances.
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

static int const N = 100005;
static int const NM = 5000000;
int rt[N], top, buf[NM];
struct Interval {
  int l, r, ord;
  bool operator<(Interval const &a) const { return l < a.l; }
};
std::set<Interval> st;
struct SegmentTree {
  int ch[2], val, sum;
} nd[NM];

void update(int rt) {
  nd[rt].sum = nd[nd[rt].ch[0]].sum + nd[rt].val + nd[nd[rt].ch[1]].sum;
}

void insert(int &rt, int nl, int nr, int p) {
  if (!rt)
    nd[rt = buf[--top]] = nd[0];
  if (nl == nr) {
    nd[rt].val = nd[rt].sum = 1;
    return;
  }
  int mid = nl + nr >> 1;
  if (p <= mid)
    insert(nd[rt].ch[0], nl, mid, p);
  else
    insert(nd[rt].ch[1], mid + 1, nr, p);
  update(rt);
}

void merge(int &p, int &q) {
  if (!p || !q) {
    p = p + q, q = 0;
    return;
  }
  merge(nd[p].ch[0], nd[q].ch[0]), merge(nd[p].ch[1], nd[q].ch[1]);
  buf[top++] = q, q = 0, update(p);
}

int split(int &rt, int k) {
  if (!rt || nd[rt].sum == k)
    return 0;
  if (!k) {
    int rec = rt;
    return rt = 0, rec;
  }
  if (nd[nd[rt].ch[0]].sum >= k) {
    int sp = buf[--top];
    nd[sp].ch[0] = split(nd[rt].ch[0], k), nd[sp].ch[1] = nd[rt].ch[1],
    nd[rt].ch[1] = 0;
    return update(rt), update(sp), sp;
  }
  int sp = buf[--top];
  nd[sp].ch[0] = 0,
  nd[sp].ch[1] = split(nd[rt].ch[1], k - nd[nd[rt].ch[0]].sum);
  return update(rt), update(sp), sp;
}

int query(int rt, int nl, int nr, int k) {
  if (nl == nr)
    return nl;
  int mid = nl + nr >> 1;
  if (nd[nd[rt].ch[0]].sum >= k)
    return query(nd[rt].ch[0], nl, mid, k);
  else
    return query(nd[rt].ch[1], mid + 1, nr, k - nd[nd[rt].ch[0]].sum);
}

int main() {
  for (int i = 1; i < NM; ++i)
    buf[top++] = i;
  int n, m, q;
  scanf("%d%d", &n, &m);
  for (int i = 1, t; i <= n; ++i)
    scanf("%d", &t), insert(rt[i], 1, n, t), st.insert((Interval){i, i, 0});
  for (; m--;) {
    int op, l, r;
    scanf("%d%d%d", &op, &l, &r);
    std::set<Interval>::iterator L = st.upper_bound((Interval){l}),
                                 R = st.upper_bound((Interval){r});
    Interval recl = *(--L), recr = *(--R);
    if (L->l < l)
      if (L->ord == 0)
        rt[l] = split(rt[L->l], l - L->l);
      else
        rt[l] = split(rt[L->l], L->r - l + 1), std::swap(rt[l], rt[L->l]);
    if (L != R) {
      st.erase(L++);
      for (; L != R; st.erase(L++))
        merge(rt[l], rt[L->l]);
      if (r < R->r)
        if (R->ord == 0)
          rt[r + 1] = split(rt[R->l], r - R->l + 1);
        else
          rt[r + 1] = split(rt[R->l], R->r - r), std::swap(rt[r + 1], rt[R->l]);
      merge(rt[l], rt[R->l]);
    } else if (r < R->r)
      if (R->ord == 0)
        rt[r + 1] = split(rt[l], r - l + 1);
      else
        rt[r + 1] = split(rt[l], R->r - r), std::swap(rt[r + 1], rt[l]);
    st.erase(R), st.insert((Interval){l, r, op});
    if (recl.l < l)
      st.insert((Interval){recl.l, l - 1, recl.ord});
    if (r < recr.r)
      st.insert((Interval){r + 1, recr.r, recr.ord});
  }
  scanf("%d", &q);
  for (std::set<Interval>::iterator it = st.begin(); it != st.end(); ++it)
    if (q <= nd[rt[it->l]].sum) {
      if (it->ord == 0)
        printf("%d\n", query(rt[it->l], 1, n, q));
      else
        printf("%d\n", query(rt[it->l], 1, n, nd[rt[it->l]].sum - q + 1));
      break;
    } else
      q -= nd[rt[it->l]].sum;
  return 0;
}

Dynamic Rankings

题目描述

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the $k$-th smallest number of the given $N$ numbers. They have developed a more powerful system such that for $N$ numbers $a_1, a_2, \ldots, a_N$, you can ask it like: what is the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$? (For some $i \le j$, $0 \lt k \le j+1-i$ that you have given to it). More powerful, you can even change the value of some $a_i$, and continue to query, all the same.
Your task is to write a program for this computer, which

  • Reads $N$ numbers from the input.
  • Processes $M$ instructions of the input. These instructions include querying the $k$-th smallest number of $a_i, a_{i+1}, \ldots, a_j$ and change some $a_i$ to $t$.

题意概述

有一个长度为$N$的数列。有$M$次操作,每次操作询问数列第$i$项到第$j$项之间的第$k$小值,或者将第$i$项修改为$t$。
数据范围:$1 \le N \le 50000, \; 1 \le M \le 10000$。
内存限制:$32$M。

算法分析

对于这种询问区间第$k$小值的题目,很容易想到主席树。但由于主席树是一种类似前缀和的结构,一次修改操作需要修改$O(N)$棵线段树。这显然不是我们所希望的。
既然主席树类似前缀和,那么就可以借用维护前缀和的工具——树状数组。把树状数组的每个节点看成一棵线段树,这样一次修改操作就只需要修改$O(\log N)$棵线段树,时间复杂度为$O(\log^2N)$。而询问操作需要先把该询问在树状数组上用到的节点提取出来(有$O(\log N)$个),然后利用类似主席树的方法二分,时间复杂度也是$O(\log^2N)$。
但是!这题的内存限制非常小,接受不了$O((N+M)\log^2N)$的空间复杂度。再考虑主席树,它的空间复杂度是$O(N\log N)$的。因此可以对原序列建立静态的主席树,对修改操作利用树状数组维护,这样空间复杂度降至$O(N\log N+M\log^2N)$,可以通过。

代码

/*
 * Beware of Bigfoot!
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>

static int const N = 60005;
static int const NM = 2000000;
int n, m, nn, a[N], arr_rt[N], bit_rt[N], rec[N];
struct Query {
  int o, i, j, k;
} q[N];
struct SegmentTree {
  int ch[2], sum;
} nd[NM];

int create(int rt = 0) { return nd[++nn] = nd[rt], nn; }

int arr_insert(int rt, int p) {
  rt = create(rt), ++nd[rt].sum;
  int L = 0, R = N;
  for (int cur = rt; L < R;) {
    int MID = L + R >> 1, b = p > MID;
    nd[cur].ch[b] = create(nd[cur].ch[b]), ++nd[nd[cur].ch[b]].sum,
    cur = nd[cur].ch[b];
    b ? L = MID + 1 : R = MID;
  }
  return rt;
}

void bit_insert(int &rt, int p, int v) {
  if (rt == 0)
    rt = create();
  nd[rt].sum += v;
  int L = 0, R = N;
  for (int cur = rt; L < R;) {
    int MID = L + R >> 1, b = p > MID;
    if (nd[cur].ch[b] == 0)
      nd[cur].ch[b] = create();
    nd[nd[cur].ch[b]].sum += v;
    int tmp = nd[cur].ch[b];
    cur = tmp, b ? L = MID + 1 : R = MID;
  }
}

int bit_add(int p, int v, int c) {
  for (; p <= n; p += p & -p)
    bit_insert(bit_rt[p], v, c);
}

int main() {
  int T;
  scanf("%d", &T);
  for (; T--;) {
    std::map<int, int> mp;
    memset(arr_rt, nn = 0, sizeof arr_rt), memset(bit_rt, 0, sizeof bit_rt);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
      scanf("%d", &a[i]), mp[a[i]] = 0;
    for (int i = 1; i <= m; ++i) {
      char c;
      scanf(" %c", &c);
      if (c == 'Q')
        q[i].o = 0, scanf("%d%d%d", &q[i].i, &q[i].j, &q[i].k);
      else
        q[i].o = 1, scanf("%d%d", &q[i].i, &q[i].j), mp[q[i].j] = 0;
    }
    int cnt = 0;
    for (std::map<int, int>::iterator it = mp.begin(); it != mp.end(); ++it)
      rec[cnt] = it->first, it->second = cnt++;
    for (int i = 1; i <= n; ++i)
      arr_rt[i] = arr_insert(arr_rt[i - 1], mp[a[i]]);
    for (int i = 1; i <= m; ++i) {
      if (q[i].o == 0) {
        std::vector<int> a, b;
        a.push_back(arr_rt[q[i].i - 1]), b.push_back(arr_rt[q[i].j]);
        for (int p = q[i].i - 1; p; p -= p & -p)
          a.push_back(bit_rt[p]);
        for (int p = q[i].j; p; p -= p & -p)
          b.push_back(bit_rt[p]);
        int L = 0, R = N;
        for (; L < R;) {
          int sum = 0;
          for (int i = 0; i < a.size(); ++i)
            sum -= nd[nd[a[i]].ch[0]].sum;
          for (int i = 0; i < b.size(); ++i)
            sum += nd[nd[b[i]].ch[0]].sum;
          int MID = L + R >> 1;
          if (sum < q[i].k) {
            L = MID + 1, q[i].k -= sum;
            for (int i = 0; i < a.size(); ++i)
              a[i] = nd[a[i]].ch[1];
            for (int i = 0; i < b.size(); ++i)
              b[i] = nd[b[i]].ch[1];
          } else {
            R = MID;
            for (int i = 0; i < a.size(); ++i)
              a[i] = nd[a[i]].ch[0];
            for (int i = 0; i < b.size(); ++i)
              b[i] = nd[b[i]].ch[0];
          }
        }
        printf("%d\n", rec[L]);
      } else
        bit_add(q[i].i, mp[a[q[i].i]], -1),
            bit_add(q[i].i, mp[a[q[i].i] = q[i].j], 1);
    }
  }
  return 0;
}

Little Pony and Lord Tirek

题目描述

Lord Tirek is a centaur and the main antagonist in the season four finale episodes in the series “My Little Pony: Friendship Is Magic”. In “Twilight’s Kingdom” (Part 1), Tirek escapes from Tartarus and drains magic from ponies to grow stronger.
The core skill of Tirek is called Absorb Mana. It takes all mana from a magic creature and gives them to the caster.
Now to simplify the problem, assume you have $n$ ponies (numbered from $1$ to $n$). Each pony has three attributes:

  • $s_i$: amount of mana that the pony has at time $0$;
  • $m_i$: maximum mana that the pony can have;
  • $r_i$: mana regeneration per unit time.

Lord Tirek will do $m$ instructions, each of them can be described with three integers: $t_i, l_i, r_i$. The instruction means that at time $t_i$, Tirek will use Absorb Mana on ponies with numbers from $l_i$ to $r_i$ (both borders inclusive). We’ll give you all the m instructions in order, count how much mana Tirek absorbs for each instruction.

题意概述

有$n$匹马,第$i$匹马初始时有$s_i$点魔法,魔法上限为$m_i$,每秒增加$r_i$点魔法。有$m$次操作,第$i$次操作在第$t_i$秒进行,将区间$[l_i, r_i]$中马的魔法清零。求每次操作清除了多少点魔法。
数据范围:$1 \le n, m \le 10^5, \; 0 \le s_i \le m_i \le 10^5, \; 0 \le r_i \le 10^5, \; 0 \le t_i \le 10^9$。

算法分析

显然,答案只与两次询问的时间差有关。
用set维护一些不相交的区间(它们的并是整个序列),每段区间内所有马的上次操作时间相同。每次操作就相当于切割一些区间然后合并一些区间。由于每次至多切割两个区间,因此总共操作的区间个数是$O(n)$的。
考虑区间询问。每匹马都可以表示为一个分段函数,我们用主席树来维护,第$i$棵线段树表示经过$i$秒后每匹马的函数。因为有些马有初始魔法,所以需要建两棵主席树,一棵表示第$i$匹马的初始魔法为$s_i$,另一棵表示所有马的初始魔法为$0$。
那么只要预处理出主席树,对于每次操作,在set中找到其对应的一些区间,在主席树上询问答案,并更新区间。

代码

/*
 * So, is the glass half empty, half full, or just twice as large as it needs to
 * be?
 */

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>

template <typename T> void read(T &n) {
  char c;
  for (; (c = getchar()) < '0' || c > '9';)
    ;
  for (n = c - '0'; (c = getchar()) >= '0' && c <= '9'; (n *= 10) += c - '0')
    ;
}

typedef long long ll;
typedef int const ic;

static ic N = 100005;
int numn, root[N << 1];
struct Pony {
  int s, m, r;
} p[N];
struct Event {
  int t, p, b;
} e[N];
struct Query {
  int t, l, r;
  bool operator<(Query const &a) const { return l < a.l; }
} q[N];
struct SegmentTree {
  int child[2];
  ll a, b;
} node[N << 6];
std::set<Query> st;

void update(ic &root) {
  if (!root)
    return;
  node[root].a = node[node[root].child[0]].a + node[node[root].child[1]].a;
  node[root].b = node[node[root].child[0]].b + node[node[root].child[1]].b;
}

void modify(int &root, ic &nl, ic &nr, ic &p, ic &a, ic &b, ic &flag) {
  if (p > nr || nl > p)
    return;
  if (flag)
    node[++numn] = node[root], root = numn;
  else if (!root)
    root = ++numn;
  if (nl == nr) {
    node[root].a = a, node[root].b = b;
    return;
  }
  ic mid = (nl + nr) >> 1;
  modify(node[root].child[0], nl, mid, p, a, b, flag);
  modify(node[root].child[1], mid + 1, nr, p, a, b, flag);
  update(root);
}

ll query(ic &root, ic &nl, ic &nr, ic &t, ic &l, ic &r) {
  if (!root || l > nr || nl > r)
    return 0;
  if (l <= nl && nr <= r)
    return node[root].a * t + node[root].b;
  ic mid = (nl + nr) >> 1;
  return query(node[root].child[0], nl, mid, t, l, r) +
         query(node[root].child[1], mid + 1, nr, t, l, r);
}

int main() {
  int n, m;
  read(n);
  for (int i = 0; i < n; ++i)
    read(p[i].s), read(p[i].m), read(p[i].r);
  read(m);
  for (int i = 0; i < m; ++i)
    read(q[i].t), read(q[i].l), read(q[i].r), --q[i].l, --q[i].r;
  for (int i = 0; i < n; ++i)
    modify(root[0], 0, n - 1, i, p[i].r, 0, 0),
        e[i] = (Event){p[i].r ? p[i].m / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[i] = root[i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  for (int i = 0; i < n; ++i)
    modify(root[N], 0, n - 1, i, p[i].r, p[i].s, 0),
        e[i] = (Event){p[i].r ? (p[i].m - p[i].s) / p[i].r + 1 : N, i, p[i].m};
  std::sort(e, e + n, [](Event const &a, Event const &b) { return a.t < b.t; });
  for (int i = 1, p = 0; i < N; ++i) {
    root[N + i] = root[N + i - 1];
    for (; p < n && e[p].t == i; ++p)
      modify(root[N + i], 0, n - 1, e[p].p, 0, e[p].b, 1);
  }
  st.insert((Query){0, 0, n - 1});
  for (int i = 0; i < m; ++i) {
    auto rec = st.lower_bound((Query){q[i].t, q[i].l, q[i].r});
    if (rec == st.end())
      --rec;
    for (; rec != st.begin() && rec->r >= q[i].l; --rec)
      ;
    if (rec->r < q[i].l)
      ++rec;
    auto tmp = rec;
    Query l = (Query){rec->t, rec->l, q[i].l - 1};
    ll ans = 0;
    for (; rec != st.end() && rec->l <= q[i].r; ++rec)
      ans += rec->t ? query(root[std::min(q[i].t - rec->t, N - 1)], 0, n - 1,
                            q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r))
                    : query(root[std::min(q[i].t - rec->t, N - 1) + N], 0,
                            n - 1, q[i].t - rec->t, std::max(rec->l, q[i].l),
                            std::min(rec->r, q[i].r));
    printf("%lld\n", ans), --rec;
    Query r = (Query){rec->t, q[i].r + 1, rec->r};
    for (; tmp != st.end() && tmp->l <= q[i].r;)
      st.erase(tmp++);
    st.insert((Query){q[i].t, q[i].l, q[i].r});
    if (l.l <= l.r)
      st.insert(l);
    if (r.l <= r.r)
      st.insert(r);
  }
  return 0;
}

Destiny

题目描述

Once, Leha found in the left pocket an array consisting of $n$ integers, and in the right pocket $q$ queries of the form $l$ $r$ $k$. If there are queries, then they must be answered. Answer for the query is minimal $x$ such that $x$ occurs in the interval $l$ $r$ strictly more than ${r-l+1 \over k}$ times or $-1$ if there is no such number. Help Leha with such a difficult task.

题意概述

给定包含$n$个数的序列,有$q$次询问,每次询问给定$l, r, k$,求区间$[l, r]$中出现次数严格大于${r-l+1 \over k}$的最小数字。
数据范围:$1 \le n, q \le 3 \times 10^5, \; 1 \le a_i \le n, \; 2 \le k \le 5$。

算法分析

建主席树,第$i$个位置上的线段树是前$i$个数的权值线段树。这样就可以用前缀和思想快速求出区间$[l, r]$中某个数出现的次数。对于每个询问,用第$r$个位置上线段树的值减去第$(l-1)$个位置上线段树的值,直接在主席树上暴力查找。由于$k$比较小,查找复杂度不会太高。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T>
  inline bool read(T &x) {
    char c; bool flag = false; x = 0;
    while (~ c && ! isdigit(c = getchar()) && c != '-') ;
    c == '-' && (flag = true, c = getchar());
    if (! ~ c) return false;
    while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return (flag && (x = -x), true);
  }
  inline bool read(char &c) {
    c = '\n';
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    return ~ c;
  }
  inline int read(char s[]) {
    char c; int len = 0;
    while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
    if (! ~ c) return 0;
    while (isprint(c) && c != ' ') s[len ++] = c, c = getchar();
    return (s[len] = '\0', len);
  }
  template <typename T>
  inline IOManager r(T &x) {
    read(x); return *this;
  }
  template <typename T>
  inline void write(T x) {
    x < 0 && (putchar('-'), x = -x);
    x > 9 && (write(x / 10), true);
    putchar(x % 10 + '0');
  }
  inline void write(char c) {
    putchar(c);
  }
  inline void write(char s[]) {
    int pos = 0;
    while (s[pos] != '\0') putchar(s[pos ++]);
  }
  template <typename T>
  inline IOManager w(T x) {
    write(x); return *this;
  }
} io;

struct SegmentTree {
private:
  static const int N = 9000000;
  int tot;
  struct Node {
    int val, child[2];
  } node[N];
  int add_point(int root, int l, int r, int p) {
    if (l == r) {
      node[++ tot] = (Node) { node[root].val, 0, 0 };
      ++ node[tot].val; return tot;
    }
    int mid = l + r >> 1, rec = ++ tot;
    node[rec] = (Node) { 0, 0, 0 };
    if (p <= mid) {
      node[rec].child[1] = node[root].child[1];
      node[rec].child[0] = add_point(node[root].child[0], l, mid, p);
    } else {
      node[rec].child[0] = node[root].child[0];
      node[rec].child[1] = add_point(node[root].child[1], mid + 1, r, p);
    }
    node[rec].val = node[node[rec].child[0]].val + node[node[rec].child[1]].val;
    return rec;
  }
  int query_point(int root1, int root2, int l, int r, int p) {
    if (node[root2].val - node[root1].val < p) return -1;
    if (l == r) return node[root2].val - node[root1].val >= p ? l : -1;
    int mid = l + r >> 1, res = -1;
    if (node[node[root2].child[0]].val - node[node[root1].child[0]].val >= p)
      res = query_point(node[root1].child[0], node[root2].child[0], l, mid, p);
    if (~ res) return res;
    res = query_point(node[root1].child[1], node[root2].child[1], mid + 1, r, p);
    return res;
  }

public:
  int n, cnt, root[N];
  void add(int p) {
    root[cnt + 1] = add_point(root[cnt], 1, n, p), ++ cnt;
  }
  int find(int l, int r, int p) {
    return query_point(root[l - 1], root[r], 1, n, p);
  }
  void print() {
    cout << cnt << endl;
    for (int i = 1; i <= cnt; ++ i) cout << root[i] << ' ';
    cout << endl << tot << endl;
    for (int i = 1; i <= tot; ++ i) cout << i << ' ' << node[i].val << ' ' << node[i].child[0] << ' ' << node[i].child[1] << endl;
  }
};

struct Solver {
private:
  int n, q;
  SegmentTree tree;
  void input() {
    io.r(n).r(q);
    tree.n = n;
    for (int i = 1; i <= n; ++ i) {
      int t; io.read(t), tree.add(t);
    }
  }
  void process() {
    int l, r, k; io.r(l).r(r).r(k);
    int p = (r - l + 1) / k + 1;
    io.w(tree.find(l, r, p)).w('\n');
  }

public:
  void solve() {
    input(); while (q --) process();
  }
} solver;

int main() {
  solver.solve();
  return 0;
}

Sum of Medians

题目描述

In one well-known algorithm of finding the $k$-th order statistics we should divide all elements into groups of five consecutive elements and find the median of each five. A median is called the middle element of a sorted array (it’s the third largest element for a group of five). To increase the algorithm’s performance speed on a modern video card, you should be able to find a sum of medians in each five of the array.
A sum of medians of a sorted $k$-element set $S={a_1, a_2, \ldots, a_k}$, where $a_1 \lt a_2 \lt a_3 \lt \cdots \lt a_k$, will be understood by as $\sum_{i \bmod 5=3} a_i$.
The $\bmod$ operator stands for taking the remainder, that is $x \bmod y$ stands for the remainder of dividing $x$ by $y$.
To organize exercise testing quickly calculating the sum of medians for a changing set was needed.

题意概述

有一个初始为空的集合。有三种操作:①向集合中加入一个元素,保证操作前这个元素不存在;②从集合中删除一个元素,保证操作前这个元素存在;③询问集合中元素排序后下标模$5$余$3$的元素之和。共有$n$次操作。
数据范围:$1 \le n \le 10^5$。

算法分析1

直接用平衡树来维护。对于每个节点储存它子树的大小以及它子树排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。显然,一个节点的左子树可以直接更新当前节点,而右子树则需根据左子树的大小进行处理后再更新当前节点。

代码1

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
long long n, x;
string o;
struct treap {
  int tot, root;
  struct node_type {
    int child[2], rank;
    long long val, size, mod[5];
  } node[100001];
  void update(int t) {
    node[t].size = node[node[t].child[0]].size + node[node[t].child[1]].size + 1;
    for (int i = 0; i < 5; ++i)
      node[t].mod[i] = node[node[t].child[0]].mod[i] + node[node[t].child[1]].mod[(i + 99999 - node[node[t].child[0]].size) % 5];
    node[t].mod[(node[node[t].child[0]].size + 1) % 5] += node[t].val;
  }
  void rotate(int &t, int dire) {
    int p = node[t].child[!dire];
    node[t].child[!dire] = node[p].child[dire], node[p].child[dire] = t;
    update(t), update(p), t = p;
  }
  void insert(int &t, long long val) {
    if (!t) {
      t = ++tot, node[t].rank = ((rand() & ((1 << 16) - 1)) << 10) ^ rand(), node[t].val = node[t].mod[1] = val, node[t].size = 1;
      return;
    }
    ++node[t].size;
    if (val < node[t].val) {
      insert(node[t].child[0], val);
      if (node[node[t].child[0]].rank > node[t].rank) rotate(t, 1);
    } else {
      insert(node[t].child[1], val);
      if (node[node[t].child[1]].rank > node[t].rank) rotate(t, 0);
    }
    update(t);
  }
  void remove(int &t, long long val) {
    if (!node[t].child[0] && !node[t].child[1]) { t = 0; return; }
    if (val == node[t].val) {
      if (node[node[t].child[0]].rank > node[node[t].child[1]].rank) rotate(t, 1);
      else rotate(t, 0);
    }
    if (val < node[t].val) remove(node[t].child[0], val);
    else remove(node[t].child[1], val);
    update(t);
  }
  long long query() { return node[root].mod[3]; }
} tree;
int main()
{
  srand(time(NULL));
  cin >> n;
  while (n--) {
    cin >> o;
    if (o[0] == 'a') { cin >> x; tree.insert(tree.root, x); }
    else if (o[0] == 'd') { cin >> x; tree.remove(tree.root, x); }
    else cout << tree.query() << endl;
  }
  return 0;
}

算法分析2

将操作离线,并将所有操作数离散化,用线段树来维护离散后的区间。和平衡树类似,对于每个节点储存区间内的元素个数以及区间内的元素排序后下标模$5$余$0$、余$1$、…、余$4$的元素之和。更新操作也大同小异。

DZY Loves Fibonacci Numbers

题目描述

In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:
$$F_1=1, \; F_2=1, \; F_n=F_{n-1}+F_{n-2} \; (n \gt 2)$$
DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of $n$ integers: $a_1, a_2, \ldots, a_n$. Moreover, there are $m$ queries, each query has one of the two types:

  • Format of the query “1 $l$ $r$”. In reply to the query, you need to add $F_{i-l+1}$ to each element $a_i$, where $l \le i \le r$.
  • Format of the query “2 $l$ $r$”. In reply to the query you should output the value of $\sum_{i=l}^r a_i$ modulo $1000000009$ ($10^9+9$).

Help DZY reply to all the queries.

题意概述

给定一个长度为$n$的数列,第$i$个数为$a_i$。有两种操作:①对于$i \in [l, r]$,将$a_i$加上$F_{i-l+1}$;②询问区间$[l, r]$内的数字之和。其中$F_i$表示Fibonacci数列的第$i$项。操作有$m$次。
数据范围:$1 \le n, m \le 3 \times 10^5, \; 1 \le a_i \le 10^9$。

算法分析

在一个Fibonacci数列上加一个Fibonacci数列,其结果仍然是Fibonacci数列。而对于一个Fibonacci数列,只要知道前两个数,就能知道接下来的所有数。可以用线段树来维护,对于每一个节点记录下区间和,以及可以代表这个区间上Fibonacci数列的前两个数。设前两个数分别为$a, b$,预处理出Fibonacci数列每一项$a$和$b$的系数,即可在$O(1)$时间内计算出Fibonacci数列的任意一项。其前缀和亦然。

代码

#include <cstdio>
#include <iostream>
using namespace std;
const long long mod = 1000000009ll;
struct node_type {
  long long l, r, val[2], sum, child[2];
} node[1000001];
long long n, m, o, l, r, tot = 1, a[300001], x[300001][2], y[300001][2];
void build_tree(int root) {
  if (node[root].l == node[root].r) return; long long mid = node[root].l + node[root].r >> 1;
  node[++tot].l = node[root].l, node[tot].r = mid, node[root].child[0] = tot, build_tree(tot);
  node[++tot].l = mid + 1, node[tot].r = node[root].r, node[root].child[1] = tot, build_tree(tot);
}
void push_down(int root) {
  if (node[root].l == node[root].r || node[root].val[0] == 0 && node[root].val[1] == 0) return;
  if (node[node[root].child[0]].l == node[node[root].child[0]].r) node[node[root].child[0]].sum += node[root].val[0];
  else {
    (node[node[root].child[0]].val[0] += node[root].val[0]) %= mod, (node[node[root].child[0]].val[1] += node[root].val[1]) %= mod;
    node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][0] * node[root].val[0] % mod;
    node[node[root].child[0]].sum += y[node[node[root].child[0]].r - node[node[root].child[0]].l + 1][1] * node[root].val[1] % mod;
  }
  long long p = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 2][1] * node[root].val[1]) % mod;
  long long q = (x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][0] * node[root].val[0] + x[node[node[root].child[0]].r - node[node[root].child[0]].l + 3][1] * node[root].val[1]) % mod;
  if (node[node[root].child[1]].l == node[node[root].child[1]].r) node[node[root].child[1]].sum += p;
  else {
    (node[node[root].child[1]].val[0] += p) %= mod, (node[node[root].child[1]].val[1] += q) %= mod;
    node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][0] * p % mod;
    node[node[root].child[1]].sum += y[node[node[root].child[1]].r - node[node[root].child[1]].l + 1][1] * q % mod;
  }
  node[root].val[0] = node[root].val[1] = 0;
}
void push_up(int root) {
  if (node[root].l == node[root].r) return;
  node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum;
}
void insert_line(int root, int l, int r, int val) {
  if (node[root].r < l || node[root].l > r) return;
  if (node[root].l >= l && node[root].r <= r) {
    if (node[root].l == node[root].r) node[root].sum += x[val][0] + x[val][1];
    else {
      (node[root].val[0] += x[val][0] + x[val][1]) %= mod;
      (node[root].val[1] += x[val + 1][0] + x[val + 1][1]) %= mod;
      node[root].sum += y[node[root].r - node[root].l + 1][0] * (x[val][0] + x[val][1]) % mod;
      node[root].sum += y[node[root].r - node[root].l + 1][1] * (x[val + 1][0] + x[val + 1][1]) % mod;
    }
    return;
  }
  push_down(root);
  insert_line(node[root].child[0], l, r, val);
  insert_line(node[root].child[1], l, r, max(1ll, val + node[node[root].child[1]].l - max((long long) l, node[node[root].child[0]].l)));
  push_up(root);
}
long long get_sum(int root, int l, int r) {
  if (node[root].r < l || node[root].l > r) return 0;
  if (node[root].l >= l && node[root].r <= r) return node[root].sum;
  long long ret;
  push_down(root);
  ret = get_sum(node[root].child[0], l, r) + get_sum(node[root].child[1], l, r);
  push_up(root);
  return ret;
}
int main()
{
  scanf("%lld%lld", &n, &m);
  x[1][0] = x[2][1] = y[1][0] = y[2][0] = y[2][1] = 1;
  for (int i = 3; i <= n; ++i) {
    x[i][0] = (x[i - 1][0] + x[i - 2][0]) % mod;
    x[i][1] = (x[i - 1][1] + x[i - 2][1]) % mod;
    y[i][0] = (y[i - 1][0] + x[i][0]) % mod;
    y[i][1] = (y[i - 1][1] + x[i][1]) % mod;
  }
  node[1].l = 1, node[1].r = n, build_tree(1);
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] += a[i - 1];
  while (m--) {
    scanf("%lld%lld%lld", &o, &l, &r);
    if (o == 1) insert_line(1, l, r, 1);
    else printf("%lld\n", ((get_sum(1, l, r) + a[r] - a[l - 1]) % mod + mod) % mod);
  }
  return 0;
}

Maze

题意概述

有$n$个排成一行的传送器,第$i$个传送器可以传送到$[L_i, R_i]$之间的所有传送器上(传送前的身影还在),可以多次传送。你现在随机出生在一个传送器上,求有你身影的传送器个数的期望。

算法分析

首先利用线段树优化建图,使得点数为$O(n)$,边数为$O(n\log n)$。
这是一张有向图。考虑在同一个强连通分量中的两个点,它们的答案一定是一样的。因此可以将图中的强连通分量缩成一个点,对每个强连通分量分别计算答案。

代码

#include <cstdio>
#include <iomanip>
#include <cstring>
using namespace std;
struct node_type {
  int l, r, child[2];
} node[300001];
struct edge {
  int v, c, nxt;
} e[600001];
int n, tot, nume, id, h[300001], que[600001], dfn[300001], low[300001];
int top, sta[300001], cnt, belong[300001], pnt[300001];
long double ans;
bool vis[300001];
void add_edge(int u, int v) {
  if (u == v) return;
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(int root) {
  int mid = node[root].l + node[root].r >> 1;
  if (node[root].l == mid) {
    node[root].child[0] = mid, add_edge(root, mid);
  } else {
    node[++tot].l = node[root].l, node[tot].r = mid;
    node[root].child[0] = tot, add_edge(root, tot), build_tree(tot);
  }
  if (mid + 1 == node[root].r) {
    node[root].child[1] = mid + 1, add_edge(root, mid + 1);
  } else {
    node[++tot].l = mid + 1, node[tot].r = node[root].r;
    node[root].child[1] = tot, add_edge(root, tot), build_tree(tot);
  }
}
void insert_line(int root, int l, int r, int t) {
  if (node[root].l == l && node[root].r == r) {
    add_edge(t, root); return;
  }
  int mid = node[root].l + node[root].r >> 1;
  if (r <= mid) insert_line(node[root].child[0], l, r, t);
  else if (l > mid) insert_line(node[root].child[1], l, r, t);
  else {
    insert_line(node[root].child[0], l, mid, t);
    insert_line(node[root].child[1], mid + 1, r, t);
  }
}
void dfs(int t) {
  dfn[t] = low[t] = ++id;
  sta[++top] = t, vis[t] = true;
  for (int i = h[t]; i; i = e[i].nxt) {
    if (!dfn[e[i].v]) dfs(e[i].v), low[t] = min(low[t], low[e[i].v]);
    else if (vis[e[i].v]) low[t] = min(low[t], dfn[e[i].v]);
  }
  if (dfn[t] == low[t]) {
    int v; ++cnt;
    do belong[v = sta[top--]] = cnt, vis[v] = false; while (v != t);
  }
}
int bfs(int u) {
  memset(vis, false, sizeof(vis));
  int s = 0, t = 0, ret = 1;
  vis[que[++t] = u] = true;
  while (s < t) {
    int v = que[++s];
    for (int i = h[v]; i; i = e[i].nxt) {
      if (!vis[e[i].v]) {
        vis[que[++t] = e[i].v] = true;
        if (e[i].v && e[i].v <= n) ++ret;
      }
    }
  }
  return ret;
}
int main()
{
  scanf("%d", &n); tot = n + 1;
  for (int i = 1; i <= n; ++i) node[i].l = node[i].r = i;
  node[tot].l = 1, node[tot].r = n, build_tree(tot);
  for (int i = 1; i <= n; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    insert_line(n + 1, l, r, i);
  }
  for (int i = 1; i <= tot; ++i) if (!dfn[i]) dfs(i);
  for (int i = 1; i <= n; ++i) {
    if (!pnt[belong[i]]) pnt[belong[i]] = bfs(i);
    ans += pnt[belong[i]];
  }
  printf("%.6llf\n", ans / n);
  return 0;
}

Till I Collapse

题目描述

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated $n$ Mr. Meeseeks, standing in a line numbered from $1$ to $n$. Each of them has his own color. $i$-th Mr. Meeseeks’ color is $a_i$.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most $k$ different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each $1 \le i \le e \le j \le n$, if Mr. Meeseeks number $i$ and Mr. Meeseeks number $j$ are in the same squad then Mr. Meeseeks number $e$ should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of $k$, so in order to choose it, for each $k$ between $1$ and $n$ (inclusive) need to know the minimum number of presidios needed.

题意概述

给定一个长度为$n$的数列,第$i$个数为$a_i$。要求将它们分成若干连续段。对于所有$k \in [1, n]$,问至少分成多少段,使得每一段中数字的种类数不超过$k$。
数据范围:$1 \le a_i \le n \le 10^5$。

算法分析1

有个显然的贪心策略:每一段越长越好。
容易发现答案一定单调不递增。对于$i \le j$,如果$ans_i=ans_j$,那么$ans_i=ans_{i+1}=ans_{i+2}= \cdots =ans_j$。因此我们可以贪心$O(n)$计算出左端点和右端点的$ans$,若它们相等,则将这个区间中的$ans$全都赋成左端点的$ans$;否则,取区间中点,并递归处理左右两个区间。

代码1

#include <cstdio>
#include <cstring>
using namespace std;
int n, last, a[100001], c[100001], ans[100001];
int get(int t) {
  memset(c, 0, sizeof(c));
  int p = 0, q = 1, ret = 0;
  while (q <= n) {
    int cnt = 1; c[a[q]] = 1;
    while (q < n) {
      if (cnt < t || c[a[q + 1]]) {
        cnt += !c[a[++q]], ++c[a[q]];
      } else break;
    }
    while (p < q) --c[a[++p]];
    ++q, ++ret;
  }
  return ret;
}
void solve(int l, int r) {
  if (l > r) return;
  ans[l] = get(l), ans[r] = get(r);
  if (ans[l] == ans[r]) {
    for (int i = l + 1; i < r; ++i) ans[i] = ans[l];
    return;
  }
  int mid = l + r >> 1;
  solve(l + 1, mid), solve(mid + 1, r - 1);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  solve(1, n);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}

算法分析2

建可持久化线段树,第$i$个节点上的线段树维护区间$[j, i]$中数字的种类数。当遇到一个前面已经出现过的数字时,就在前面出现的位置上减一,在当前位置上加一。枚举$k$,并依据上述贪心策略,即可得到答案。

代码2

#include <cstdio>
using namespace std;
struct node_type {
  int val, child[2];
} node[4000001];
int n, tot, ans, a[100001], root[100001], pre[100001];
int insert_line(int root, int l, int r, int p, int val) {
  if (l == r) {
    node[++tot].val = node[root].val + val;
    node[tot].child[0] = node[tot].child[1] = 0;
    return tot;
  }
  int mid = l + r >> 1, ch;
  if (p <= mid) {
    ch = insert_line(node[root].child[0], l, mid, p, val);
    node[++tot].child[0] = ch, node[tot].child[1] = node[root].child[1];
  } else {
    ch = insert_line(node[root].child[1], mid + 1, r, p, val);
    node[++tot].child[0] = node[root].child[0], node[tot].child[1] = ch;
  }
  node[tot].val = node[node[tot].child[0]].val + node[node[tot].child[1]].val;
  return tot;
}
int query(int root, int l, int r, int p) {
  if (l == r) if (p >= node[root].val) return l; else return l + 1;
  int mid = l + r >> 1;
  if (p >= node[node[root].child[1]].val) return query(node[root].child[0], l, mid, p - node[node[root].child[1]].val);
  else return query(node[root].child[1], mid + 1, r, p);
}
int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  pre[a[1]] = 1, root[1] = insert_line(0, 1, n, 1, 1);
  for (int i = 2; i <= n; ++i) {
    int rt = root[i - 1];
    if (pre[a[i]]) rt = insert_line(rt, 1, n, pre[a[i]], -1);
    pre[a[i]] = i, root[i] = insert_line(rt, 1, n, i, 1);
  }
  for (int i = 1; i <= n; ++i) {
    if (ans != 1) {
      ans = 0;
      int l = n, r;
      while (l) r = l, l = query(root[r], 1, n, i) - 1, ++ans;
    }
    printf("%d ", ans);
  }
  printf("\n");
  return 0;
}

Legacy

题目描述

Rick and his co-workers have made a new radioactive formula and a lot of bad guys are after them. So Rick wants to give his legacy to Morty before bad guys catch them.
There are n planets in their universe numbered from $1$ to $n$. Rick is in planet number $s$ (the earth) and he doesn’t know where Morty is. As we all know, Rick owns a portal gun. With this gun he can open one-way portal from a planet he is in to any other planet (including that planet). But there are limits on this gun because he’s still using its free trial.
By default he can not open any portal by this gun. There are $q$ plans in the website that sells these guns. Every time you purchase a plan you can only use it once but you can purchase it again if you want to use it more.
Plans on the website have three types:

  1. With a plan of this type you can open a portal from planet $v$ to planet $u$.
  2. With a plan of this type you can open a portal from planet $v$ to any planet with index in range $[l, r]$.
  3. With a plan of this type you can open a portal from any planet with index in range $[l, r]$ to planet $v$.

Rick doesn’t known where Morty is, but Unity is going to inform him and he wants to be prepared for when he finds and start his journey immediately. So for each planet (including earth itself) he wants to know the minimum amount of money he needs to get from earth to that planet.

题意概述

有$n$个点以及$q$条边。边有$3$种类型:①从点$v$到点$u$;②从点$v$到编号在$[l, r]$之间的点;③从编号在$[l, r]$之间的点到点$v$。每条边都有一个权值$w$。求从点$s$出发到其他所有点的最短路径长度。
数据范围:$1 \le n, q \le 10^5, \; 1 \le w \le 10^9$。

算法分析

分别从上到下、从下到上建立线段树,但边的方向均为从上到下,边权均为$0$。
Two Segment Trees
如图,红色边表示线段树中的边。对于输入的每一条边,在这张图中建立相对应的边:①直接在最中间一层连边;②从最中间一层的点向上面的线段树连边;③从下面的线段树向最中间一层的点连边。最后跑一遍最短路即可。显然,点的数目为$O(n)$,边的数目为$O(n\log n)$,因此可以AC。

代码

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
struct node_type {
    long long l, r, child[2];
} node[2000001];
struct edge {
    long long v, w, nxt;
} e[2000001];
long long n, q, s, dist[2000001], tot, nume, h[2000001];
bool in[2000001];
queue<long long> que;
void add_edge(long long u, long long v, long long w) {
    if (u == v) return;
    e[++nume].v = v, e[nume].w = w, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(long long root, int mode) {
    long long mid = node[root].l + node[root].r >> 1;
    if (node[root].l == mid) node[root].child[0] = node[root].l;
    else {
        node[++tot].l = node[root].l, node[tot].r = mid;
        node[root].child[0] = tot, build_tree(tot, mode);
    }
    if (mid + 1 == node[root].r) node[root].child[1] = node[root].r;
    else {
        node[++tot].l = mid + 1, node[tot].r = node[root].r;
        node[root].child[1] = tot, build_tree(tot, mode);
    }
    if (mode) {
        add_edge(node[root].child[0], root, 0);
        add_edge(node[root].child[1], root, 0);
    } else {
        add_edge(root, node[root].child[0], 0);
        add_edge(root, node[root].child[1], 0);
    }
}
void insert_line(long long root, long long l, long long r, long long v, long long w, int mode) {
    if (l == node[root].l && r == node[root].r) {
        if (!mode) add_edge(v, root, w);
        else add_edge(root, v, w);
        return;
    }
    if (r < node[node[root].child[1]].l) insert_line(node[root].child[0], l, r, v, w, mode);
    else if (l > node[node[root].child[0]].r) insert_line(node[root].child[1], l, r, v, w, mode);
    else {
        insert_line(node[root].child[0], l, node[node[root].child[0]].r, v, w, mode);
        insert_line(node[root].child[1], node[node[root].child[1]].l, r, v, w, mode);
    }
}
void spfa() {
    memset(dist, 0x1f, sizeof(dist));
    while (!que.empty()) que.pop();
    que.push(s), in[s] = true, dist[s] = 0;
    while (!que.empty()) {
        long long t = que.front(); que.pop(); in[t] = false;
        for (long long i = h[t]; i; i = e[i].nxt) {
            if (dist[e[i].v] > dist[t] + e[i].w) {
                dist[e[i].v] = dist[t] + e[i].w;
                if (!in[e[i].v]) que.push(e[i].v), in[e[i].v] = true;
            }
        }
    }
}
int main()
{
    scanf("%lld%lld%lld", &n, &q, &s);
    for (int i = 1; i <= n; ++i) {
        node[i].l = node[i].r = i;
    }
    tot = n + 2;
    node[n + 1].l = node[n + 2].l = 1;
    node[n + 1].r = node[n + 2].r = n;
    if (n > 1) build_tree(n + 1, 0), build_tree(n + 2, 1);
    for (long long i = 1, t, v, u, l, r, w; i <= q; ++i) {
        scanf("%lld", &t);
        if (t == 1) {
            scanf("%lld%lld%lld", &v, &u, &w);
            add_edge(v, u, w);
        } else {
            scanf("%lld%lld%lld%lld", &v, &l, &r, &w);
            insert_line(n + t - 1, l, r, v, w, t - 2);
        }
    }
    spfa();
    for (int i = 1; i <= n; ++i) {
        if (dist[i] != dist[0]) printf("%lld ", dist[i]);
        else printf("-1 ");
    }
    printf("\n");
    return 0;
}

Karen and Cards

题目描述

Karen just got home from the supermarket, and is getting ready to go to sleep.
After taking a shower and changing into her pajamas, she looked at her shelf and saw an album. Curious, she opened it and saw a trading card collection.
She recalled that she used to play with those cards as a child, and, although she is now grown-up, she still wonders a few things about it.
Each card has three characteristics: strength, defense and speed. The values of all characteristics of all cards are positive integers. The maximum possible strength any card can have is $p$, the maximum possible defense is $q$ and the maximum possible speed is $r$.
There are $n$ cards in her collection. The $i$-th card has a strength $a_i$, defense $b_i$ and speed $c_i$, respectively.
A card beats another card if at least two of its characteristics are strictly greater than the corresponding characteristics of the other card.
She now wonders how many different cards can beat all the cards in her collection. Two cards are considered different if at least one of their characteristics have different values.

题意概述

给定$n$张牌,每张牌有三个属性$a_i, b_i, c_i$。一张牌能压制另一张牌$\Leftrightarrow$前者的至少两个属性严格大于后者的对应属性。已知三个属性的上限分别为$p, q, r$,问有多少种不同的牌能压制给定的$n$张牌。
数据范围:$1 \le n, p, q, r \le 5 \times 10^5, \; 1 \le a_i \le p, \; 1 \le b_i \le q, \; 1 \le c_i \le r$。

算法分析

可以先枚举从$1$到$p$枚举$a$属性,分别算出可行的牌数,累加得到答案。
现在考虑$b, c$属性。设正在枚举$a=k$的情况。我们以$b$为$x$轴、$c$为$y$轴建立平面直角坐标系。对于$a_i \ge k$的牌,必须满足$b_i \lt x \land c_i \lt y$;对于$a_i \lt k$的牌,必须满足$b_i \lt x \lor c_i \lt y$。
A Plane
如图,红色区域表示$a_i \ge k$的牌可取的点,蓝色、绿色区域表示$a_i \lt k$的牌不可取的点。显然,用红色区域的点数减去红色和蓝色、绿色区域交集的点数,就是$a=k$时可行的牌数。
红色区域的大小取决于$a_i \ge k$的牌中$b_i, c_i$的最大值。蓝色、绿色区域的大小取决于$a_i \lt k$的牌中$b_i, c_i$的值;这可以用线段树来维护。理论时间复杂度为$O(n\log n)$。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct card {
    long long a, b, c;
} c[500002];
bool operator < (card a, card b) {
    return a.a < b.a;
}
long long n, p, q, r, pnt = 1, ans, s[500002], t[500002];
struct segment_tree {
    struct node_type {
        long long l, r, val, max, sum, tag;
        node_type *child[2];
    } *root;
    void build_tree(node_type *root) {
        if (root->l == root->r) return;
        long long mid = root->l + root->r >> 1;
        node_type *p, *q;
        p = new node_type;
        p->l = root->l, p->r = mid, p->val = p->max = p->sum = p->tag = 0;
        q = new node_type;
        q->l = mid + 1, q->r = root->r, q->val = q->max = q->sum = q->tag = 0;
        build_tree(p), build_tree(q);
        root->child[0] = p, root->child[1] = q;
    }
    void push_up(node_type *root) {
        if (root->l != root->r) {
            root->sum = root->child[0]->sum + root->child[1]->sum;
            root->max = max(root->child[0]->max, root->child[1]->max);
        }
    }
    void push_down(node_type *root) {
        if (root->tag && root->l != root->r) {
            root->child[0]->tag = root->child[0]->max = root->child[1]->tag = root->child[1]->max = root->tag;
            root->child[0]->sum = (root->child[1]->l - root->child[0]->l) * root->tag;
            root->child[1]->sum = (root->child[1]->r - root->child[0]->r) * root->tag;
        }
        root->tag = 0;
    }
    void insert_line(node_type *root, long long l, long long r, long long t) {
        if (l == root->l && r == root->r) {
            root->tag = root->max = t;
            root->sum = (r - l + 1) * t;
            return;
        }
        push_down(root);
        if (r < root->child[1]->l) insert_line(root->child[0], l, r, t);
        else if (l > root->child[0]->r) insert_line(root->child[1], l, r, t);
        else {
            insert_line(root->child[0], l, root->child[0]->r, t);
            insert_line(root->child[1], root->child[1]->l, r, t);
        }
        push_up(root);
    }
    long long get(node_type *root, long long t) {
        if (root->l == root->r) return root->l;
        push_down(root);
        if (root->child[1]->max < t) return get(root->child[0], t);
        else return get(root->child[1], t);
    }
    long long get_sum(node_type *root, int l, int r) {
        if (l == root->l && r == root->r) return root->sum;
        push_down(root);
        if (r < root->child[1]->l) return get_sum(root->child[0], l, r);
        else if (l > root->child[0]->r) return get_sum(root->child[1], l, r);
        else return get_sum(root->child[0], l, root->child[0]->r) + get_sum(root->child[1], root->child[1]->l, r);
    }
} tree;
int main()
{
    scanf("%lld%lld%lld%lld", &n, &p, &q, &r);
    tree.root = new segment_tree::node_type;
    tree.root->l = 0, tree.root->r = q, tree.root->val = tree.root->max = tree.root->sum = tree.root->tag = 0;
    tree.build_tree(tree.root);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld%lld%lld", &c[i].a, &c[i].b, &c[i].c);
    }
    sort(c + 1, c + n + 1);
    s[n] = c[n].b, t[n] = c[n].c;
    for (int i = n - 1; i; --i) {
        s[i] = max(s[i + 1], c[i].b);
        t[i] = max(t[i + 1], c[i].c);
    }
    tree.insert_line(tree.root, 0, 0, q + 1);
    long long tmp;
    for (int i = 1, j = 1; i <= p; ++i) {
        for (; j <= n && c[j].a < i; ++j) {
            tmp = tree.get(tree.root, c[j].c);
            if (tmp >= c[j].b) continue;
            tree.insert_line(tree.root, tmp + 1, c[j].b, c[j].c);
        }
        tmp = max(s[j], tree.get(tree.root, t[j] + 1));
        ans += (tmp - s[j]) * r + (q - tmp) * (r - t[j]);
        if (tmp > s[j]) ans -= tree.get_sum(tree.root, s[j] + 1, tmp);
    }
    printf("%lld\n", ans);
    return 0;
}