HDU - 5213 Lucky（莫队算法+容斥思想）

题目大意：

多次询问，每次询问两个区间 [l1,r1]，[l2,r2] 个选出一个元素，有多少种选择方法可以使选出的两数的和为定值 k 。

分析：

设 f([a,b],[c,d]) 表示区间 [a,b],[c,d] 的选择方式数，那么，就可以推得一个公式：

f([a,b],[c,d])=f([a,d],[a,d])−f([a,c−1],[a,c−1])−f([b+1,d],[b+1,d])+f([b+1,c−1],[b+1,c−1])

然后只要求每个区间 [l,r] 对应的 f([l,r],[l,r]) 就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 30050
struct mo
{
    int l;int r;int id;int ans;
}q[4*maxn];
int m,n,cnt,k,ans,num[2*maxn],a[maxn],out[maxn],pos[maxn],temp_a,temp_b,temp_c,temp_d;
void add_mo(int l,int r)
{
    q[cnt].l=l;q[cnt].r=r;q[cnt].id=cnt;
}
bool cmp_mo(mo a,mo b)
{
    return pos[a.l]==pos[b.l] ? a.r<b.r : a.l<b.l;
}
bool cmp_id(mo a,mo b)
{
    return a.id<b.id;
}
void move_mo(int x,int add)
{
    ans+=(add*num[k-a[x]]);num[a[x]]+=add;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;ans=0;
        memset(num,0,sizeof(num));
        int unit=sqrt(n);
        for(int i=0;i<=n;i++)pos[i]=i/unit;

        scanf("%d",&k);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&temp_a,&temp_b,&temp_c,&temp_d);
            add_mo(temp_a,temp_d);cnt++;
            add_mo(temp_a,temp_c-1);cnt++;
            add_mo(temp_b+1,temp_d);cnt++;
            add_mo(temp_b+1,temp_c-1);cnt++;
        }
        sort(q,q+cnt,cmp_mo);
        int l=1,r=0;
        for(int i=0;i<cnt;i++)
        {
            while(r<q[i].r)move_mo(r+1,1),r++;
            while(l>q[i].l)move_mo(l-1,1),l--;
            while(r>q[i].r)move_mo(r,-1),r--;
            while(l<q[i].l)move_mo(l,-1),l++;
            q[i].ans=ans;
        }
        sort(q,q+cnt,cmp_id);
        for(int i=0;i<cnt;i+=4)
        {
            //printf("[%d,%d]=%d\n",q[i].l,q[i].r,q[i].ans);
            out[q[i].id/4]=q[i].ans-q[i+1].ans-q[i+2].ans+q[i+3].ans;
            //printf("[%d,%d]=%d\n",q[i+3].l,q[i+3].r,q[i+3].ans);
            //if(a[q[i+3].l]+a[q[i+3].r]==k)out[q[i].id/4]++;
        }
        for(int i=0;i<m;i++)
        {
            printf("%d\n",out[i]);
        }
        //cout<<"ans="<<ans<<endl;
    }
}