题目链接：传送门

Description

给一个序列a，以及K，有Q个询问，每个询问四个数，L,R,U,V, 求L<=i<=R,U<=j<=V，a[i]+a[j]=K的(i, j)对数（题目保证了L <= R < U <= V）

Solution

因为要求的答案满足区间的可加性，我们令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)。 然后就是莫队的操作了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 300000 + 10;

int N, M, K;
int S;
int A[Maxn];

struct node
{
    int l, r, fl, id;
}Q[Maxn << 2];

inline int cmp (node x, node y)
{
    if((x.l / S) == (y.l / S)) return x.r < y.r;
    return x.l < y.l;
}

int Sum, Cnt[Maxn], Ans[Maxn];

inline void update (int x, int y)
{
    if (K > A[x] && K - A[x] <= N)
        Sum += Cnt[K - A[x]] * y;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (scanf("%d%d", &N, &K) != EOF)
    {
        S = sqrt(N);
        memset(Cnt, 0, sizeof (Cnt));
        memset(Ans, 0, sizeof (Ans));
        for (int i = 1; i <= N; ++i)
            scanf("%d", &A[i]);
        scanf("%d", &M);
        int cnt = 0;
        for (int i = 1; i <= M; ++i)
        {
            int l1, l2, r1, r2;
            scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
            Q[++cnt].l = l1, Q[cnt].r = r2, Q[cnt].fl = 1, Q[cnt].id = i;
            Q[++cnt].l = l1, Q[cnt].r = l2 - 1, Q[cnt].fl = -1, Q[cnt].id = i;
            Q[++cnt].l = r1 + 1, Q[cnt].r = r2, Q[cnt].fl = -1, Q[cnt].id = i;
            Q[++cnt].l = r1 + 1, Q[cnt].r = l2 - 1, Q[cnt].fl = 1, Q[cnt].id = i;
        }

        sort(Q + 1, Q + cnt + 1, cmp);
        int l = 1, r = 0;
        Sum = 0;
        for (int i = 1; i <= cnt; ++i)
        {
            while (r < Q[i].r)
                update(++r, 1), Cnt[A[r]] ++;
            while (r > Q[i].r)
                Cnt[A[r]] --, update(r--, -1);
            while (l < Q[i].l)
                Cnt[A[l]] --, update(l++, -1);
            while (l > Q[i].l)
                update(--l, 1), Cnt[A[l]] ++;
            Ans[Q[i].id] += Sum * Q[i].fl;
        }

        for (int i = 1; i <= M; ++i)
            printf("%d\n", Ans[i]);
    }
    return 0;
}