数据结构题（莫队算法）

数据结构题

题目：

问在区间[l,r]和[l1,r1]内x的出现次数的乘积是多少？

题解：

莫队算法的模板题
关于莫队算法你可以参考这个
我这里简单的说说我对莫队的理解：
莫队是一个优雅的暴力，就是将原本复杂度不能过的程序进行优化，莫队是通过分块来实现
如果暴力做这个题，查询区间[l,r]内x的数量我们可能就从头开始搜查，按照题目给的数据来搜查，但其实我们可以这样优化,比如题目给的查询区间[3,4],[2,4],[1,5],我们可以先查询[1,5],然后顺势查询[2,4],最后[3,4]，而非从头开始，这样就省了不少时间。那如何实现这个？我们可以对整体进行分块，然后按照所分的快进行排序，尽可能实现查询区间时省时省力，最后再输出答案
至于为什么要分块排序呢？可以看看莫队算法的讲解
很显然这是一个离线算法，且适合查询量很大的情况
代码如下

代码：

#include<bits/stdc++.h>
#define forn(i,a,b) for(ll i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;

#define ll long long
const ll N =100*1000+10;
const ll mod = 20180623;
ll n,m;
ll a[N],ans[N*2],num[N],pos[N];
struct node{
    ll L,R,x,id;
}t[N*2];

bool cmp(node a,node b){
    if(pos[a.L]==pos[b.L])
        return a.R<b.R;
    else return pos[a.L]<pos[b.L];
}

ll L=1,R=0;
void solve(node p){
     while(p.L>L){
        num[a[L]]--;
        L++;
    }
    while(p.R>R){
        R++;
        num[a[R]]++;
    }
    while(p.L<L){
        L--;
        num[a[L]]++;
    }
    while(p.R<R){
        num[a[R]]--;
        R--;
    }
}

int main(){
    scanf("%lld %lld",&n,&m);
    memset(num,0,sizeof(num));
    ll block=sqrt(n);
    for(ll i=1;i<=n;i++){
        scanf("%lld",a+i);
        pos[i]=i/block;
    }

    for(ll i=1;i<=m;i++){
        ll l1,r1,l2,r2,x;
        scanf("%lld%lld%lld%lld%lld",&l1,&r1,&l2,&r2,&x);
        if(l1>r1)swap(l1,r1);
        if(l2>r2)swap(l2,r2);
        t[i].L=l1;
        t[i].R=r1;
        t[i].id=i;
        t[i].x=x;
        t[i+m].L=l2;
        t[i+m].R=r2;
        t[i+m].id=i+m;
        t[i+m].x=x;
    }

    sort(t+1,t+1+2*m,cmp);
    memset(num,0,sizeof(num));

    for(ll i=1;i<=2*m;i++){
        solve(t[i]);
        ans[t[i].id]=num[t[i].x];
    }

    for(ll i=1;i<=m;i++)
        printf("%lld\n%lld\n%lld\n",ans[i]%mod,ans[i+m]%mod,(ans[i]%mod*ans[i+m])%mod);

    return 0;
}