CF848C Goodbye Souvenir

题解
CDQ分治

Description

给出一个长度为 $n$ 的序列 $a_i$，$1 \le a_i \le n$ 。有 $m$ 个操作，每次操作输入三个数 $o,x,y$ 表示

  • $o=1$ ，此时表示令 $a_x=y$
  • $o=2$ ，此时表示询问 $\sum_{i=1}^n v(i)$ 。其中 $v(i)$ 是数字 $i$ 在 $[x,y]$ 中最后一次出现的位置减去第一次出现的位置。如果没有出现，则 $v(i) = 0$

$n, m \leq 10^5$

Solution

我们令 $pre_i$ 表示最大的 $j$ 满足 $j < i$ 且 $a_j = a_i$ （若不存在这样的 $j$ 则 $j = 0$）

同样的 $nxt_i$ 表示最小的 $j$ 满足 $j > i$ 且 $a_j = a_i$ （若不存在这样的 $j$ 则 $j = n+1$）

如果没有修改操作，那么我们把每一个 $(i, pre_i)$ 这样的二元组看成坐标上的一个点，他的值为 $i - pre_i$ ，那么每次询问 $[l, r]$ 的答案就是一个左下角为 $(l,l)$ 右上角为 $(r,r)$ 的矩（正方）形内的所有点值之和（包括边）。

这样做的原因在于，对于一个值，如果他最后一次出现在 $e$ 这个位置，第一次出现在 $s$ 这个位置，那么他对答案的贡献就是 $s-e = (s - pre_s) + (pre_s - pre_{pre_s})+ \cdots+(nxt_s - s)$ 即把 $[s, e]$ 这个区间拆分成若干个 $[pre_i, i]$ 的区间。如果把 $(i, pre_i)$ 看成一个坐标系上的点，那么他的两个维度都满足在 $[l, r]$ 中，那么他会对答案产生贡献；反之，$[l, r]$ 内的答案也是由这些点的贡献所组成的。

有了修改操作，直接用 $n$ 个 set 维护一下 $nxt$ 和 $pre$ 。对于每一个 $a[x] = y$ 修改，会减少 $(x, pre_{a_x}), (nxt_{a_x}, x), (nxt_y, pre_y)$ 三个点，增加了 $(nxt_{a_x}, pre_{a_x}), (x, pre_y), (nxt_y, x)$ 三个点。（注意这里的 $nxt_a, pre_a$ 表示的是对于 $a$ 这个值在 $x$ 这个位置之前/之后第一次出现的位置）。于是问题转化成一个加点删点求矩形内部值之和，可以以时间为第一维，$i$ 为第二维，$pre_i$ 为第三维用CDQ分治做三维偏序就做完了。（询问矩阵再用一个差分）

时间复杂度：$O(n \log^2 n)$ （由于点数可能很多所以参与 CDQ 分治的点有大概 $6n$ 个所以很慢）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**
 * Author: AcFunction
 * Date:   2019-07-06 17:01:34
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 500500; 

int n, m, a[N], nxt[N], pre[N], po[N]; 
int tot, fla[N]; 
ll ans[N], c[N]; 
set <int> s[100001]; 

struct Query {
  int op, y, z, v, id; 
} Q[N * 2]; 

void mk (int op, int y, int z, int v, int id) {
  Q[++tot].y = y, Q[tot].z = z; 
  Q[tot].id = id; Q[tot].op = op; Q[tot].v = v; 
}

int lb(int x) {
  return x & (-x); 
}

void add(int x, int d) {
  for(int i = x; i <= 100005; i += lb(i))
    c[i] += d; 
}

ll sum(int x) {
  ll ret = 0; 
  for(int i = x; i; i -= lb(i)) 
    ret += c[i]; 
  return ret; 
}

bool cmp(Query x, Query y) {
  return x.y < y.y; 
}

void CDQ(int l, int r) {
  if(l == r) return ; 
  int mid = (l + r) >> 1; 
  CDQ(l, mid); CDQ(mid + 1, r); 
  sort(Q + l, Q + mid + 1, cmp); 
  sort(Q + mid + 1, Q + r + 1, cmp); 
  int pos = l; 
  for(int i = mid + 1; i <= r; i++) {
    while(pos <= mid && Q[pos].y <= Q[i].y) {
      if(Q[pos].op == 0)
        add(Q[pos].z + 1, Q[pos].v); 
      pos++; 
    } if(Q[i].op == 1) {
      ans[Q[i].id] += sum(Q[i].z + 1); 
    }
  } 
  for(int i = l; i < pos; i++) {
    if(Q[i].op == 0) 
      add(Q[i].z + 1, -(Q[i].v)); 
  }
} 

int main() {
  scanf("%d %d", &n, &m); 
  for(int i = 1; i <= n; i++) {
    s[i].insert(0), s[i].insert(n + 1); 
    scanf("%d", &a[i]); 
    pre[i] = po[a[i]]; 
    po[a[i]] = i; 
    mk(0, i, pre[i], i - pre[i], 0); 
    s[a[i]].insert(i); 
  }
  for(int i = 1; i <= n; i++) 
    po[i] = n + 1; 
  for(int i = n; i >= 1; i--) {
    nxt[i] = po[a[i]]; 
    po[a[i]] = i; 
  }
  for(int i = 1; i <= m; i++) {
    int op, x, y; 
    scanf("%d %d %d", &op, &x, &y);
    if(op == 1) {
      if(a[x] == y) continue ;
      mk(0, x, pre[x], pre[x] - x, 0); 
      mk(0, nxt[x], x, x - nxt[x], 0); 
      mk(0, nxt[x], pre[x], nxt[x] - pre[x], 0);   
      nxt[pre[x]] = nxt[x]; 
      pre[nxt[x]] = pre[x]; 
      s[a[x]].erase(x);
      a[x] = y; 
      s[y].insert(x);
      set < int > :: iterator Nw = s[y].find(x); 
      int Pr = *(--Nw), Nx = *(++(++(Nw))); 
      mk(0, Nx, Pr, Pr - Nx, 0); 
      mk(0, x, Pr, x - Pr, 0); 
      mk(0, Nx, x, Nx - x, 0); 
      pre[Nx] = nxt[Pr] = x; 
      pre[x] = Pr, nxt[x] = Nx; 
    } else {
      mk(1, x - 1, x - 1, 0, i * 4 - 3); 
      mk(1, x - 1, y, 0, i * 4 - 2); 
      mk(1, y, x - 1, 0, i * 4 - 1); 
      mk(1, y, y, 0, i * 4); 
      fla[i] = 1; 
    }
  } 
  CDQ(1, tot);
  for(int i = 1; i <= m; i++) {
    if(fla[i]) {
      printf("%lld\n", ans[i * 4 - 3] - ans[i * 4 - 2] - ans[i * 4 - 1] + ans[i * 4]); 
    }
  }
  return 0; 
}