题解 AT1219 【歴史の研究】
皎月半洒花
2020-04-13 18:03:10
大家好，我不喜欢回滚莫队，所以我用普通莫队把这题给 A 掉了。复杂度 $O(n\sqrt m + m\sqrt n)$。
考虑普通莫队的问题在哪。对于一个莫队而言，本身可以看作是 $O(n\sqrt m)$ 组查询，$O(m)$ 组询问，同时本身每个数的「出现次数带权」这个东西本身可以线段树来维护，所以复杂度可以看作是 $O(n\sqrt m\log n+ m\log n+m\log m)$ （最后一个 $\log$ 是排序的，当然也可以写基排不过显然不是很有必要）。
考虑复杂度重心向查询偏移，于是本着根号平衡的思想，大概需要一个 $O(\sqrt n)$ 查询，$O(1)$ 修改的 ds 来维护这个信息。但是似乎普通的值域分块不可做。
考虑问题出在哪：无法在当前最大值被 `del` 之后，快速找出下一个最大值。所以可以想到要去借鉴带一个 $\log $ 的权值线段树的做法，即假设某个 $x$ 的出现次数是 $1,2,3\cdots cnt_x$ ，那么一开始把所有的 $x\cdot 1,x\cdot 2, x\cdot 3\cdots,x\cdot cnt_x$ 放在一起离散化，然后对这个离散化后的数组进行值域分块。因为 $\sum _xcnt_x=n$ 所以可以知道复杂度是对的。
于是最后复杂度是 $O(n\sqrt m+m\sqrt n)$ 。因为滥用 `vector` 以及 cache 十分不友好导致慢的一匹，用了扶苏的 `fastI/O` 也毛用没有/dk。
```cpp
typedef long long ll ;
#define il inline
#define lwb lower_bound
#define upb upper_bound
#define vint vector <int>
#define mint map <int, int>
#define minttoll map <int, ll>
using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;
il bool comp(const query &a, const query &b){
return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] :
((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
il void add(const int &p){
if (buc[tmp[p]] < 0){
++ buc[tmp[p]] ; return ;
}
int lval = base[tmp[p]][buc[tmp[p]]] ;
int val = base[tmp[p]][++ buc[tmp[p]]] ;
// cout << val << " " << lval << endl ;
sump[val] ++ ; sumb[ blv[val] ] ++ ;
sump[lval] -- ; sumb[ blv[lval] ] -- ;
}
il void del(const int &p){
if (buc[tmp[p]] <= 0 ){
-- buc[tmp[p]] ; return ;
}
// if (buc[tmp[p]] + 1 >= base[tmp[p]].size()) cout << base <<buc[tmp[p]] << " " << p << ' ' << tmp[p] <<'\n', exit(0) ;
int lval = base[tmp[p]][buc[tmp[p]]] ;
int val = base[tmp[p]][-- buc[tmp[p]]] ;
sump[val] ++ ; sumb[ blv[val] ] ++ ;
sump[lval] -- ; sumb[ blv[lval] ] -- ;
}
il int ask(){
int ob = 0 ;
for (int b = blv[V] ; b >= 0 ; -- b)
if (sumb[b] > 0) { ob = b ; break ; } if (!ob) return 0 ;
for (int p = vr[ob] ; p >= vl[ob] ; -- p) if (sump[p]) return p ;
}
int main(){
qr(n) ; qr(m) ; B = n / sqrt(m) ;
for (int i = 1 ; i <= n ; ++ i) qr(g[i]) ;
for (int i = 1 ; i <= n ; ++ i)
bu[g[i]] ++, t[++ cnt] = 1ll * g[i] * bu[g[i]] ;
// debug(t, 1, cnt, ' ', '\n') ;
sort(t + 1, t + cnt + 1) ; bu.clear() ;
for (int i = 1 ; i <= n ; ++ i){
bl[i] = i / B ; bu[g[i]] ++ ; int w ;
w = upb(t + 1, t + cnt + 1, 1ll * g[i] * bu[g[i]]) - t - 1 ;
// cout << g[i] << " " << w << '\n' ;
if (bu[g[i]] == 1){
base[w].push_back(0) ;
base[w].push_back(w) ; vu[g[i]] = w ;
}
else base[vu[g[i]]].push_back(w) ; V = max(V, w) ;
su[w] = 1ll * g[i] * bu[g[i]] ; t[w] ++ ;
}
for (int i = 1 ; i <= m ; ++ i)
qr(q[i].l), qr(q[i].r), q[i].id = i ;
sort(q + 1, q + m + 1, comp) ;
for (int i = 1 ; i <= n ; ++ i) tmp[i] = vu[g[i]] ;
// for (int i = 1 ; i <= n ; ++ i) if(buc[tmp[i]]) return 0 ; else buc[tmp[i]] ++ ;
/* for (int i = 1 ; i <= n ; ++ i){
cout << g[i] << " " << tmp[i] << '\n' ;
debug(base[tmp[i]], 0, base[tmp[i]].size() - 1, ' ', '\n') ;
}return 0 ; */
// debug(tmp, 1, n, ' ', '\n') ;
B = sqrt(V) + 1 ;
for (int i = 1 ; i <= V ; ++ i){
blv[i] = i / B + 1 ;
if (blv[i] != blv[i - 1])
vr[blv[i - 1]] = i - 1, vl[blv[i]] = i ;
}
int l = 1, r = 0 ; vr[blv[V]] = V ;
// debug(blv, 1, V, ' ', '\n') ;
// debug(vl, 1, blv[V], ' ', '\n') ;
// debug(vr, 1, blv[V], ' ', '\n') ;
// while (l <= n) add(l ++) ;// cout << l << '\n' ;
for (int i = 1 ; i <= m ; ++ i){
while (l > q[i].l) add(-- l) ;
while (r < q[i].r) add(++ r) ;
while (l < q[i].l) del(l ++) ;
while (r > q[i].r) del(r --) ;
ans[q[i].id] = su[ ask() ] ;
}
for (int i = 1 ; i <= m ; ++ i)
qw(ans[i], '\n') ; return 0 ;
}
```