题目连接：hdu_5213_Lucky
题意：给你n个数，一个K，m个询问，每个询问有l1,r1,l2,r2两个区间，让你选取两个数x,y，x,y的位置为xi,yi，满足l1<=xi<=r1,l2<=y2<=r2，使得x+y=K；
题解：首先，这题没有修改操作，即可以离线，离线区间问题就要想到莫队算法，然后看状态怎么搞，因为要求的答案满足区间的可加性，我们令f(l,r)表示 l到r这个区间满足条件的ans,令F(l1,r1,l2,r2)为在这两个区间内选取的数满足条件的ans，则根据容斥定理，F(l1,r1,l2,r2)=f(l1,r2)-f(r1+1,r2)-f(l1,l2-1)+f(r1+1,l2-1)。这里为什么不用靠左的区间来减1呢？因为当靠左的区间为1时，减1会到0的位置，所以不方便操作，这个公式可以在草稿上画一下线段区间图就了解了。然后就是莫队的操作了。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #define F(i,a,b) for(int i=a;i<=b;i++) 6 using namespace std; 7 8 const int N=(int)3e4+7; 9 int sqr,n,a[N],m,K,l1,r1,l2,r2,ans[N],cnt[N]; 10 struct dt{ 11 int l,r,id,f; 12 bool operator<(const dt &b)const{ 13 if(l/sqr==b.l/sqr)return r<b.r; 14 else return l/sqr<b.l/sqr; 15 } 16 }q[N<<2]; 17 18 void modui(){ 19 sqr=(int)sqrt(n+0.5); 20 sort(q,q+(m<<2)); 21 int an=0,l=1,r=0; 22 F(i,0,(m<<2)-1){ 23 while(r<q[i].r){ 24 r++; 25 if(K>a[r]&&K-a[r]<=n)an+=cnt[K-a[r]]; 26 cnt[a[r]]++; 27 } 28 while(r>q[i].r){ 29 cnt[a[r]]--; 30 if(K>a[r]&&K-a[r]<=n)an-=cnt[K-a[r]]; 31 r--; 32 } 33 while(l<q[i].l){ 34 cnt[a[l]]--; 35 if(K>a[l]&&K-a[l]<=n)an-=cnt[K-a[l]]; 36 l++; 37 } 38 while(l>q[i].l){ 39 l--; 40 if(K>a[l]&&K-a[l]<=n)an+=cnt[K-a[l]]; 41 cnt[a[l]]++; 42 } 43 ans[q[i].id]+=an*q[i].f; 44 } 45 } 46 47 int main(){ 48 while(~scanf("%d",&n)){ 49 scanf("%d",&K); 50 F(i,1,n)scanf("%d",a+i),cnt[i]=0; 51 scanf("%d",&m); 52 F(i,0,m-1){ 53 scanf("%d%d%d%d",&l1,&r1,&l2,&r2),ans[i]=0; 54 q[(i<<2)].l=l1,q[(i<<2)].r=r2,q[(i<<2)].id=i,q[(i<<2)].f=1; 55 q[(i<<2)+1].l=l1,q[(i<<2)+1].r=l2-1,q[(i<<2)+1].id=i,q[(i<<2)+1].f=-1; 56 q[(i<<2)+2].l=r1+1,q[(i<<2)+2].r=r2,q[(i<<2)+2].id=i,q[(i<<2)+2].f=-1; 57 q[(i<<2)+3].l=r1+1,q[(i<<2)+3].r=l2-1,q[(i<<2)+3].id=i,q[(i<<2)+3].f=1; 58 } 59 modui(); 60 F(i,0,m-1)printf("%d ",ans[i]); 61 } 62 return 0; 63 }