【洛谷 P2709】 小B的询问

小B的询问

洛谷

题目大意

  • 【洛谷 P2709】 小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;
}

上一篇:线段树求解连续区间问题


下一篇:PTA L2-002 链表去重