Goodbye Souvenir

题目描述

I won’t feel lonely, nor will I be sorrowful… not before everything is buried.

A string of $n$ beads is left as the message of leaving. The beads are numbered from $1$ to $n$ from left to right, each having a shape numbered by integers between $1$ and $n$ inclusive. Some beads may have the same shapes.

The memory of a shape $x$ in a certain subsegment of beads, is defined to be the difference between the last position and the first position that shape $x$ appears in the segment. The memory of a subsegment is the sum of memories over all shapes that occur in it.

From time to time, shapes of beads change as well as the memories. Sometimes, the past secreted in subsegments are being recalled, and you are to find the memory for each of them.

题意概述

给定一个长度为$n$的序列$a_i$，有$m$次操作。操作有两种：给定$p, x$，将第$p$个数修改成$x$；给定$l, r$，求$[l, r]$内每种数字的长度之和。某种数字长度的定义是该数字在区间内第一次出现的位置与最后一次出现的位置之差。

数据范围：$1 \le n, m \le 10^5, \ 1 \le a_i, x \le n$。

算法分析

设区间$[l, r]$中某种数字出现的位置为$p_1, p_2, \ldots, p_k$，显然这个数字对答案的贡献为$p_k-p_1=(p_2-p_1)+(p_3-p_2)+ \cdots +(p_k-p_{k-1})$。令$pre_i$表示在$i$之前离$i$最近的等于$a_i$的数的位置，那么贡献就是$(p_2-pre_2)+(p_3-pre_3)+ \cdots +(p_k-pre_k)$。我们把每个数$a_i$想像成二维空间中的一个点$(pre_i, i)$，它的权值是$i-pre_i$。那么问题就变成了求在矩形$(l, l)-(r, r)$中的点权之和。这可以用传说中的 CDQ 分治来解决。

代码

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

#define int long long

using namespace std;

void maxify(int &a, int b) { b > a && (a = b); }
void minify(int &a, int b) { b < a && (a = b); }

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 operator > (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 operator < (T x) {
    write(x); return *this;
  }
} io;

struct BinaryIndexedTree {
private:
  static const int N = 200000;
  int n, a[N];

public:
  void init(int t) {
    n = t, memset(a, 0, sizeof a);
  }
  void add(int p, int v) {
    for (; p <= n; p += p & -p) a[p] += v;
  }
  int get(int p) {
    int ret = 0;
    for (; p; p -= p & -p) ret += a[p];
    return ret;
  }
};

struct Set {
private:
  static const int N = 200000;
  int a[N];
  set <int> s[N];
  set <int> :: iterator it;

public:
  void modify(int p, int v) {
    if (a[p]) s[a[p]].erase(p);
    a[p] = v;
    s[a[p]].insert(p);
  }
  int prev(int p) {
    it = s[a[p]].find(p);
    return it == s[a[p]].begin() ? *it : *(-- it);
  }
  int next(int p) {
    it = ++ s[a[p]].find(p);
    return it == s[a[p]].end() ? *(-- it) : *it;
  }
};

#define MODIFY 1
#define QUERY 2

struct Solver {
private:
  static const int N = 200000;
  int n, m, numq, top, pos[N], pre[N], ans[N];
  BinaryIndexedTree tree;
  Set s;
  struct Query {
    int type, x, y, w, id;
    bool operator < (const Query &q) const {
      return x == q.x ? type < q.type : x < q.x;
    }
  } q[N << 2], tmp[N << 2];
  void add_query(int type, int x, int y, int w, int id) {
    q[++ numq] = (Query) { type, x, y, w, id };
  }
  void input() {
    io > n > m;
    for (int i = 2; i <= n + 1; ++ i) {
      int t; io > t, s.modify(i, t);
      int prev = s.prev(i);
      add_query(MODIFY, prev, i, i - prev, 0);
    }
    for (int i = 1; i <= m; ++ i) {
      int o; io > o;
      if (o == 1) {
        int p, x; io > p > x; ++ p;
        int prev = s.prev(p), next = s.next(p);
        if (prev < p) add_query(MODIFY, prev, p, prev - p, 0);
        if (next > p) add_query(MODIFY, p, next, p - next, 0);
        if (prev < p && next > p) add_query(MODIFY, prev, next, next - prev, 0);
        s.modify(p, x);
        prev = s.prev(p), next = s.next(p);
        if (prev < p && next > p) add_query(MODIFY, prev, next, prev - next, 0);
        if (prev < p) add_query(MODIFY, prev, p, p - prev, 0);
        if (next > p) add_query(MODIFY, p, next, next - p, 0);
      } else {
        int l, r; io > l > r, ++ l, ++ r, ++ top;
        add_query(QUERY, r, r, 1, top);
        add_query(QUERY, r, l - 1, -1, top);
        add_query(QUERY, l - 1, r, -1, top);
        add_query(QUERY, l - 1, l - 1, 1, top);
      }
    }
  }
  void process(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    process(l, mid), process(mid + 1, r);
    int s = l, t = mid + 1, pnt = l;
    while (s <= mid && t <= r) {
      if (q[s] < q[t]) {
        if (q[s].type == MODIFY) tree.add(q[s].y, q[s].w);
        tmp[pnt ++] = q[s ++];
      } else {
        if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
        tmp[pnt ++] = q[t ++];
      }
    }
    while (t <= r) {
      if (q[t].type == QUERY) ans[q[t].id] += q[t].w * tree.get(q[t].y);
      tmp[pnt ++] = q[t ++];
    }
    for (int i = l; i < s; ++ i) if (q[i].type == MODIFY) tree.add(q[i].y, -q[i].w);
    while (s <= mid) tmp[pnt ++] = q[s ++];
    for (int i = l; i <= r; ++ i) q[i] = tmp[i];
  }

public:
  void solve() {
    input(), tree.init(n + 1), process(1, numq);
    for (int i = 1; i <= top; ++ i) io < ans[i] < '\n';
  }
} solver;

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