hdu4638 莫队算法

莫队算法基础题，题目看懂就能做出来

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define ll long long

struct Query{

    int L,R,id;

}q[MAXN];

int s,vis[MAXN],id[MAXN];

ll ans[MAXN];

ll res;

bool cmp(Query a,Query b){

    if(a.L/s == b.L/s) return a.R<b.R;

    return a.L/s < b.L/s;

}

void add(int idx){//加入编号为idx的点

    if(vis[idx-] && vis[idx+]) res--;//如果两边都是连续的，那么组可以减一

    else if(!vis[idx-] && !vis[idx+]) res++;//如果两边都是断开的，那么加入该点可以使组加一

    vis[idx]=;

}

void dec(int idx){

    if(vis[idx-] && vis[idx+]) res++;

    else if(!vis[idx-] && !vis[idx+]) res--;

    vis[idx]=;

}

int main(){

    int n,m,t;

    scanf("%d",&t);

    while(t--){

        memset(vis,,sizeof vis);

        scanf("%d%d",&n,&m);

        s=(int)sqrt(n);

        for(int i=;i<=n;i++)

            scanf("%d",&id[i]);

        for(int i=;i<m;i++){

            scanf("%d%d",&q[i].L,&q[i].R);

            q[i].id=i;

        }

        sort(q,q+m,cmp);

        int L=,R=;

        res=;

        for(int i=;i<m;i++){

            while(R<q[i].R){

                R++;

                add(id[R]);

            }

            while(R>q[i].R){

                dec(id[R]);

                R--;

            }

            while(L<q[i].L){

                dec(id[L]);

                L++;

            }

            while(L>q[i].L){

                L--;

                add(id[L]);

            }

            ans[q[i].id]=res;

        }

        for(int i=;i<m;i++)

            printf("%d\n",ans[i]);

    }

    return ;

}