给定一个长度为 n 的整数序列 a1 , a2 , … , an。我们称一个二元组(i,j)是完美配对的，当且仅当 i<j 并且 ai−aj<j−i.求完美配对的二元组数目.

对于前 3 个测试点

1≤n≤103

对于后两个测试点

1≤n≤105

所有的测试点都满足

1≤ai≤105

输入格式：

1
2
n
a1 a2 ... an

输出格式：

输出完美配对的二元组数目

输入样例：

1
2
5
3 2 5 2 6

输出样例：

仅有一对二元组（1, 2）满足条件， 因为 3 - 2 = 2 - 1.

1
1

思路

暴力循环会超时，弄懂完美配对1再看本题

需要树状数组，没有学习过数据结构的话，本题可不了解，等知识积累到一定程度后，再学习树状数组是什么

只要两个元素满足ai−aj<j−i，即ai+i<aj+j

扫描给定数组，每扫描一个数ai，寻找前面已扫描过的满足ai+i<aj+j的数的数量，相当于寻找标记的aj+j为0到aj+j为(ai+i-1)的所有元素数

不再和完美配对1那样取num[arr[i] + i-1]值，而是取num[0]~num[arr[i] + i-1]的所有值的和

树状数组维护的是(x-lowbit(x),x]区间的和，具体参考代码

代码

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
#include <iostream>

using namespace std;

const int MAX_SIZE = 1e6 + 5;
long tr[MAX_SIZE], a[MAX_SIZE]; //注意数据范围，int会爆

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

void add(long x) {
    while(x < MAX_SIZE) {
        tr[x] += 1;
        x += lowbit(x);
    }
}

long sum(long x) {
    long ret = 0;
    while(x > 0) {
        ret += tr[x];
        x -= lowbit(x);
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    long ret = 0;
    for(int i = 1; i <= n; i++) {
        ret += sum(a[i] + i - 1);
        add(a[i] + i);
    }
    cout << ret << endl;
    return 0;
}