一.题目链接：

HDU-5213

二.题目大意：

有 n 组数，一个 k 值，m 次询问.

每次询问给出两个区间，求这两个区间内的数有多少组和为 k.

三.分析：

比较经典的莫队算法（奈何我第一次见）

莫队算法一般用来解决离线算法中的区间问题.

又被称为离线区间的万能解法（真是一个可啪的算法）.

又因区间不连续，所以先要用容斥原理处理一下.

由容斥原理得：F(L1, R1, L2, R2) = F(L1, R2) - F(L1, L2 - 1) - F(R1 + 1, R2) + F(R1 + 1, L2 -1).

因此要开 4 * m 的结构体数组来存区间.

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-4
#define PI acos(-1.0)
#define ll long long int
using namespace std;

const int M = 30000 + 5;
int cnt[M];
int a[M];
int res[M];
int block;
struct node
{
    int l, r;
    int id;
    int f;
} s[M << 2];

int cmp(node a, node b)
{
    if(a.l / block != b.l / block)
        return a.l / block < b.l / block;
    return a.r < b.r;
}

void modui(int n, int m, int k)
{
    int l, r;
    l = r = 1;
    int ans = 0;
    for(int i = 0; i < m; ++i)
    {
        while(r < s[i].r)
        {
            r++;
            if(k > a[r] && k - a[r] <= n)
                ans += cnt[k-a[r]];
            cnt[a[r]]++;
        }
        while(r > s[i].r)
        {
            cnt[a[r]]--;
            if(k > a[r] && k - a[r] <= n)
                ans -= cnt[k-a[r]];
            r--;
        }
        while(l < s[i].l)
        {
            cnt[a[l]]--;
            if(k > a[l] && k - a[l] <= n)
                ans -= cnt[k-a[l]];
            l++;
        }
        while(l > s[i].l)
        {
            l--;
            if(k > a[l] && k - a[l] <= n)
                ans += cnt[k-a[l]];
            cnt[a[l]]++;
        }
        res[s[i].id] += ans * s[i].f;
    }
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        memset(res, 0, sizeof(res));
        memset(cnt, 0, sizeof(cnt));
        block = (int)sqrt(n + 0.5);
        int k;
        scanf("%d", &k);
        for(int i = 1; i <= n; ++i)
        {
            cnt[i] = 0;
            scanf("%d", &a[i]);
        }
        int m;
        scanf("%d", &m);
        for(int i = 0; i < m; ++i)
        {
            int l1, r1;
            int l2, r2;
            scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
            int pos = i << 2;
            s[pos].l = l1, s[pos].r = r2, s[pos].id = i, s[pos].f = 1;
            s[pos + 1].l = l1, s[pos + 1].r = l2 - 1, s[pos + 1].id = i, s[pos + 1].f = -1;
            s[pos + 2].l = r1 + 1, s[pos + 2].r = r2, s[pos + 2].id = i, s[pos + 2].f = -1;
            s[pos + 3].l = r1 + 1, s[pos + 3].r = l2 - 1, s[pos + 3].id = i, s[pos + 3].f = 1;
        }
        sort(s, s + m * 4, cmp);
        modui(n, m * 4, k);
        for(int i = 0; i < m; ++i)
            printf("%d\n", res[i]);
    }
    return 0;
}