求逆序对（树状数组）
标签：struct 本质 sample content NPU ems sum lld 个数
求逆序对
描述
给定一个序列a1,a2,…,an，如果存在iaj，那么我们称之为逆序对，求逆序对的数目
输入
第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
N
输出
两行，第一行为所有逆序对总数，第二行为本质不同的逆序对总数。
输出
3
1
1 #include 2 #define ll long long
3 #define mod 1000000009
4 #define lowbit(x) x&(-x)
5 using namespace std;
6 ll n,sum[100005],b[100005],ans,num,f[100005],in[100005];
7 struct data{
8 ll v,id;
9 }a[100005];
10 void add(ll x,ll val)
11 {
12 while(x100001)
13 {
14 sum[x]+=val;
15 x+=lowbit(x);
16 }
17 }
18 ll ask(ll x)
19 {
20 ll ans=0;
21 while(x)
22 {
23 ans+=sum[x];
24 x-=lowbit(x);
25 }
26 return ans;
27 }
28 int main()
29 {
30 scanf("%lld",&n);
31 for(ll i=1;i)
32 scanf("%lld",&a[i].v);
33 for(ll i=1;i)
34 {
35 add(a[i].v,1);
36 ans+=i-ask(a[i].v);
37 }
38 memset(sum,0,sizeof(sum));
39 for(ll i=n;i>=1;i--)
40 {
41 if(in[a[i].v]==0)
42 {
43 add(a[i].v,1);
44 in[a[i].v]=1;
45 }
46 num-=f[a[i].v];
47 f[a[i].v]=ask(a[i].v-1);
48 num+=f[a[i].v];
49 }
50 printf("%lld\n%lld",ans,num);
51 return 0;
52 }
求逆序对（树状数组）
标签：struct 本质 sample content NPU ems sum lld 个数
原文地址：https://www.cnblogs.com/sbwll/p/13191425.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
求逆序对（树状数组）
文章链接：http://soscw.com/index.php/essay/82929.html
评论