題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=5213
題意：給我們n個數，然後給我們一個數字K，再給我們兩個區間[L,R],[U,V]，問我們從這兩個區間裡分别去兩個數，有多少對取法，可以使得所取的兩個數和為K。
方法：莫隊算法 + 容斥原理。
首先我們先來看一種更加簡單的情況。假如我們現在的情況是從一個區間裡面選出兩個數，求取法的對數。
我們用num[i]記錄數字i目前出現的次數，c[i]表示第i位的值
假如我們知道了[l,r]的答案，則我們可以求得[l,r+1]：ans += num[K-c[i]], num[c[i]]++;
假如我們知道了[l,r]的答案，則我們可以求得[l-1,r]： ans -= num[K-c[i]], num[c[i]]--;
是以我們能夠通過分塊莫隊算法輕易的求得所有區間的值。
現在我們的問題回到兩個區間中，這裡我們用一個小技巧，我們可以通過容斥原理把問題變成求單個區間的值。
設A為[L,R]，B為[U,V]，C為[R+1,U-1]，f(x,y)為從區間x,y中取兩個數和為K的取法。
則根據容斥原理有：f(A,B) = f(A+B+C, A+B+C) + f(C,C) - f(A,A) - f(B,B)。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{
int l,r,ans,id,type;
}arr[120010];
int n,m,M,K,pos[30010],c[30010],num[60010],ans,f[30010];
bool cmp(node a,node b)
{
return pos[a.l]<pos[b.l] ||(pos[a.l]==pos[b.l] && a.r<b.r);
}
void update(int p,int add)
{
ans+=num[K-c[p]]*add;
num[c[p]]+=add;
}
void solve()
{
int i,j,k,l,r;
l=1;r=0;
ans=0;
memset(num,0,sizeof(num));
for(i=1;i<=M;i++)
{
for(;r<arr[i].r;r++) update(r+1,1);
for(;r>arr[i].r;r--) update(r,-1);
for(;l<arr[i].l;l++) update(l,-1);
for(;l>arr[i].l;l--) update(l-1,1);
arr[i].ans=ans;
}
}
int main()
{
int i,j,k,l,r,u,v;
while(~scanf("%d",&n))
{
scanf("%d",&K);
for(i=1;i<=n;i++) scanf("%d",&c[i]);
k=(int)sqrt(n);
for(i=1;i<=n;i++) pos[i]=(i-1)/k+1;
scanf("%d",&m);
M=m*4;
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&l,&r,&u,&v);
arr[i*4-3].l=l;arr[i*4-3].r=v;arr[i*4-3].id=i;arr[i*4-3].type=1;
arr[i*4-2].l=l;arr[i*4-2].r=u-1;arr[i*4-2].id=i;arr[i*4-2].type=-1;
arr[i*4-1].l=r+1;arr[i*4-1].r=v;arr[i*4-1].id=i;arr[i*4-1].type=-1;
arr[i*4].l=r+1;arr[i*4].r=u-1;arr[i*4].id=i;arr[i*4].type=1;
}
sort(arr+1,arr+1+M,cmp);
solve();
memset(f,0,sizeof(f));
for(i=1;i<=M;i++) f[arr[i].id]+=arr[i].type*arr[i].ans;
for(i=1;i<=m;i++) printf("%d\n",f[i]);
}
}