线段树 fzu 2171 防守阵地 II

缘起

【1】中已经给出线段树的板子了，自然要测一下. 于是找来 fzu 2171来测一下板子的性能.

分析

题意比较裸.

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
部队中总共有N个士兵，每个士兵有各自的能力指数Xi，在一次演练中，指挥部确定了M个需要防守的地点，指挥部将选择M个士兵依次进入指定地点进行防守任务，获得的参考指数即为M个士兵的能力之和。随着时间的推移，指挥部将下达Q个指令来替换M个进行防守的士兵们，每个参加完防守任务的士兵由于疲惫等原因能力指数将下降1。现在士兵们排成一排，请你计算出每次进行防守的士兵的参考指数。

输入
输入包含多组数据。
输入第一行有两个整数N,M,Q(1<=N<=100000，1<=M<=1000,1<=Q<=100000),第二行N个整数表示每个士兵对应的能力指数Xi（1<=Xi<=1000）。
接下来Q行，每行一个整数X，表示在原始队列中以X为起始的M个士兵替换之前的士兵进行防守。（1<=X<=N-M+1）
对于30%的数据1<=M,N,Q<=1000。

输出
输出Q行，每行一个整数，为每次指令执行之后进行防守的士兵参考指数。

样例输入
5 3 3
2 1 3 1 4
1
2
3

样例输出
6
3
5

限制
Time limit 3000 ms
Memory limit 32768 kB

本题使用线段树维护区间和（所以说线段树太灵活了, 只有固定的算法思想，没有固定的算法模板）.

首先，自然的思路就是求一次和，然后更新一波. 也即下面这个样子

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 "stdafx.h"
#include<iostream>
#include <stdio.h>
#define LOCAL

using namespace std;

const int MAX_LEN = 100005;

int n,m,q, x[MAX_LEN],X;

struct
{
	int begin, end; 
	int sum;  // sum表示此节点代表的区间的片段和

} segmenttree[MAX_LEN<<2];

inline int getmid(int i) {return (segmenttree[i].begin+segmenttree[i].end)>>1;}

void build(int begin, int end, int root)
{
	if (begin > end) return;
	segmenttree[root].begin = begin;
	segmenttree[root].end = end;
	segmenttree[root].sum = 0;
	if (begin==end) return;
	int mid = (begin+end)>>1;
	build(begin, mid, root<<1);
	build(mid+1, end, (root<<1)+1);
}

void insert(int index, int i) // 插入x[index], segmenttree[i]是线段树的当前节点,这种更新一定是要到底部的
{
	segmenttree[i].sum+=x[index]; // 当前节点的部分和肯定增加了
	if (segmenttree[i].begin == segmenttree[i].end) // 如果到了叶子节点, 则返回
	{
		return;
	}
	int mid = getmid(i); // 取得区间的中点
	if (mid>=index)  // 加入左子树
	{
		insert(index, i<<1); 
	}
	else // index>mid, 则加入右子树
	{
		insert(index, (i<<1)+1);
	}
}

int getsum(int begin, int end, int i) // 求x[begin,...,end]的片段和, 其实就是把该线段[begin,end]从线段树的根节点插下去, segment[i]是线段树的当前节点
{
	if (begin==segmenttree[i].begin && end==segmenttree[i].end) // 如果区间完全重合的话, 则返回, 不需要继续了，不然会重复加的.
	{
		return segmenttree[i].sum;
	}
	else
	{
		int mid = getmid(i); // 取得区间的中点
		if (end<=mid) // 完全在左子树
		{
			return getsum(begin, end, i<<1);
		}
		else if (begin>mid) // 完全在右子树
		{
			return getsum(begin, end, (i<<1)+1);
		}
		else // 被segmenttree[i]的俩孩子剖分
		{
			return getsum(begin, mid, i<<1)+getsum(mid+1, end, (i<<1)+1);
		}
	}
}

void update(int begin, int end, int i) // segmenttree[i]是当前节点, 
{
	segmenttree[i].sum-=(end-begin+1);
	if (segmenttree[i].begin==segmenttree[i].end) // 叶子节点,注意, 这里的维护是到底的
	{
		return;
	}
	int mid = getmid(i);
	if (end<=mid)
	{
		update(begin,end,i<<1);
	}
	else if (begin>mid)
	{
		update(begin,end,(i<<1)+1);
	}
	else
	{
		update(begin, mid, i<<1);
		update(mid+1, end, (i<<1)+1);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d", &n, &m,&q))
	{		
		build(1,n,1); // 使用[1,...,n]建线段树
		for (int i = 1; i<=n; i++)scanf("%d",x+i),insert(i, 1); // 插入x[i],顺便维护线段树各个节点的sum值
		while(q--) // q次询问
		{
			scanf("%d", &X);
			printf("%d\n", getsum(X,X+m-1,1)); // 使用线段树快速求部分和
			update(X,X+m-1,1); // 使用线段树进行快速维护，注意，不能直接在getsum的基础上进行维护, 因为getsum不会走到底（找到完全匹配的节点就返回了）. 导致完全重合的节点的子节点的sum域不会更新
		}
	}
	return 0;
}

但是提交的结果是吃了T. 其实和网上已经ac掉的程序做过对拍，对拍程序如下

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
#include "stdafx.h"
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
const int INF = 0x3f3f3f3f;


int main()
{
	freopen("d:\\data.in", "w", stdout);
	srand((int)(time(0)));
	for (int i = 1;i<=100;i++)
	{
		int n,m,q;
		n = rand()%100000+1;
		m = rand()%n+1;
		q = rand()%100000+1;
		printf("%d %d %d\n", n,m,q);
		int x[100005];
		for (int i = 1; i<=n;i++)
		{
			printf("%d ", rand()%1000+1);
		}
		puts("");
		for (int i = 1; i<=q;i++)
		{

			printf("%d", rand()%(n-m+1)+1);
			if (i<q)
			{
				puts("");
			}
		}
	}
	
	fclose(stdout); 
	return 0;
}

发现没有WA的可能. 所以基本判定，第一版给的线段树算法是超时导致的（而不是因为算法错误而死循环导致吃T）. 那有没有更好的算法呢? 或者反过来思考——上面的算法哪里做了多余的事情导致超时的呢? 我们的目光定位到了——“每次获取片段和之后就自顶到底更新节点上”，真的有必要吗? 且看下图

其实如果求[1,2]的片段和的话，走到线段树的[1,2]节点就返回，我们完全没必要真的更新[1,2]的子节点们, 我们只需要给[1,2]的左右孩子都打上延迟更新的标记即可——假设算法走到了[a,b]区间就返回了，则[a,b]区间减少 (b-a+1), 那么我们并不继续使用update操作从顶至底部更新整棵线段树，而只是简单的给[a,b]区间的左右孩子打上延迟更新的标记（所以线段树的节点需要多一个lazy的属性，表示延迟更新的次数）. 那么就信息而言，是没有遗漏的~ 因为这两个孩子的sum域就是要满打满算的要减去他们对应线段的长度的值. 这才是ac之道!!! 且看下面的程序

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
//#include "stdafx.h"
#include<iostream>
#include <stdio.h>
//#define LOCAL

using namespace std;

const int MAX_LEN = 100005;

int n,m,q, x[MAX_LEN],X;

struct
{
	int begin, end;
	int sum;
	int lazy; // lazy表示此节点延迟更新的次数

} segmenttree[MAX_LEN<<2];

inline int getmid(int i) {return (segmenttree[i].begin+segmenttree[i].end)>>1;}

void build(int begin, int end, int root)
{
	segmenttree[root].begin = begin;
	segmenttree[root].end = end;
	segmenttree[root].sum = 0;
	segmenttree[root].lazy = 0;
	if (begin==end) return;
	int mid = (begin+end)>>1;
	build(begin, mid, root<<1);
	build(mid+1, end, (root<<1)+1);
}

void insert(int index, int i)
{
	segmenttree[i].sum+=x[index]; 
	if (segmenttree[i].begin == segmenttree[i].end) return;
	int mid = getmid(i);
	mid>=index?insert(index, i<<1):insert(index, (i<<1)+1);
}

void pushdown(int begin, int end, int i) // 将当前节点segmenttree[i]的延迟标记下推到它的两个子节点
{
	segmenttree[i<<1].lazy+= segmenttree[i].lazy;
	segmenttree[(i<<1)+1].lazy += segmenttree[i].lazy; // 延迟标记下推到2个子节点
	segmenttree[i].sum-=(segmenttree[i].end-segmenttree[i].begin+1)*segmenttree[i].lazy+(end-begin+1); // 当前节点不再是延迟更新了, 所以要更新当前节点的sum域了, (segmenttree[i].end-segmenttree[i].begin+1)*segmenttree[i].lazy是旧账, (end-begin+1)是新账
	segmenttree[i].lazy = 0; // 当前节点已经不再是延迟更新了
}

int getsum(int begin, int end, int i)
{
	if (begin==segmenttree[i].begin && end==segmenttree[i].end) return segmenttree[i].sum-(end-begin+1)*segmenttree[i].lazy++; // 延迟更新次数+1(但是不需要下推)
	pushdown(begin, end, i); // 下推延迟标记
	int mid = getmid(i);
	if (end<=mid) return getsum(begin, end, i<<1); // 要跳到左子树去
	else if (begin>mid) return getsum(begin, end, (i<<1)+1); // 要跳到右子树去
	else return getsum(begin, mid, i<<1)+getsum(mid+1, end, (i<<1)+1); // 要被左右孩子剖分
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d%d", &n, &m,&q))
	{		
		build(1,n,1);
		for (int i = 1; i<=n; i++)scanf("%d",x+i),insert(i, 1);
		while(q--)
		{
			scanf("%d", &X);
			printf("%d\n", getsum(X,X+m-1,1));
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 343ms
Memory 6880kB
Length 1962
Lang GNU C++
Submitted 2019-07-14 11:44:04
Shared
RemoteRunId 898004

我没有参考网上的线段树延迟更新的资料，只是凭借自己的理解写出了上述算法. 很棒~

参考

【1】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91/