[心痛]线段树或树状数组求逆序数

原文地址

线段树或树状数组求逆序数

求逆序数的方法有分治,归并,本文只介绍线段树或树状数组求逆序数的办法,众所周知,线段树和树状树可以用来解决区间操作问题,就是因为这两个算法区间操作的时间复杂度很低O(logN),才让这种方法具有可行性。

首先先来看一个序列   6 1 2 7 3 4 8 5,此序列的逆序数为5+3+1=9。冒泡法可以直接枚举出逆序数,但是时间复杂度太高O(n^2)。冒泡排序的原理是枚举每一个数组,然后找出这个数后面有多少个数是小于这个数的,小于它逆序数+1。仔细想一下,如果我们不用枚举这个数后面的所有数,而是直接得到小于这个数的个数,那么效率将会大大提高。

总共有N个数,如何判断第i+1个数到最后一个数之间有多少个数小于第i个数呢?不妨假设有一个区间 [1,N],只需要判断区间[i+1,N]之间有多少个数小于第i个数。如果我们把总区间初始化为0,然后把第i个数之前出现过的数都在相应的区间把它的值定为1,那么问题就转换成了[i+1,N]值的总和。再仔细想一下,区间[1,i]的值+区间[i+1,N]的值=区间[1,N]的值(i已经标记为1),所以区间[i+1,N]值的总和等于N-[1,i]的值!因为总共有N个数,不是比它小就是比它(大或等于)。

现在问题已经转化成了区间问题,枚举每个数,然后查询这个数前面的区间值的总和, i-[1,i] 既为逆序数。

线段树预处理时间复杂度O(NlogN),N次查询和N次插入的时间复杂度都为O(NlogN),总的时间复杂度O(3*NlogN)

树状数组不用预处理,N次查询和N次插入的时间复杂度都为O(NlogN),总的时间复杂度O(2*NlogN)

线段树:
 

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
// 线段树
#include <stdio .h>
#include <string .h>
#include <stdlib .h>
#define MAX 51000
#define MID(a,b) (a+b)>>1
#define R(a) (a< <1|1)
#define L(a) a<<1
typedef struct {
int num,left,right;
}Node;
int ans[MAX];
Node Tree[MAX<<2];
int n;

void Build(int t,int l,int r) //以1为根节点建立线段树
{
int mid;
Tree[t].left=l,Tree[t].right=r;
if(Tree[t].left==Tree[t].right)
{
Tree[t].num=0;
return ;
}
mid=MID(Tree[t].left,Tree[t].right);
Build(L(t),l,mid);
Build(R(t),mid+1,r);
}

void Insert(int t,int l,int r,int x) //向以1为根节点的区间[l,r]插入数字1
{
int mid;
if(Tree[t].left==l&&Tree[t].right==r)
{
Tree[t].num+=x;
return ;
}
mid=MID(Tree[t].left,Tree[t].right);
if(l>mid)
{
Insert(R(t),l,r,x);
}
else if(r< =mid)
{
Insert(L(t),l,r,x);
}
else
{
Insert(L(t),l,mid,x);
Insert(R(t),mid+1,r,x);
}
Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
}

int Query(int t,int l,int r) //查询以1为根节点,区间[l,r]的和
{
int mid;
if(Tree[t].left==l&&Tree[t].right==r)
return Tree[t].num;
mid=MID(Tree[t].left,Tree[t].right);
if(l>mid)
{
return Query(R(t),l,r);
}
else if(r<=mid)
{
return Query(L(t),l,r);
}
else
{
return Query(L(t),l,mid)+Query(R(t),mid+1,r);
}
}


int main()
{
int a,n,i,t;
scanf("%d",&t);
long long int k;
while(t--)
{
scanf("%d",&n);
memset(Tree,0,sizeof(Tree)); //初始化线段树
Build(1,1,n);
for(i=1;i<=n;i++) //输入n个数
{
scanf("%d",&ans[i]);
}
for(i=1,k=0;i<=n;i++)
{
a=ans[i];
Insert(1,a,a,1); //把线段树[ans[i],ans[i]]区间的值插入为1
k=k+(i-Query(1,1,a)); //查询区间[1,ans[i]]值的总和,逆序数等于i-[1,ans[i]]
}
printf("%lld\n",k);
}
return 0;
}

树状数组:

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
// 树状数组
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 100010
int c[MAX],a[MAX],ans[MAX],n;

int Lowbit(int x) //返回二进制最后一个1所表示的数
{
return x&(-x);
}

void Updata(int x) //向前更新
{
while(x<=n)
{
c[x]++;
x+=Lowbit(x);
}
}

int Sum(int x) //向后更新求和
{
int sum=0;
while(x>0)
{
sum+=c[x];
x-=Lowbit(x);
}
return sum;
}

int main()
{
int i,t,k;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&ans[i]);
}
memset(c,0,sizeof(c)); //初始化树状数组
for(i=1,k=0;i<=n;i++)
{
Updata(ans[i]); //向后更新节点ans[i].k
k=k+(i-Sum(ans[i])); //向前查询节点ans[i].k
}
printf("%d\n",k);
}
return 0;
}

 

FFZU-ACM月赛不行了

线段树/树状数组的另一种用法不会,它的逆向问题更不会

Mac OS 下怎样写作业

我本以为 存在WPS office for Mac而不存在Microsoft office for Mac,真实情况正好相反...

OOP outline 

  • 抽象
  • 继承
  • 封装
  • 多态

【GDUT-ACM】大灌水

难以容忍的两个WA
Problem C

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
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
priority_queue<LL,vector<LL>,greater<LL> > que;
CLEAR(a);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%lld",&a[i]);
sort(a,a+n);
for(int i=1;i<=m;i++)
{
que.push(a[n-i]);
}
LL ans=a[n-1];
for(int i=n-m-1;i>=0;i--)
{
LL k=que.top();
que.pop();
que.push(k+a[i]);
ans=max(ans,k+a[i]);
}
printf("%lld\n",ans);
}
return 0;
}

Problem D

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
const double pi = acos(-1.0);
const int maxn=2e5;
const LL maxl=1e5+10;
const int inf=99999999;
const float eps=1e-3;

LL a[maxn];
bool vis[maxl];
int n,m;
vector<LL> vec;

void init();
void solve();
void outp();

void get_prime()
{
vec.clear();
CLEAR(vis);
int k=0;
for (int i = 2; i < maxl;i++)
if(!vis[i])
{
k++;
vec.push_back(i);
for (int j = 1; i * j <= maxl; j++)
{
vis[i * j] = 1;
}
}
}

int getfac(LL n)
{
if (n<2) return 0;
int h=0,res=0;
while(h<vec.size())
{
if (n%vec[h]==0) res++;
while (n%vec[h]==0) n/=vec[h];
h++;
}
return res;
}

LL pow2(LL n)
{
if (n<=0) return 1;
else if (n==1) return 2;
else if (n&1)
{
int k=pow2((n-1)>>1);
return (k*k)<<1;
}
else
{
int k=pow2(n>>1);
return k*k;
}
}

int main()
{
get_prime();
int T;
LL n,m;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
if (m%n) {printf("0\n");continue;}
else if (n==1) {printf("1\n");continue;}
LL t=m/n;
//printf("%d\n",getfac(t));
LL ans=pow2(getfac(t)-1);
printf("%lld\n",ans);
}
return 0;
}

void solve()
{
}

void init()
{

}

void outp()
{
printf("\n");
}

/**************************************************************
Problem: 1113
User: semprathlon
Language: C++
Result: Wrong Answer
****************************************************************/

=====================================
Problem F
罕见的PE,输出末尾不能有多余空格,防不胜防

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
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
const double pi = acos(-1.0);
const int maxn=200;
const int inf=99999999;
const float eps=1e-3;

int a[maxn];

void init();
void solve();
void outp();

int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
CLEAR(a);
scanf("%d%d",&n,&m);
int mina=inf,h=0;
for(int i=0;i<m;i++)
{
int k;
scanf("%d",&k);
if (k<mina)
{
mina=k;
a[h++]=k;
}
}
sort(a,a+h);
int k=0;
for(int i=1;i<=n;i++)
{
if (k<h-1&&a[k+1]<=i) k++;
if (i<n) printf("%d ",a[k]);
else printf("%d",a[k]);
}
puts("");
}
return 0;
}

void solve()
{
}

void init()
{

}

void outp()
{
printf("\n");
}

/**************************************************************
Problem: 1121
User: semprathlon
Language: C++
Result: Accepted
Time:0 ms
Memory:1488 kb
****************************************************************/

Problem G

1
2
3
4
5
6
7
8
9
int main()
{
while(~scanf("%d",&n))
{
int k=n/3;
printf("%d\n",(n%3)?2*k+n%3-1:2*k);
}
return 0;
}

Problem E
裸的并查集

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
const int maxn=2e5;
const int inf=99999999;
const float eps=1e-3;

int f[maxn];
int n,m;

int getf(int n)
{
if (f[n]==n) return n;
else return f[n]=getf(f[n]);
}

bool unite(int u,int v)
{
int x=getf(u);
int y=getf(v);
if (x!=y)
{
f[ y ]=x;return 1;
}
else return 0;
}


int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
CLEAR(f);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
unite(u,v);
}
int ans=-1;
for(int i=1;i<=n;i++)
if (f[i]==i) ans++;
printf("%d\n",ans);
}
return 0;
}

/**************************************************************
Problem: 1118
User: semprathlon
Language: C++
Result: Accepted
Time:264 ms
Memory:2264 kb
****************************************************************/

=====================
还有个来不及提交的![个人原因,15:26才加入比赛
Problem H

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
const int maxn=2e4;
const int inf=99999999;
const float eps=1e-3;
const pair<int,int> p0=make_pair(0,0);

int a[maxn],f1[maxn],f2[maxn];
pair<int,int> g1[maxn],g2[maxn];

void init();
void solve();
void outp();


int main()
{
int T,n,m;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
CLEAR(a);
CLEAR(f1);
CLEAR(f2);
CLEAR(g1);
CLEAR(g2);
scanf("%d",&a[1]);
f1[1]=f2[1]=0;
g1[1]=g2[1]=p0;
for(int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
if (f1[i-1]<f2[i-1])
{
g1[i]=make_pair(a[i],g1[i-1].second);
g2[i]=make_pair(g1[i-1].first,a[i]);
f1[i]=f1[i-1]+abs(a[i]-g1[i-1].first);
f2[i]=f2[i-1]+abs(a[i]-g1[i-1].second);
}
else
{
g1[i]=make_pair(a[i],g2[i-1].second);
g2[i]=make_pair(g2[i-1].first,a[i]);
f1[i]=f1[i-1]+abs(a[i]-g2[i-1].first);
f2[i]=f2[i-1]+abs(a[i]-g2[i-1].second);
}

}
printf("%d\n",min(f1[n],f2[n]));
}
}

【GDUT-ACM】水题差点写跪了,囧

Problem B: 神奇的编码

Description

假如没有阿拉伯数字,我们要怎么表示数字呢
小明想了一个方法如下:
1 -> A
2 -> B
3 -> C
….
25 -> Y
26 -> Z
27 -> AA

28 -> AB
….

现在请你写一个程序完成这个转换

Input

输入的第一个数为一个正整数T,表明接下来有T组数据。
每组数据为一个正整数n ( n <= 1000)

Output

对于每个正整数n,输出他对应的字符串

Sample Input

3 1 10 27

Sample Output

A J AA

没什么神奇的,本质还是进制转换

心急如焚之时,代码风格无比混乱;那个26的倍数的特殊处理,是个大痛点,AC一次耗时25min

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
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define CLEAR(a) memset((a),0,sizeof((a)))

using namespace std;

typedef long long LL;
const double pi = acos(-1.0);
const int maxn=1e4;
const int inf=99999999;
const double eps=1e-3;


int n;

void init();
void solve();
void outp();

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
string str;
scanf("%d",&n);
//n+=(n-1)/26;
//n++;
//if (n%26==0) n--;
while(n)
{
char ch=(n%26)?n%26+'A'-1:(n--,'Z');
str=ch+str;
n/=26;
}
printf("%s",str.c_str());
puts("");
}
return 0;
}

void solve()
{
}

void init()
{
for(int i=1;i<=n;i++)
{

}
}

void outp()
{
printf("\n");
}

/**************************************************************
Problem: 1112
User: semprathlon
Language: C++
Result: Accepted
Time:0 ms
Memory:1484 kb
****************************************************************/

=======================分隔符==============================

题E
自我感觉正确,可是未能在结束前提交。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n;

char* solve(double v,double d);

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
double v,d;
scanf("%lf%lf",&v,&d);
puts(solve(v,d));
}
return 0;
}

char* solve(double v,double d)
{
return (char*)(((v*v*sqrt(2.0))/10.0-d>eps)?"Fire":"Retreat");
}

题A
耗时16min,循环队列,简直没有TLE/MLE的理由

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
int n;
int que[maxsize],h,r;

int EnQ(int id)
{
if ((r+1)%maxsize!=h)
{
r=(r+1)%maxsize;
que[r]=id;
return 0;
}
else return -1;
}

int DeQ()
{
if (h!=r)
{
int t=h;
h=(h+1)%maxsize;
return que[t];
}
else return -1;
}

int Query(int k)
{
if (h==r) return -1;
int t=(h<=r)?r-h:maxsize-r+h;
return (t>=k)?que[(h+k)%maxsize]:-1;
}

int main()
{
int T;
scanf("%d",&T);
while(T--)
{
CLEAR(que);h=r=0;
int cas,k;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&cas);
switch(cas)
{
case 1:scanf("%d",&k);EnQ(k);break;
case 2:DeQ();break;
case 3:scanf("%d",&k);
if (Query(k)>=0) printf("%d\n",Query(k));
else puts("na li you zhe me duo ren");
break;
}
}
}
return 0;
}