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
|
#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; }
|