线段树

看视频学呀！

B站视频

基本线段树实现代码（B站）

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<stdio.h>

#define MAX_LEN 1000

void build_tree(int arr[],int tree[],int node,int start,int end){
	if(start==end){
		tree[node]=arr[start];
	}
	else{
		int mid=(start+end)/2;
		int left_node=2*node+1;
		int right_node=2*node+2;
		build_tree(arr,tree,left_node,start,mid);
		build_tree(arr,tree,right_node,mid+1,end);
		tree[node]=tree[left_node]+tree[right_node];
	}
}

void update_tree(int arr[],int tree[],int node,int start,int end,int idx,int val){
	if(start==end){
		arr[idx]=val;
		tree[node]=val;
	}
	else{
		int mid=(start+end)/2;
		int left_node=2*node+1;
		int right_node=2*node+2;
		if(idx>=start&&idx<=mid){
			update_tree(arr,tree,left_node,start,mid,idx,val);
		}
		else{
			update_tree(arr,tree,right_node,mid+1,end,idx,val);
		}
		tree[node]=tree[left_node]+tree[right_node];
	}
} 

int query_tree(int arr[],int tree[],int node,int start,int end,int L,int R){
	if(R<=start||L>end){
		return 0;
	}
	else if(L<=start&&end<=R){
		return tree[node];
	}
	else{
		int mid=(start+end)/2;
		int left_node=2*node+1;
		int right_node=2*node+2;
		int sum_left=query_tree(arr,tree,left_node,start,mid,L,R);
		int sum_right=query_tree(arr,tree,right_node,mid+1,end,L,R);
		return sum_left+sum_right;
	}
}

int main()
{
	int arr[]={1,3,5,7,9,11};
	int size=6;
	int tree[MAX_LEN]={0};
	build_tree(arr,tree,0,0,size-1);
	for(int i=0;i<15;++i)
	{
		printf("tree[%d]=%d\n",i,tree[i]);	
	} 
	printf("\n");
	update_tree(arr,tree,0,0,size-1,4,6);
	for(int i=0;i<15;++i)
	{
		printf("tree[%d]=%d\n",i,tree[i]);	
	} 
	int sum=query_tree(arr,tree,0,0,size-1,2,5);
	printf("(2-5)=%d\n",sum);
	return 0;	
}

作业题zoj

Count the Colors

颜色覆盖问题

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<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=8010;
struct Node
{
    int l,r;
    int color;
}segTree[MAXN*3];
int color[MAXN];
int temp;
void Build(int i,int l,int r)
{
    segTree[i].l=l;
    segTree[i].r=r;
    segTree[i].color=-1;//-1表示没有颜色
    if(l+1==r)return;
    int mid=((l+r)>>1);
    Build(i<<1,l,mid);
    Build((i<<1)|1,mid,r);
}
void insert(int i,int l,int r,int c)
{
    if(l==r)return;
    if(segTree[i].color==c)return;
    if(l<=segTree[i].l&&r>=segTree[i].r)
    {
        segTree[i].color=c;
        return;
    }
    if(segTree[i].color>=0)//存在颜色，往下更新
    {
        segTree[i<<1].color=segTree[i].color;
        segTree[(i<<1)|1].color=segTree[i].color;
        segTree[i].color=-2;//表示有多种颜色
    }
    int mid=((segTree[i].l+segTree[i].r)>>1);
    if(r<=mid) insert(i<<1,l,r,c);
    else if(l>=mid) insert((i<<1)|1,l,r,c);
    else
    {
        insert(i<<1,l,mid,c);
        insert((i<<1)|1,mid,r,c);
    }
    segTree[i].color=-2;
}
void Count(int i)//统计各颜色的段数
{
    if(segTree[i].color==-1)
    {
        temp=-1;
        return;
    }
    if(segTree[i].color!=-2)
    {
        if(segTree[i].color!=temp)//temp存的是前一段的颜色
        {
            color[segTree[i].color]++;
            temp=segTree[i].color;
        }
        return;
    }
    if(segTree[i].l+1!=segTree[i].r)
    {
        Count(i<<1);
        Count((i<<1)|1);
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,a,b,c;
    int Max;
    while(scanf("%d",&n)!=EOF)
    {
        Build(1,0,8000);
        Max=0;
        while(n--)
        {
            scanf("%d%d%d",&a,&b,&c);
            insert(1,a,b,c);
            if(c>Max)Max=c;
        }
        temp=-1;
        memset(color,0,sizeof(color));
        Count(1);
        for(int i=0;i<=Max;i++)
        {
            if(color[i])printf("%d %d\n",i,color[i]);
        }
        printf("\n");
    }
    return 0;
}

相关模板学习

csdn线段树学习

约瑟夫环问题

数学解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
int main()
{
	int n,k,s;
	scanf("%d %d %d",&n,&k,&s);
	s=s-1;
	for(int i=2;i<=n;++i)
	{
		s=(s+k)%i;
		printf("%d\n",s+1);
	}
	printf("winner:%d",s+1);
	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
#include<bits/stdc++.h>
using namespace std;

struct node{
	int num;
	int l;
	int r;
};

node *tree;

void build(int left,int right,int index){ 
	tree[index].l=left;
	tree[index].r=right;
	if(right==left){
		tree[index].num=1;
		return; 
	} 
	int mid=(left+right)/2;
	build(left,mid,index<<1);
	build(mid+1,right,index<<1|1);
	tree[index].num=tree[index<<1].num+tree[index<<1|1].num;
}

int update(int p,int index){
	if(tree[index].r==tree[index].l){
		tree[index].num=0;
		return tree[index].r;
	}
	tree[index].num--;
	
	if(p<=tree[index<<1].num)
		return update(p,index<<1);
	else
		return update(p-tree[index<<1].num,index<<1|1);
}

int main()
{
	int n,m,k;
	while(cin>>n>>m>>k){
		tree=new node[3*n];
		build(1,n,1);
		int seq=k;
		for(int i=0;i<n;++i){
			seq=(seq+m-1)%tree[1].num;
			if(seq==0)
				seq=tree[1].num;
			cout<<update(seq,1)<<" ";
		}
		printf("\n");
	}
	return 0;
}

作业题zoj2451

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
#include <bits/stdc++.h>
using namespace std;

#define MAXN 222222

int L[MAXN], R[MAXN], seg[MAXN];
int n, M;

void build(int i, int l, int r)
{
	L[i] = l;
	R[i] = r;
	seg[i] = M + 1;
	if (l == r)
		return;
	int mid = ((l + r) >> 1);
	build(i << 1, l, mid);
	build((i << 1) | 1, mid + 1, r);
}

void update(int i, int p, int val)
{
	seg[i] = min(seg[i], val);
	if (L[i] == R[i])
		return;
	int mid = (L[i] + R[i]) >> 1;
	if (p <= mid)
		update(i << 1, p, val);
	else
		update((i << 1) | 1, p, val);
}

int query(int i, int l, int r)
{
	if (L[i] == l && R[i] == r)
		return seg[i];
	int mid = (L[i] + R[i]) >> 1;
	if (r <= mid)
		return query(i << 1, l, r);
	else if (l > mid)
		return query((i << 1) | 1, l, r);
	else
		return min(query(i << 1, l, mid), query((i << 1) | 1, mid + 1, r));
}

int main()
{
	while (2 == scanf("%d%d", &n, &M))
	{
		build(1, 1, n);
		update(1, 1, 0);
		int a, b;
		while (M--)
		{
			scanf("%d%d", &a, &b);
			int value = query(1, a, b - 1);
			update(1, b, value + 1);
		}
		printf("%d\n", query(1, n, n));
	}
	return 0;
}
算法 scnu-ACM-class

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！