【洛谷 P2709】 小B的询问算法,数据结构qq41991981的博客-

小B的询问

洛谷

题目大意

• 
  ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200522152728803.png?x-oss-process=image/watermark,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; }