# 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.

## 代码

#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>
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);
}
c = '\n';
while (~ c && ! (isprint(c = getchar()) && c != ' ')) ;
return ~ c;
}
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) {
}
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, 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;
}


418 I'm a teapot