USACO 【Haircut G】

题库：USACO
题目：Haircut G
题号：洛谷P6278
link：https://www.luogu.com.cn/problem/P6278

不用求逆序对的方法也可以做。

逆序对指，设一个数列中有A和B两个元素，如果A的值大于B的值，且A的下标小于B的下标，称A和B为一对逆序对。

首先观察样例得知，如果数列中出现过j - 1，那么就会出现逆序对。具体出现多少呢？设当j增加1时，如果i点的值不变，那么称作一次修改。因为j在不断提高，所以j - 1也在不断提高，因此后来修改的值，肯定大于前面修改的值，并且小于没被修改过的值。不难得出，每一次修改，都会增加1 ~ i - 1中没被修改过的数量个逆序对。

所以我们只需要求出在当前j时，如果j - 1这个值出现过，答案就累加1 ~ i - 1中没被修改过的数量（i为j - 1这个值在原数列中的位置），问题就是求1 ~ i - 1中有多少个没被修改过的呢？暴力肯定是不行的，n²会炸，所以考虑线段树维护，具体参见代码。

code：

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 using namespace std;
 4 int n, q[100010], z[100010];
 5 map < int, int > ap[100010];
 6 struct tree//线段树 
 7 {
 8     int l, r, val;
 9 }stu[800010];
10 void build(int u, int l, int r)
11 {
12     int mid = (l + r) >> 1;
13     stu[u].l = l;
14     stu[u].r = r;
15     if(l == r)
16     {
17         stu[u].val = 1;
18         return;
19     }
20     build(u * 2, l, mid);
21     build(u * 2 + 1, mid + 1, r);
22     stu[u].val = stu[u * 2].val + stu[u * 2 + 1].val;
23     return;
24 }
25 void change(int u, int l, int r)
26 {
27     if(stu[u].l > r || stu[u].r < l)
28     {
29         return;
30     }
31     if(stu[u].l == stu[u].r)
32     {
33         stu[u].val = 0;
34         return;
35     }
36     change(u * 2, l, r);
37     change(u * 2 + 1, l, r);
38     stu[u].val = stu[u * 2].val + stu[u * 2 + 1].val;
39     return;
40 }
41 int find(int u, int l, int r)
42 {
43     if(stu[u].l > r || stu[u].r < l)
44     {
45         return 0;
46     }
47     if(stu[u].l >= l && stu[u].r <= r)
48     {
49         return stu[u].val;
50     }
51     return find(u * 2, l, r) + find(u * 2 + 1, l, r);
52 }
53 signed main()
54 {
55     scanf("%d", &n);
56     for(register int i = 1; i <= n; ++i)
57     {
58         scanf("%d", &q[i]);
59         ap[q[i]][++z[q[i]]] = i;//记录q[i]出现的位置 
60     }
61     build(1, 1, n);
62     long long ans = 0;
63     puts("0");
64     for(register int i = 1; i < n; ++i)
65     {
66         if(!ap[i - 1][1])//没有出现过j - 1就直接输出上一次的逆序对数量，并continue 
67         {
68             printf("%lld
", ans);
69             continue;
70         }
71         for(register int j = 1; j <= z[i - 1]; ++j)
72         {
73             change(1, ap[i - 1][j], ap[i - 1][j]);//记住要先改再搜，否则如果出现多次修改，答案会比正确的要多 
74         }
75         for(register int j = 1; j <= z[i - 1]; ++j)
76         {
77             ans += find(1, 1, ap[i - 1][j] - 1);
78         } 
79         printf("%lld
", ans);
80     }
81     return 0;
82 }