题解 SP30906 【ADAUNIQ - Ada and Unique Vegetable】
TRZ_2007
2021-02-24 15:49:22
**[题解 SP30906 【ADAUNIQ - Ada and Unique Vegetable】](https://www.luogu.com.cn/problem/SP30906)**
~~乱搞做法居然混到了最优解az~~
# Solution
观察数据：$1\le n,a_i\le 10^5$，在看一眼题面——啊，这不是待修莫队嘛！
**前置知识：不带修莫队**。
我们都知道，莫涛队长发明莫队的时候是不支持带修改的操作的。于是后人们就想出了带修改的操作。
- 1 **：要维护的东西**
莫队中维护左右端点，左端点所在的块数，右端点所在的块数，第几次修改，第几次询问，并存下修改。
代码如下：
```cpp
struct change { //修改
int id,y; //id表示修改的数字的编号，y表示改动后的数字
}p[N];
struct node {
int id,l,r,bl,br,pre; //id表示这是第几次询问，bl和br分别表示左端点和右端点偶在的块，pre表示之前有多少组询问
}q[N];
```
- 2 **：如何排序**
三关键字排序，第一关键字是左端点所在的块的编号，第二关键字是右端点所在的块的编号，第三关键字是修改的次数。都是升序排列。
- 3 **：如何带修**
在离线修改的时候我们引入一个时间常量 ```t``` ，来表示当前进行了几次修改。如果说 ```t``` 大于了我们本次询问的修改次数，那么就**暴力还原多余的修改**，否则就**直接暴力向下修改** ,直到找到我们的最终值。修改我们可以自己定义一个 ```update``` 函数，代码如下：
```cpp
inline void update(int x) {
int alpha = p[x].id; //取出当前要修改的数字的编号
if(l <= alpha && alpha <= r) { //只有在查询区间内本次修改才会对答案有贡献
del(a[alpha]); add(p[x].y); //在答案之中删除原数的贡献，加上修改后数的贡献
}
swap(a[alpha],p[x].y);
//这个地方很重要，就是说我们修改好了之后有可能还要改回来。
//那个时候我们就无法把数字改为原来的数字，而会改为原本修改中存下的数字也就是现在的a[alpha]（相当于没有改回来）。
//为了避免这种现象，在改完之后就对这两个数字进行交换。
}
```
最后一点注意事项： **这道题下标是从 ``0`` 开始的！**
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
#define gc getchar
inline int read() {
int c = gc(), t = 1, n = 0;
while(isspace(c)) { c = gc(); }
if(c == '-') { t = -1, c = gc(); }
while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
return n * t;
}
#undef gc
struct change {
int id,y;
}p[N];
struct node {
int id,l,r,bl,br,pre;
}q[N];
int n,m,len,l,r,t,cnt,tota,totb,opt;
int a[N],sum[N],ans[N];
bool cmp(node u,node v) {
if(u.bl != v.bl) return u.bl < v.bl;
else {
if(u.br != v.br) return u.br < v.br;
else return u.pre < v.pre;
}
}
inline void add(int x) {
if(sum[x] == 1) --cnt;
if(sum[x] == 0) ++cnt;
++sum[x];
}
inline void del(int x) {
if(sum[x] == 1) --cnt;
if(sum[x] == 2) ++cnt;
--sum[x];
}
inline void update(int x) {
int alpha = p[x].id;
if(l <= alpha && alpha <= r) {
del(a[alpha]); add(p[x].y);
}
swap(a[alpha],p[x].y);
}
inline void solve() {
l = 1; r = 0; t = 0;
for(int i = 1;i <= totb;i++) {
while(l > q[i].l) add(a[--l]);
while(r < q[i].r) add(a[++r]);
while(l < q[i].l) del(a[l++]);
while(r > q[i].r) del(a[r--]);
while(t > q[i].pre) update(t--);
while(t < q[i].pre) update(++t);
ans[q[i].id] = cnt;
}
}
int main() {
n = read(); m = read(); len = pow(n,2.0 / 3);
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= m;i++) {
opt = read();
if(opt == 1) {
p[++tota] = {read() + 1,read()};
}else {
++totb;
q[totb].l = read() + 1; q[totb].r = read() + 1; q[totb].pre = tota; q[totb].id = totb;
q[totb].bl = (q[totb].l - 1) / len + 1; q[totb].br = (q[totb].r - 1) / len + 1;
}
}
sort(q + 1,q + totb + 1,cmp);
solve();
for(int i = 1;i <= totb;i++) {
printf("%d\n",ans[i]);
}
return 0;
}
```