题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5213
#include<bits/stdc++.h>
using namespace std;
#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)
#define ll long long
#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn =3e4+5;
const int mod=1e9+7;
/*
题目大意：
给定n个数的序列和k值，
q个查询，每个查询是两个区间组成，
要求对于每个查询，输出x+y=k的对数，x，y分别属于两个区间。先对问题进行容斥思考，
f(x1,y1,x2,y2)=g(x1,y2)+g(y1+1,x2-1)-g(x1,x2-1)-g(y1+1,y2);
其中g是代表这个小区间内有多少对数满足和为k。下面就是莫队的套路了，把每个查询离线，并分解成四个二维点，
并对二维点进行编号，处理对答案贡献的符号。
然后分块排序，按序扫一遍。莫队的特点是在区间左右端点移动的过程中可以O(1)计算新区间，
对于这题我们只需要维护在区间中每个数的计数即可，
最终答案改动就是cnt[k-dat[l]]这样的数量。关于莫队玄学的一点思考：
可以把二维查询看成二维平面点，
那么两个点的偏移量其实就是两个平面点的曼哈顿距离，
那么为了使复杂度降到最小就要搞一颗曼哈顿距离的最小生成树。
虽然我们最终是按边直接扫，也就是说其实最终我们扫的是一条路径，
但复杂度也利用了其性质降到了O(n^(3/2))级别.
具体关于曼哈顿距离最小生成树：https://blog.csdn.net/huzecong/article/details/8576908*/
int blocks;
struct qy
{int l,r,id,f;bool operator<(const qy& y)const{if(l/blocks==y.l/blocks) return r<y.r;return l/blocks<y.l/blocks;}
}q[maxn<<2];
///数据域
int x1,y1,x2,y2;
int n,num,k,dat[maxn];
int ans[maxn];
int cnt[maxn];
///解决主体函数
bool judge(int x)
{return x>=1&&x<=n;
}
void solve()
{blocks=sqrt(n+0.5);memset(cnt,0,sizeof(cnt));sort(q,q+(num<<2));int l=1,r=0,ret=0;for(int i=0;i<(num<<2);i++){if(q[i].l>q[i].r) continue;while(l<q[i].l){cnt[dat[l]]--;if(judge(k-dat[l])) ret-=cnt[k-dat[l]];///数据必须控制在界限范围之内l++;}while(l>q[i].l){l--;cnt[dat[l]]++;if(judge(k-dat[l])) ret+=cnt[k-dat[l]];}while(r<q[i].r){r++;cnt[dat[r]]++;if(judge(k-dat[r])) ret+=cnt[k-dat[r]];}while(r>q[i].r){cnt[dat[r]]--;if(judge(k-dat[r])) ret-=cnt[k-dat[r]];r--;}ans[q[i].id]+=q[i].f*ret;}
}int main()
{while(scanf("%d",&n)!=EOF){scanf("%d",&k);for(int i=1;i<=n;i++) scanf("%d",&dat[i]);scanf("%d",&num);for(int i=0;i<num;i++){ans[i]=0;int tp=(i<<2);scanf("%d%d%d%d",&x1,&y1,&x2,&y2);q[tp].l=x1,q[tp].r=y2,q[tp].f=1,q[tp].id=i;q[tp+1].l=y1+1,q[tp+1].r=x2-1,q[tp+1].f=1,q[tp+1].id=i;q[tp+2].l=x1,q[tp+2].r=x2-1,q[tp+2].f=-1,q[tp+2].id=i;q[tp+3].l=y1+1,q[tp+3].r=y2,q[tp+3].f=-1,q[tp+3].id=i;}solve();for(int i=0;i<num;i++) printf("%d\n",ans[i]);}return 0;
}