P4168 [Violet] 蒲公英 (离散化+分块 在线查询区间众数)

P4168 [Violet] 蒲公英

离散化+分块 在线查询区间众数

由于a_i范围是1e9的,记录a_i出现的次数不方便直接用数组记录，但是一共有n个数，我们就可以把它们排序去重，把a_i映射为在n个数中排第几，这样映射后的值域就小于n了，我们就能直接用数组记录了，这就是离散化
将长度为 n 的数组分块，每块长度为 B=sqrt(n)
比如[0,B),[B,2*b)...[k*B,n)
对于所查询的区间 [l ,r] 设l位于块bl, r位于块br,
|-------------------p1----------------p2---------------------|
|  ------l-------------|-------------------|-----------r----------|
其中p1 = (bl+1)*B,p2 = br*B-1
该区间的众数只可能为在 $[l,p1) ∪ (p2,r]$内出现的数 和 块 $[bl+1,br-1]$的众数之间

因为在加[l,p1) ∪ (p2,r]内出现的数的时候才会改变 块 [bl+1,br-1]的众数

当bl和br位于同一个块或相邻块为了方便些代码就直接暴力复杂度最大$2*sqrt(n)$
否则就是在cnt数组中只维护[l,p1) ∪ (p2,r]内出现的数 和 块 [bl+1,br-1]的众数,这些数字最多也是sqrt(n)级别的，在遍历l->p_1和p_2->r用vis数组判断是否已经加了某个数在[p1,p2]中的出现次数
p1->p2所有数出现的次数用前缀和维护
这样总复杂度就是O(nlog(n)+(n+q)*sqrt(n))
ac代码如下:
[code]#includeusing namespace std;#define ull signed long long // #define int long long #define CINT \// cin>>T;void solve(){    int n,q;cin>>n>>q;    vector a(n);    for(int i = 0;i>a;    }    vector b = a;    // 离散化    sort(b.begin(),b.end());    b.erase(unique(b.begin(),b.end()),b.end());    for(int i = 0;i