#C241109B. 晄轮大会
标签（Label）
- 莫队算法
- 观察+分析
网址（Website）
题目（Problem）
样例
输入数据 1
1
8 10
2 5 3 1 5 2 1 3
1 4
6 8
3 7
4 6
1 7
4 8
6 6
4 7
7 8
5 8输出数据 1
6
3
6
3
9
6
0
3
1
6【样例2～10】
见下发文件 hoshino/hoshino2～10.in 和 hoshino/hoshino2～10.ans。
题解（Solution）
$\qquad$发现区间不好合并，离线又可以处理，直接莫队启动！！！
$\qquad$我直接想了 $O(n\sqrt n \log n)$ 的做法，推了一下式子，发现离散化之后，搞一个 $buc_i$ 的桶表示当前区间类别为 $i$ 的学生有多少个，然后再弄一个 $b_s$ 表示 $\sum_{i=1}^{i\le n} [buc_i=s]$ 的数量，容易发现先干掉 $buc$ 更大的 $i$ 更优，考虑每次修改的贡献，推了好久，又枚举了一下，最后得出：（这里的 $A$ 表示 $b_s$ 的最大值，其实就是 $n$ ，因为最多就 $n$ 个数）
$$
ans=\sum_{i=1}^A\left(i\times\left(\frac{b_i\cdot (b_i-1)}{2}+b_i\cdot\left(\sum_{j=i}^{j\le A}b_j\right)\right)\right)
$$
然后推一下如果 $b_i$ 减少 $1$ 的影响：
$$
ans=\sum_{i=1}^A\left(i\times\left(\frac{(b_i-1)\cdot (b_i-2)}{2}+(b_i-1)\cdot\left(\sum_{j=i}^{j\le A}b_j\right)\right)\right)
$$
然后就可以推出来 $b_i$ 加减对答案的影响：
加：
$$
ans+=i\times\left(\left(\sum_{j\in [i+1,A]}b_j\right)+b_i\right)+\sum_{j\in[1,i-1]}j\times b_j
$$
减：
$$
ans-=i\times\left(\left(\sum_{j\in [i+1,A]}b_j\right)+b_i-1\right)+\sum_{j\in[1,i-1]}j\times b_j
$$
发现 $\sum_{j\in [i+1,A]}b_j$ 和 $\sum_{j\in[1,i-1]}j\times b_j$ 都可以使用树状数组维护，所以做出来就是 $O(n\sqrt n \log n)$ 。
现在发现已经很接近正解了，只是自己本来就没什么自信，导致拿着式子就开始打暴力，痛失正解啊~
也是正常，这几次考试都把信心干没了，人都想摆烂了，甚至放弃希望了，现在会做题目都不敢打。
出题者题解
### 算法分析测试点 1∼2 (10pts)
每次询问直接全排列枚举即可。复杂度 $O(nm \times n!)$。
测试点 3∼4 (10pts)
结论：出现次数越多的物资应该越先被放置。可以使用排序不等式等方式证明。
有了这个结论后，只需要每次询问时暴力排序计算答案即可。复杂度 $O(nm \log n)$。
测试点 5∼7 (15pts)
因为 $a_i$ 很小，所以每次询问直接暴力把每一种物资的出现次数算出来，暴力计算即可。复杂度 $O(ma \log a)$，其中 $a$ 是 $a_i$ 的取值范围。
测试点 8∼10 (15pts)
$a_i$ 是随机选取的，那么出现次数的最大值不会太大。先用莫队将询问离线，每次询问时直接扫出现次数的值域计算即可。复杂度 $O(n\sqrt m + m \times \frac{n}{a})$，其中 $na$ 表示出现次数的最大值（由于 $a_i$ 是随机选取的，所以 $na$ 不会太大）。
测试点 11∼14 (20pts)
因为 $l=1$，所以可以直接遍历 $1$ 至 $n$，算出每一个前缀的答案。每次加入一个学生会使一种物资的出现次数 $+1$，可以简单地用数据结构在 $O(\log n)$ 的时间复杂度下维护。复杂度 $O(n \log n + m)$。
测试点 15∼16 (10pts)
给常数不大的 $O(n\sqrt m \log n)$ 做法的一档分。
测试点 17∼18 (10pts)
给小常数的 $O(n\sqrt m \log n)$ 或常数过大的 $O(n\sqrt n)$ 做法的一档分。
测试点 19∼20 (10pts)
先使用莫队把问题变为每次操作为将一种物资的出现次数 +1 或 -1，这样可以直接使用上一档分的做法直接维护，复杂度是 $O(n\sqrt m \log n)$ 的。发现每次一种物资的变化量只有 1，可以直接维护。设 $p_i$ 为当前区间内出现次数为 $i$ 的物资的种数，当某种物资出现次数增多时，出现次数比它少的物资和出现次数大于它且增加 1 的物资消耗的体力并不会改变，所以直接计算它变化带来的改变并修改 $p$ 数组即可，出现次数减少时同理。具体地，设当前对一个出现次数为 $k$ 的物资进行一次增加操作，设 $s = \sum_{i=k+1}^{n} p_i$，则增加的量为 $s \times (k+1) - s \times k = s$，所以动态维护后缀和即可，每次修改的位置的数量是 $O(1)$ 的。
复杂度 $O(n\sqrt m)$，常数不大。
代码（Code）
$O(n\sqrt n\log n)$
#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 501234;
bool ST;
int tid,Tt;
struct Wolf{int l,r,id;}q[N];
int n,B,m,ans,as[N];
int a[N],pos[N];
unordered_map<int,int> mp;
int buc[N],tot;
struct BIT{
int n,c[N];inline void init(int s){s++;n=s;memset(c,0,sizeof c);}
inline int lbt(int x){return x&-x;}
void update(int x,int v){x++;for(int i=x;i<=n;i+=lbt(i))c[i]+=v;}
int ask(int x){x++;int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
inline int ask(int l,int r){return ask(r)-ask(l-1);}
}Bs,Bsi;
inline void calcdel(int i){
ans -= i*(Bs.ask(i,n)-1) + Bsi.ask(i-1);
Bs.update(i,-1), Bsi.update(i,-i);
}
inline void calcins(int i){
ans += i*Bs.ask(i,n) + Bsi.ask(i-1);
Bs.update(i,1), Bsi.update(i,i);
}
inline void del(int col){
if(buc[col]) calcdel(buc[col]);
buc[col]--;
if(buc[col]) calcins(buc[col]);
}
inline void ins(int col){
if(buc[col]) calcdel(buc[col]);
buc[col]++;
if(buc[col]) calcins(buc[col]);
}
inline int san(){
int x = rd();
if(!mp.count(x)) return mp[x]=++tot;
else return mp[x];
}
void Solve(){
n=rd(),m=rd(),B=sqrt(n);
For(i,1,n) a[i]=san(),pos[i]=(i-1)/B+1;
For(i,1,m) q[i]={rd(),rd(),i};
sort(q+1,q+m+1,[&](Wolf a,Wolf b){
if(pos[a.l]^pos[b.l]) return pos[a.l]<pos[b.l];
if(pos[a.l]&1) return a.r>b.r;
return a.r<b.r;});
Bs.init(n), Bsi.init(n);
int l=1,r=0;
For(i,1,m){
int L=q[i].l,R=q[i].r;
while(l>L) ins(a[--l]);
while(r<R) ins(a[++r]);
while(l<L) del(a[l++]);
while(r>R) del(a[r--]);
as[q[i].id] = ans;
}For(i,1,m) printf("%lld\n",as[i]);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("hoshino.in","r",stdin);
freopen("hoshino.out","w",stdout);
tid=rd(),Tt=1;double Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}$O(n\sqrt n)$
#include<bits/stdc++.h>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int N = 501234;
bool ST;
int tid,Tt;
struct Wolf{int l,r,id;}q[N];
int n,B,m,ans,as[N];
int a[N],pos[N];
unordered_map<int,int> mp;
int buc[N],sum[N],tot;
struct BIT{
int n,c[N];inline void init(int s){s++;n=s;memset(c,0,sizeof c);}
inline int lbt(int x){return x&-x;}
void update(int x,int v){x++;for(int i=x;i<=n;i+=lbt(i))c[i]+=v;}
int ask(int x){x++;int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}
inline int ask(int l,int r){return ask(r)-ask(l-1);}
}Bs,Bsi;
inline void del(int col){
ans-=sum[buc[col]]-1;
sum[buc[col]]--;
buc[col]--;
}
inline void ins(int col){
ans+=sum[buc[col]+1];
sum[buc[col]+1]++;
buc[col]++;
}
inline int san(){
int x = rd();
if(!mp.count(x)) return mp[x]=++tot;
else return mp[x];
}
void Solve(){
n=rd(),m=rd(),B=sqrt(n);
For(i,1,n) a[i]=san(),pos[i]=(i-1)/B+1;
For(i,1,m) q[i]={rd(),rd(),i};
sort(q+1,q+m+1,[&](Wolf a,Wolf b){
if(pos[a.l]^pos[b.l]) return pos[a.l]<pos[b.l];
if(pos[a.l]&1) return a.r>b.r;
return a.r<b.r;});
Bs.init(n), Bsi.init(n);
int l=1,r=0;
For(i,1,m){
int L=q[i].l,R=q[i].r;
while(l>L) ins(a[--l]);
while(r<R) ins(a[++r]);
while(l<L) del(a[l++]);
while(r>R) del(a[r--]);
as[q[i].id] = ans;
}For(i,1,m) printf("%lld\n",as[i]);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("hoshino.in","r",stdin);
freopen("hoshino.out","w",stdout);
tid=rd(),Tt=1;double Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
