LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 301 个字)

10122. 「一本通 4.2 练习 1」天才的记忆

题意

给你一大串数字（编号为 $1$ 到 $N$，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 $M$ 个询问，每次询问就给你两个数字 $A,B$，要求你瞬间就说出属于 $A$ 到 $B$ 这段区间内的最大数。

思路

典型的RMQ模板题啦。

先把一开始的一大串数字塞入RMQ。然后询问就好啦。没有一点坑。。。

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
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
const int N=2e5+5,M=1e6;
using namespace std;
inline ll read(){
	char ch=getchar();ll res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(ll zx){
	if(zx<0) zx=-zx,putchar('-');
	if(zx<10) putchar(zx+'0');
	else{
		write(zx/10);
		putchar(zx%10+'0');
	}
}
ll n,m,f[N][20],st[N],las[M<<1];
void ST(){
	for(ll j=1;(1<<j)<=n;j++){
        for(ll i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
ll find(ll l,ll r){
	if(st[l]==l) return l;
	if(st[r]<l) return r+1;
	int L=l,R=r;
	while(L<=R){
		int m=L+R>>1;
		if(st[m]<l) L=m+1;
		else R=m-1;
	}
	return L;
}
int main(){
	n=read();
	for(ll i=1;i<=n;i++){
		int x=read();
		f[i][0]=x;
	}
	ST();m=read();
	for(ll i=1;i<=m;i++){
		ll L,R;
		L=read();R=read();int ans=RMQ(L,R);
		write(ans);putchar('\n');
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 345 个字)

10123. 「一本通 4.2 练习 2」Balanced Lineup

题意

FJ 准备了 $Q$ 个可能的牛的选择和所有牛的身高。他想知道每一组里面最高和最低的牛的身高差别。

思路

典型的RMQ模板题啦。

先把一开始的一大串数字塞入RMQ。然后询问就好啦。没有一点坑。。。

注意RMQ2次就好了啊

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
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
const int N=2e5+5,M=1e6;
using namespace std;
inline ll read(){
	char ch=getchar();ll res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(ll zx){
	if(zx<0) zx=-zx,putchar('-');
	if(zx<10) putchar(zx+'0');
	else{
		write(zx/10);
		putchar(zx%10+'0');
	}
}
ll n,m,f[N][20],st[N],las[M<<1],f2[N][20];
void ST(){
	for(ll j=1;(1<<j)<=n;j++){
        for(ll i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
void ST2(){
	for(ll j=1;(1<<j)<=n;j++){
        for(ll i=1;i+(1<<j)-1<=n;i++){
            f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ2(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return min(f2[l][k],f2[r-(1<<k)+1][k]);
}
int main(){
	n=read();m=read();
	for(ll i=1;i<=n;i++){
		int x=read();
		f2[i][0]=f[i][0]=x;
	}
	ST();ST2();
	for(ll i=1;i<=m;i++){
		ll L,R;
		L=read();R=read();int ans=RMQ(L,R)-RMQ2(L,R);
		write(ans);putchar('\n');
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 347 个字)

10120. 「一本通 4.2 例 2」最敏捷的机器人

题意

首先，他们面前会有一排共 $n$ 个数，它们比赛看谁能最先把每连续 $k$ 个数中最大和最小值写下来，当然，这些机器人运算速度都很快，它们比赛的是谁写得快。

思路

模板题。不介绍。

RMQ问题分别做一个最大值与最小值。

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
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
inline ll read(){
	char ch=getchar();ll res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(ll zx){
	if(zx<0) zx=-zx,putchar('-');
	if(zx<10) putchar(zx+'0');
	else{
		write(zx/10);
		putchar(zx%10+'0');
	}
}
ll n,m,a[100010],f[100010][20],f2[100010][20];
void ST(){
	for(ll i=1;i<=n;i++) f[i][0]=a[i];
	for(ll j=1;(1<<j)<=n;j++) {
        for(ll i=1;i+(1<<j)-1<=n;i++) {
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
void ST2(){
	for(ll i=1;i<=n;i++) f2[i][0]=a[i];
	for(ll j=1;(1<<j)<=n;j++) {
        for(ll i=1;i+(1<<j)-1<=n;i++) {
            f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ2(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return min(f2[l][k],f2[r-(1<<k)+1][k]);
}
int main(){
	n=read();m=read();
	for(ll i=1;i<=n;i++) a[i]=read();
	ST();ST2();
	for(ll i=1;i<=n-m+1;i++){
		write(RMQ(i,i+m-1));
		putchar(' ');
		write(RMQ2(i,i+m-1));
		putchar('\n');
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 320 个字)

10121. 「一本通 4.2 例 3」与众不同

题意

定义完美序列：一段连续的序列满足序列中的数互不相同。

想知道区间 $[L,R]$ 之间最长的完美序列长度。

思路

设$las[x]$表示盈利$x$最近出现位置。

设$st[i]$表示以第$i$个数结尾的最长完美序列的起始位置。
$$
st[i]=max(st[i-1],las[a[i]+1])
$$
设$f[i]$表示以第$i$个数结尾的最长完美序列的长度
$$
f[i]=i-st[i]+1
$$
由$st$的递推式可知，$st$的值是一个非递减的序列。

对于一个询问区间$[l_i,r_i]$，该区间内的$st$值可能会有两种情况：

  • 左边一部分的$st$值不在区间内，即$<l_i$
  • 右边一部分的$st​$值不在区间内，即$\ge l_i​$

由于$st$的值具有单调性，所以这个边界可以通过二分得到。设求出的边界为$mid$_i，可得：
$$
st[l_i…mid_i-1]<l_i
$$

$$
st[mid_i…r_i]\ge l_i
$$

那么整个区间$[l_i,r_i]$的最长完美序列的长度可以分两部分来求。

  • 左边：很显然为$mid_i-l_i$

  • 右边：$MAX(m_i…r_i)$

所以右边的长度要使用ST表，即RMQ来求。

整个问题的时间复杂度：
$$
O((M+N) \times logN)
$$

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
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long
const int N=2e5+5,M=1e6;
using namespace std;
inline ll read(){
	char ch=getchar();ll res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(ll zx){
	if(zx<0) zx=-zx,putchar('-');
	if(zx<10) putchar(zx+'0');
	else{
		write(zx/10);
		putchar(zx%10+'0');
	}
}
ll n,m,f[N][20],st[N],las[M<<1];
void ST(){
	for(ll j=1;(1<<j)<=n;j++){
        for(ll i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
ll RMQ(ll l,ll r){
    ll k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
ll find(ll l,ll r){
	if(st[l]==l) return l;
	if(st[r]<l) return r+1;
	int L=l,R=r;
	while(L<=R){
		int m=L+R>>1;
		if(st[m]<l) L=m+1;
		else R=m-1;
	}
	return L;
}
int main(){
	n=read();m=read();
	for(ll i=1;i<=n;i++){
		int x=read();
		st[i]=max(st[i-1],las[x+M]+1);
		f[i][0]=i-st[i]+1;
		las[x+M]=i;
	}
	ST();
	for(ll i=1;i<=m;i++){
		ll L,R;
		L=read();R=read();L++;R++;
		ll mid=find(L,R),ans=0,tmp;
		if(mid>L) ans=mid-L;
		if(mid<=R){
			tmp=RMQ(mid,R);
			ans=max(ans,tmp);
		}
		write(ans);putchar('\n');
	}
	return 0;
}
LOJ刷题 / 2019寒假刷题计划
2 分钟 读完 (大约 255 个字)

10119. 「一本通 4.2 例 1」数列区间最大值

题意

这是一道模板题。

输入一串数字，给你 $M​$ 个询问，每次询问就给你两个数字 $X,Y​$，要求你说出 $X​$ 到 $Y​$ 这段区间内的最大数。

思路

模板题。不介绍。

RMQ问题

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
#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	char ch=getchar();int res=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
	return res*f;
}
inline void write(int zx){
	if(zx<0) zx=-zx,putchar('-');
	if(zx<10) putchar(zx+'0');
	else{
		write(zx/10);
		putchar(zx%10+'0');
	}
}
int n,m,a[100010],f[100010][20];
void ST(){
	for(int i=1;i<=n;i++) f[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int l,int r){
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	ST();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();
		write(RMQ(l,r));
		putchar('\n');
	}
	return 0;
}
关注我

链接

分类

标签云

Link Cut Tree RMQ Splay bfs dp fhq treap spfa 二分 博弈论 堆 差分 异或 数论 斜率优化 暴力 最长链 枚举 树状数组 树链剖分 模拟 线性筛 线段树 背包 贪心 通知

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1

最新文章

归档

标签

Link Cut Tree 1
RMQ 5
Splay 2
bfs 1
dp 11
fhq treap 1
spfa 9
二分 3
博弈论 1
堆 1
差分 4
异或 1
数论 1
斜率优化 1
暴力 1
最长链 1
枚举 1
树状数组 6
树链剖分 1
模拟 1
线性筛 1
线段树 5
背包 1
贪心 1
通知 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×