数据结构（并查集，ST表）

并查集

数据结构：

//数据结构
const int N = 1e3;
int fa[N]; //fa:father
1
2
3

基本操作：
查找：

//递归写法
int get(int x){
	if(fa[x]==0) return fa[x]=x; //初始化 
	return fa[x]==x?x:fa[x]=get(fa[x]); //回溯寻找最祖先，并且路径压缩 
}
1
2
3
4
5

合并：

void merge(int x,int y){
	fa[get(y)]=get(x); //让x的最祖先作为y树的最祖先 
}
1
2
3

ST表

维护区间最大值（不修改元素的值）

数据结构：

const int N=2e5+5;
int a[N][20]; //a[i][j]:表示以i为起点，长度为2^i的区间的最值。
1
2

预处理出区间最值

for(int i=1;i<=m;++i) scanf("%d",&a[i][0]); //读入序列
	for(int i=1;(1<<i)<=m;++i) //遍历指数,2^i=区间长度
		for(int j=1;j+(1<<i)-1<=m;++j) //遍历区间起点 
			a[j][i]=max(a[j][i-1],a[j+(1<<(i-1))][i-1]);
1
2
3
4

查询：

int ask(int l,int r){
	int k=log2(r-l+1);
	return max(a[l][k],a[r-(1<<k)+1][k]);
}
1
2
3
4

好题，练手题：D. Rorororobot

参考代码：

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int a[N][20],n,m,q;
int ask(int l,int r){
	int k=log2(r-l+1);
	return max(a[l][k],a[r-(1<<k)+1][k]);
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;++i) scanf("%d",&a[i][0]);
	for(int i=1;(1<<i)<=m;++i) //遍历指数,2^i=区间长度
		for(int j=1;j+(1<<i)-1<=m;++j) //遍历区间起点 
			a[j][i]=max(a[j][i-1],a[j+(1<<(i-1))][i-1]);
	scanf("%d",&q);
	int x,y,x2,y2,k;
	while(q--){
		scanf("%d%d%d%d%d",&x,&y,&x2,&y2,&k);
		if((x-x2)%k==0 && (y-y2)%k==0 && (n-x)/k*k+x>ask(min(y,y2),max(y,y2)))
			puts("YES");
		else puts("NO");
	}
	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