\(\\\)

---

原题题面太过混乱出题人语文凉凉

给出一个长为 \(n\) 的数列 \(A\) ，多次询问：

对于一个区间 \([L_i,R_i]\)，把区间内的所有数最少划分成多少个数集，使得每一个集合内没有相同元素。

• \(A_i\le 10^9,n,m\le 2\times 10^5\)

\(\\\)

Solution

---

题目的模型很容易转化成区间众数问题。

莫队求解区间众数。

首先数据范围是假的，离散化之后就开的下桶了。

对于区间扩张，肯定是加一下桶，然后跟当前答案取 \(max\) 。

问题在于区间缩小时，删除一个数怎么搞。

\(\\\)

开始有一个 too simple 想法，是用堆去维护当前答案区间内所有数出现个数，然后懒惰删除法，每次更新时判断一下堆顶是否正确。

想一想是对的，但是 \(O(N\sqrt NlogN)\) 的复杂度对于 \(2\times 10^5\) 很吃力。

\(\\\)

一个机智的做法。

设 \(cnt[i]\) 表示 \(bkt[x]=i\) 的个数，也就是当前区间里出现次数为 \(i\) 的数的个数。

空间没有问题，因为最多出现数列长度的次数。

这样一来修改就容易了很多，减的时候只需要判断一下，当前数对应的 \(cnt\) 是否 \(>1\) 即可。

注意加减是对 \(cnt\) 和 \(bkt\) 的同时更新。

\(\\\)

Code

---

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 200000#define R register#define gc getcharusing namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}int n,m,ans,bl[N],cnt[N],bkt[N],s[N],tmp[N];struct Q{int l,r,ans,id;}q[N];inline bool cmp1(Q x,Q y){ return bl[x.l]==bl[y.l]?x.r
           
            
             q[i].l){--nowl;add(nowl);} while(nowr>q[i].r){del(nowr);--nowr;} while(nowr