题解 SP30906 【ADAUNIQ - Ada and Unique Vegetable】
乱搞做法居然混到了最优解az

Solution

观察数据：$1\le n,a_i\le 10^5$，在看一眼题面——啊，这不是待修莫队嘛！

前置知识：不带修莫队。
我们都知道，莫涛队长发明莫队的时候是不支持带修改的操作的。于是后人们就想出了带修改的操作。

• 1 ：要维护的东西
  莫队中维护左右端点，左端点所在的块数，右端点所在的块数，第几次修改，第几次询问，并存下修改。
  代码如下：

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 函数，代码如下：

  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

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