利用树状数组记录小于a[i]数字的个数
树状数组的模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int lowbit(int x)
{
return x&(-x);
}
int tr[N];
int n;
void update(int x,int i)
{
while(i<=n)
{
tr[i]+=x;
i+=lowbit(i);
}
}
int getval(int i)
{
int ans=0;
while(i)
{
ans+=tr[i];
i-=lowbit(i);
}
return ans;
}
|
树状数组的一个应用——记录数字出现的情况
比如说数字a[i]，出现的时候将其在树状数组的位置+1，之后的a[j]，就可以取树状数组的记录值，来得出有几个大于a[j]的数字。
题目链接：P10589
题目大意：有n个数字组成的排列，问能组成机组V型和倒V型。
思路：按顺序遍历排列数字，对于ai，可以用树状数组得出前面遍历过的数字（即左侧）有多少小于ai的，同时因为左侧有i个数字，故大于的有i-t1-1个；上侧共n-ai个点，故可以求出4个方位的点个数，做乘法组合。
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
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
using namespace std;
const int N = 1000000;
void solve();
void init();
int lowbit(int x)
{
return x&(-x);
}
int tr[N];
int n;
void update(int x,int i)
{
while(i<=n)
{
tr[i]+=x;
i+=lowbit(i);
}
}
int getval(int i)
{
int ans=0;
while(i)
{
ans+=tr[i];
i-=lowbit(i);
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
init();
while(t--)solve();
cout.flush();
return 0;
}
void solve()
{
cin>>n;
veci a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
int ans1=0,ans2=0;
for(int i=1;i<=n;i++)
{
int t1=getval(a[i]);
int t2=i-t1-1;
ans1+=t2*(n-a[i]-t2);
ans2+=t1*(a[i]-1-t1);
update(1,a[i]);
}
cout<<ans1<<' '<<ans2<<endl;
}
void init()
{
}
|
