Rainy2k
0%

树状数组

Posted on Edited on

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int c[maxn * 2];
int lowbit(int x) {
    return x & (-x);
}

void add(int i,int d) {
    while(i<maxn*2) {
        c[i] += d;
        i += lowbit(i);
    }
}

int query(int i) {
    int ret = 0;
    while(i>0) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}

例题

Codeforces1324D Pair of Topics

https://codeforces.com/contest/1324/problem/D

给定a,ba,b序列,求有多少对i<ji<j且ai+aj>bi+bja_i+a_j>b_i+b_j

解法1:按照值从大到小插入
代码 : https://xlorpaste.cn/2rdsp4

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn];
int b[maxn];
int c[maxn];
struct Node {
    int v, index;
    bool operator<(const Node& b) const {
        if(v==b.v) {
            return index <b.index;//注意这里!!
        }
        return v < b.v;  //从小到大排序 
	}
} node[maxn];
int n;
void add(int i) {
	while(i<=n*2)
	{
		c[i]++;
		i+=i&(-i);	
	}
}
int sum(int i) {
	int res=0;
	while(i>0)
	{
		res+=c[i];
		i-=i&(-i);
	}
	return res;
}
vector<int> v;
int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
    }
    for(int i=1;i<=n;i++) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n;i++) {
        node[i].v = a[i] - b[i];
        node[i].index = i;
        node[i + n].v = b[i] - a[i];
        node[i + n].index = i + n;
    }
    long long ans = 0;
    sort(node + 1, node + 1 + 2 * n);
    for (int i = 2*n; i >=1;i--) {
        int id = node[i].index;
        int v = node[i].v;
        if(id<=n) {
            add(node[i].index);
            continue;
        }
        if(v<0)
            ans--;
        ans += sum(id - n);
    }
    cout<<ans<<endl;
}

解法2:按照序列顺序从小到大

代码 : https://xlorpaste.cn/3vucur

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int a[maxn], b[maxn], c[maxn * 2];
int lowbit(int x) {
    return x & (-x);
}

void add(int i,int d) {
    while(i<maxn*2) {
        c[i] += d;
        i += lowbit(i);
    }
}

int query(int i) {
    int ret = 0;
    while(i>0) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}

vector<int> v;

int main() {
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n;i++) {
        scanf("%d", &b[i]);
    }
    for (int i = 1; i <= n;i++) {
        v.push_back(a[i] - b[i]);
        v.push_back(b[i] - a[i]);
    }
    long long ans = 0;
    sort(v.begin(), v.end());
    for (int i = 1;i<=n;i++) {
        int x = b[i] - a[i];
        int y = a[i] - b[i];
        int id = upper_bound(v.begin(), v.end(), x) - v.begin() + 1;
        int id2 = upper_bound(v.begin(), v.end(), y) - v.begin() + 1;
        ans += (i - 1 - query(id));
        add(id2, 1);
    }
    cout << ans << endl;
}

解法3: 不需要树状数组

代码 : https://xlorpaste.cn/5oto9y

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
vector<int> v;
int a[maxn],b[maxn];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n;i++) {
        scanf("%d", &b[i]);
        v.push_back(a[i] - b[i]);
    }
    sort(v.begin(), v.end());
    long long ans = 0;
    for (int i = 1; i <= n;i++) {
        int id = upper_bound(v.begin(), v.end(), b[i] - a[i]) - v.begin();
        ans += (n  - id);
        if(a[i]-b[i]>b[i]-a[i])
            ans--;
    }
    ans /= 2;
    cout << ans << endl;
}