水题笔记_ hzwer与逆序对 + Luogu_1908逆序对 [线段树, 权值线段树, 逆序对]

旧题新做

↑: 舒老师: “我奶一口能过25”

舒化奶之可见一斑

懵逼的 题目

传送至 Codevs
传送至 Luogu

扯淡的 题解

水…权值线段树模板, CV那个比较毒瘤必须用树状数组

沙茶的 代码

hzwer与逆序对

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (1000000 + 5)
#define LL long long
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define max(a, b) ((a) > (b) ? (a) :(b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define lowbit(x) ((x) & (-x))
using namespace std;
LL ans;
int n;
int a[MAXN];
LL b[MAXN];
int c[MAXN];
void js();
void xg(int);
int cx(int);
void init();
void solve();
bool cmp(int, int);
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
c[i] = a[i];
}
init();
solve();
printf("%lld", ans);
return 0;
}
void init()
{
sort(c + 1, c + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int x = lower_bound(c + 1, c + n + 1, a[i]) - c;
a[i] = x;
}
}
void solve()
{
for (int i = 1; i <= n; i++)
{
ans += cx(n) - cx(a[i]);
xg(a[i]);
}
}

void xg(int wz)
{
for (int i = wz; i <= n; i += lowbit(i))
++b[i];
}
int cx(int wz)
{
int re = 0;
for (int i = wz; i > 0; i -= lowbit(i))
{
re += b[i];
}
return re;
}
bool cmp(int x, int y)
{
return x < y;
}

逆序对(模拟一遍过高考一遍过23333)

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
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define max(a, b) ((a) > (b) ? (a) :(b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
struct node
{
int le;
int ri;
int zh;
}b[MAXN << 2];
int ans;
int n;
int a[MAXN];
int c[MAXN];
void js(int, int, int);
void xg(int, int);
int cx(int, int, int);
void init();
void solve();
bool cmp(int, int);
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
c[i] = a[i];
}
init();
solve();
printf("%d", ans);
return 0;
}
void init()
{
sort(c + 1, c + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int x = lower_bound(c + 1, c + n + 1, a[i]) - c;
a[i] = x;
}
}
void solve()
{
js(1, 1, n);
for (int i = 1; i <= n; i++)
{
ans += cx(1, a[i], n);
xg(1, a[i]);
}
}
void js(int dq, int le, int ri)
{
b[dq].zh = 0;
b[dq].le = le, b[dq].ri = ri;
if (le == ri)
return ;
int mi = (le + ri) >> 1;
js(LS(dq), le, mi);
js(RS(dq), mi + 1, ri);
}
void xg(int dq, int wz)
{
if (b[dq].le == b[dq].ri && b[dq].le == wz)
{
++b[dq].zh;
return ;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (wz <= mi)
xg(LS(dq), wz);
else
xg(RS(dq), wz);
b[dq].zh = b[LS(dq)].zh + b[RS(dq)].zh;
}
int cx(int dq, int le, int ri)
{
if (b[dq].le == le && b[dq].ri == ri)
{
return b[dq].zh;
}
int mi = (b[dq].le + b[dq].ri) >> 1;
if (le > mi)
return cx(RS(dq), le, ri);
else if (ri <= mi)
return cx(LS(dq), le, ri);
else
return cx(LS(dq), le, mi) + cx(RS(dq), mi + 1, ri);
}
bool cmp(int x, int y)
{
return x < y;
}

By 傻叉 Cansult