Chika and Friendly Pairs (莫队+ 树状数组 + 离散化 + 预处理)

ACM 阅读量

一个区间中如果存在这样的一对数字 $（A,B）$ 并且 $abs（A-B）$ 不大于 $K$ ，我们就称这一对数字为奇妙的数字对。现在给出你长为n的序列，求奇妙数字对 $（i，j）$ 在 $[L,R]$ 中的个数。

题目链接

Hdu-6534-Chika and Friendly Pairs

输入输出格式

输入格式：

第一行输入三个数字 $N,M,K$;

第二行有 $N$ 个数字，代表序列。

第三行有 $M$ 次询问 $L,R$

输出格式

输出$M$行。每行一个数字，代表询问区间的奇妙数字对的个数。

输入输出样例

输入样例

1
2
3
4
5
6
7
7 5 3   
2 5 7 5 1 5 6   
6 6   
1 3   
4 6   
2 4   
3 4

输出样例

1
2
3
4
5
0
2
1
3
1

说明

对于 $ 100% $ 的数据，$ 1 \leq n \leq 27000, 1 \leq m \leq 27000， 1 \leq k \leq 10 ^ 9 ， n个数字都不超过10^9$。

题解

首先，看到题目中的数据范围 $27000$ 为什么不是 $1e5$ 为什么不是 $3e4$ $?$ 想到可能可以用分块或者莫队去暴力。 可是想了很久也没想到用莫队或者分块去维护什么东西 我好菜 。慢慢去想。

  • 首先很容易想到，对于这样的数对，我们可以枚举这个序列直接 $n^2$ 暴力去求解，此时时间复杂度为$O(m * n^2)$ 显而易见是不可取的

  • 想想如何去降低一下时间复杂度$?$ 对于题目中的式子 $|A - B| \leq K $ 把他化简开可以的得到这样的一个式子$ -K \leq A - B \leq K $ 这样的话，对于某个区间内的所有数，能跟当前枚举出来的数 $x$ 组成满足题意的数对的，一定在 $[x-k,x+k]$ 这个区间里，我们只需要统计这个区间有多少个数就行了。这样每一侧的操作是 $O(m* L* L)$ (L代表区间长度),当然还是会T，还要优化。但是现在问的是对于某个给定的区间内的所有数能够组成的合法数对个数，我们就不能对区间每个数都像上面这样子暴力去统计了。那要怎么办呢？。

  • 首先对于我们的 $M$ 次查询，如果每次都重新对一个区间进行查询一定会进行很多重复的查询，如果能利用这部分重复的信息就可以把时间复杂度再下一个级。使用莫队算法能够使得我们有效利用重叠区间所统计的答案，使时间复杂度变为 $O(m* \sqrt{L} * L)$。马上就对了！

  • 此时唯一还能优化的地方就是，再 $[L,R]$ 区间内符合的数的个数。对于每次查询和修改，不必要区间的每个数都重新跑一边，而利用不必过多的修改统计的树状数组，将 $O(L^2)$ 的查询变成 $O(L* \log L)$ 这个题就优化完了 总时间复杂度为 $O(m * \sqrt{n} * \log n)$

  • 对于区间 $[x-k,x+k]$ 我们需要先知道每个 $a_i$ 所对应的左右区间分别到哪里，所以预处理这个序列对 $x-k,x+k$ ，数据太大需要离散化，剩下的代码注释把。

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5+7;
int block,num,belong[MAXN],tree[MAXN],l[MAXN],r[MAXN];
int n,m,k,u,v,ans[MAXN];
int a[MAXN],b[MAXN],c[MAXN],tot;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c == '\r' || c == '\n');
	if(c == '-')
		flag = true;
	else num = c - '0';
	while(isdigit(c = getchar()))
		num = (num<<3) + (num<<1) + c - '0';
	return (flag ? -1 : 1) * num;
}

struct Node {
    int l,r,id;
    bool operator <(const Node &S)const {
        return (belong[l] ^ belong[S.l]) ? belong[l] < belong[S.l] : ((belong[l] & 1) ? r < S.r : r > S.r); //莫队奇偶玄学排序
    }
} data[MAXN];

void Build() {
    block = sqrt(n);
    num = n/block;
    if(n % block)
        num++;
    for(int i = 1; i <= n; i++)
        belong[i] = (i-1)/block + 1;
}

int lowbit(int x) {
    return x & (-x);
}

void Update(int x,int d) {
    for(int i = x; i <= tot; i += lowbit(i)) {
        tree[i] += d;
    }
}

int Sum(int x) {
    int ret = 0;
    for(int i = x;i > 0;i -= lowbit(i))
        ret += tree[i];
    return ret;
}


int main() {
    n = get_num();
	m = get_num();
	k = get_num();
    Build();
    for(int i = 1; i <= n; i++)
        a[i] = get_num(),b[i] = a[i];

    sort(b+1,b+1+n); //对数据进行离散化
    c[1] = b[1];
    tot = 1;
    for(int i = 2; i <= n; i++) {
        if(b[i] != b[i-1])
            c[++tot] = b[i];
    }
    for(int i = 1; i <= n; i++) { //预处理每个值所处的区间边界
        l[i] = lower_bound(c+1,c+1+tot,a[i] - k) - c;
        r[i] = upper_bound(c+1,c+1+tot,a[i] + k)- c - 1;
        a[i] = lower_bound(c+1,c+tot+1,a[i]) - c;
    }

    

    for(int i = 1; i <= m; i++) {
        data[i].l = get_num();
		data[i].r = get_num();
		data[i].id = i;
    }
    sort(data+1,data+1+m);
    int L = 1,R = 0,temp = 0;
    for(int i = 1; i <= m; i++) {
        int ql = data[i].l,qr = data[i].r;
        while(ql < L) {
            L--;
            temp += Sum(r[L]) - Sum(l[L] - 1);
            Update(a[L],1);
        }
        while(ql > L) {
            Update(a[L],-1);
            temp -= Sum(r[L]) - Sum(l[L] - 1);
            L++;
        }
        while(qr < R) {
            Update(a[R],-1);
            temp -= Sum(r[R]) - Sum(l[R] - 1);
            R--;
        }
        while(qr > R) {
            R++;
            temp += Sum(r[R]) - Sum(l[R] - 1);
            Update(a[R],1);
        }

        ans[data[i].id] = temp;
    }

    for(int i = 1; i <= m; i++) {
        printf("%d\n",ans[i]);
    }
    //printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
    return 0;
}

自闭历程

题目来源是2019CCPC湘潭邀请赛的一岛银牌题，但在这道题上有了一些变动，目前为止这是我写过最难的一道题，从这个题在我眼前出现，到搜题解把这个题AC一共用了3天的时间，让我持续自闭。后期还要把这个题拿出来在学一遍。从开始的暴力，到线段树维护区间差值，发现线段树的区间不能完全覆盖，到看到Luogu的P1102想到把式子拆分，用分块维护两个式子，发现时间复杂度还是过高，再到用莫队去利用多余数据，发现根本不知道怎么利用这个重复的查询，用主席树去求每个区间内的有多少个数超时的操作，等等等等……真的是把我目前已知的所有东西都用上了，一度陷入了自闭的状态，去网上搜题解也都搜不到，直到问了一个湘潭大学的金牌选手从他那里得知这到题目的出处，看了题解才过掉。一路自闭，一路慢慢搞懂，好难，我好菜。

题意延申

一个区间中如果存在这样的一对数字 $（A,B）$ 并且 $abs（A-B）$ 不小于 $K$ ，我们就称这一对数字为奇妙的数字对。现在给出你长为n的序列，求奇妙数字对 $（i，j）$ 在 $[L,R]$ 中的个数。 源自集训队WHY大佬出的题目，在原题的基础上改一下每个数字的上下界，稍作修改即可。

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e4 + 9;
struct Node {
    int l, r, id;
} q[MAXN];

int belong[MAXN], ans[MAXN];
int tree[MAXN * 4], c[MAXN * 4];
int r_r[MAXN], l_l[MAXN];
int b[MAXN], a[MAXN];
int res = 0;

bool cmp(Node a, Node b) { return ((belong[a.l] == belong[b.l]) ? (a.r < b.r) : (a.l < b.l)); }

int lowbit(int x) { return x & (-x); }
void add(int x, int v) {
    while (x <= MAXN * 3) {
        tree[x] += v;
        x += lowbit(x);
    }
}
int get(int x) {
    int ans = 0;
    while (x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    int u = sqrt(n), cnt = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        a[i] = x;
        c[++cnt] = x;
        c[++cnt] = x - k;
        c[++cnt] = x + k - 1;
        belong[i] = i / u + 1;
    }
    sort(c + 1, c + 1 + cnt);
    int num = unique(c + 1, c + 1 + cnt) - c - 1;

    for (int i = 1; i <= n; i++) {
        r_r[i] = lower_bound(c + 1, c + 1 + num, a[i] + k - 1) - c;
        l_l[i] = lower_bound(c + 1, c + 1 + num, a[i] - k) - c;
        b[i] = lower_bound(c + 1, c + 1 + num, a[i]) - c;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0, res = 0, sum = 0;
    for (int i = 1; i <= m; i++) {
        while (r < q[i].r) {
            r++;
            res += sum - get(r_r[r]) + get(l_l[r]);
            add(b[r], 1);
            sum++;
        }
        while (r > q[i].r) {
            add(b[r], -1);
            sum--;
            res -= sum - get(r_r[r]) + get(l_l[r]);
            r--;
        }
        while (l < q[i].l) {
            add(b[l], -1);
            sum--;
            res -= sum - get(r_r[l]) + get(l_l[l]);
            l++;
        }
        while (l > q[i].l) {
            l--;
            res += sum - get(r_r[l]) + get(l_l[l]);
            add(b[l], 1);
            sum++;
        }
        ans[q[i].id] = res;
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2018 - 2020 Never Give Up! All Rights Reserved.

访客数 : | 访问量 :