小B的询问
题目大意
-
![在这里插入图片描述](https://www.icode9.com/i/ll/?i=20200522152728803.png?,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTkxOTgx,size_16,color_FFFFFF,t_70 -
数据范围在5e4
最基础的莫队算法
- 分块+暴力
- 对每个值划定区块,然后将查询区间按照分的块排序,遍历求解
- 由于优秀的排序,指针移动次数大大减少(莫队算法最关键的点,减少left,right指针的移动次数)
- 查询需要离线求解
show the code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep2(i,st,ed) for(int i = st; i < ed; ++i)
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
const ll mod = 1e9 + 7;
const ll N = 1e5 + 200;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
int a[N], belong[N];
int cnt[N], ans[N];
struct nod{
int l,r;
int id;
}q[N];
bool cmp(nod a, nod b){
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
bool cmp2(nod a ,nod b){
return belong[a.l] == belong[b.l] ? a.r < b.r : belong[a.l] < belong[b.l]; //奇偶排序,相比普通比较,时间复杂度优化十分明显
}
int main(){
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
int siz = (int)sqrt(n);
rep(i,n){
cin>>a[i+1];
belong[i] = i/siz + 1; //分块
}
rep(i,m){
cin>>q[i].l>>q[i].r;
q[i].id = i;
}
sort(q,q+m,cmp); //将查询排序
int l = q[0].l; //left,right指针,进行区间的遍历
int r = l-1;
int now = 0;
rep(i,m){
int ql = q[i].l, qr = q[i].r;
while(l>ql)l--,cnt[a[l]]++,now +=2*cnt[a[l]]-1;
while(r<qr)r++,cnt[a[r]]++,now +=2*cnt[a[r]]-1;
while(l<ql)cnt[a[l]]--,now -=2*cnt[a[l]]+1,l++;
while(r>qr)cnt[a[r]]--,now -=2*cnt[a[r]]+1,r--;
ans[q[i].id] = now;
}
rep(i,m){
cout<<ans[i]<<endl;
}
return 0;
}