hdu 5213——莫队算法

题目大意是给出n个自然数a[],1<=a[i]<=n,给出m个询问l1,r1,l2,r2.再给出k,问第一个数在[l1,r1],第二个数在[l2,r2],且两个数加起来等于k。这样的数有多少对。n,m都是<=30000
这题需要莫队算法。设ans[l,r]表示[l,r]之间有多少对这样的数。则答案=ans[l1,r2]-ans[l1,l2-1]-ans[r1+1,r2]+ans[r1+1,l2-1]
也就是说把每个询问分解成四个莫队算法那类题的四个询问,然后分块解决。
时间复杂度:n^1.5

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn=30000+10;
int n,k,m;
int a[maxn],ans[maxn][5];
typedef struct Query{
    int id,num;
    int g,l,r;
}Query;
Query q[maxn<<2];
int iq;
int cnt[maxn],ret;
bool cmp(Query a,Query b)
{
    if(a.g==b.g) return a.r<b.r;
    return a.g<b.g;
}
int index(int x)
{
    return x<0?30001:x;
}
void cal(int l1,int r1,int l2,int r2)
{
    while(l1<l2) {ret-=cnt[index(k-a[l1])];cnt[a[l1]]–;l1++;}
    while(l1>l2) {l1–;ret+=cnt[index(k-a[l1])];cnt[a[l1]]++;}
    while(r1<r2) {r1++;ret+=cnt[index(k-a[r1])];cnt[a[r1]]++;}
    while(r1>r2) {ret-=cnt[index(k-a[r1])];cnt[a[r1]]–;r1–;}
    return;
}
int main()
{
    int i,j;
    int l1,r1,l2,r2;
    cnt[30001]=0;
    while(~scanf("%d",&n))
    {
        iq=0;
        memset(cnt,0,sizeof(cnt));
        scanf("%d",&k);
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            q[++iq].id=i;q[iq].num=1;q[iq].l=l1;q[iq].r=r2;
            q[++iq].id=i;q[iq].num=2;q[iq].l=l1;q[iq].r=l2-1;
            q[++iq].id=i;q[iq].num=3;q[iq].l=r1+1;q[iq].r=r2;
            q[++iq].id=i;q[iq].num=4;q[iq].l=r1+1;q[iq].r=l2-1;
        }
        int len=(int)sqrt(n*1.0);
        for(i=1;i<=iq;i++) q[i].g=q[i].l/len;
        sort(q+1,q+1+iq,cmp);

        q[0].l=1;q[0].r=1;cnt[a[1]]=1;
        ret=0;
        for(i=1;i<=iq;i++)
        {
            cal(q[i-1].l,q[i-1].r,q[i].l,q[i].r);
            ans[q[i].id][q[i].num]=ret;
        }
        for(i=1;i<=m;i++)
            printf("%d\n",ans[i][1]-ans[i][2]-ans[i][3]+ans[i][4]);
    }
    return 0;
}