HDU_4614_线段树+端点查找(通过数量)

HDU 4614

  1. 从A开始插F朵花.插满为止,瓶子少了则剩下的花扔掉,
  • 即统计A后面有多少个0,如果0的个数ans<=0,说明一个也花一个也插不了,tmp表示A前面有多少0
  • 如果ans>0,找到x后的第一个0用来插花
  • 判断要插入的花的数量和ans的数量,若要插的数量>ans,那么最后一个插花的地方是第(ans+tmp)个0,否则是第(y+tmp)个0

2.

  • 插花就是把区间全部修改成1
  • 扔掉a,b之间的花,就是统计1的个数,和修改区间为0
  • 区间点非0即1
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
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 50005;
int add[maxn << 2];
int sum[maxn << 2];

void pushUp(int p) {
	sum[p] = sum[2*p] + sum[2*p+1];
}
void pushDown(int p,int left,int right) {
	if (~add[p] ) {
		add[2*p] = add[2*p+1] = add[p];
		int mid = (left + right) / 2;
		sum[2*p] = (add[p] ? mid - left + 1 : 0); //通过延迟标记判断是否插花
		sum[2*p+1] = (add[p] ? right - mid : 0);
		add[p] = -1;
	}
}
void updata(int L,int R,int val,int p,int left,int right) {
	if (L<=left && right<= R) {
		add[p] = val;
		sum[p] = (add[p] ? right - left + 1 : 0);
		return;
	}
	pushDown(p,left,right);
	int mid = (left + right)/2;
	if (L <= mid) updata(L,R,val,2*p,left,mid);
	if (mid < R) updata(L,R,val,2*p+1,mid+1,right);
	pushUp(p);
}
int query(int L,int R,int p,int left,int right) {
	if (L<=left && right<=R) return sum[p];
	pushDown(p,left,right);
	int mid = (left+right)>>1;
	int ans = 0;
	if (L <= mid) ans += query(L,R,2*p,left,mid);
	if (mid < R) ans += query(L,R,2*p+1,mid+1,right);
	return ans;
}
int search(int x,int p,int left,int right) {
	if (left == right) return left;
	pushDown(p,left,right);
	int mid = (left + right) / 2, tmp = mid - left + 1 - sum[2*p]; //左节点0的个数
	if (tmp >= x) return search(x, 2*p, left, mid);
	else return search(x-tmp,2*p+1,mid+1,right);
}
int main() {
//	freopen("a.txt","r",stdin);
	int times; scanf("%d",&times);
	while (times--) {
		int n,m;
		int k, l, r, x, y;
		scanf("%d%d",&n,&m);
		memset(add,-1,sizeof add);
		memset(sum,0,sizeof sum);
		while (m--) {
			scanf("%d",&k);
			if (k == 1) {
				scanf("%d%d", &x, &y);
				++x;
				int ans = n - x + 1 - query(x,n,1,1,n);// ans表示x以后有多少个0
				int tmp = n - sum[1] - ans;//n-所有1-x后所有0 = x前0的个数
				if (ans <= 0) printf("Can not put any one.\n");
				else {
					l = search(1 + tmp,1,1,n);
					if (y > ans) r = search(ans + tmp, 1, 1, n);//找到最后一个0
					else r = search(y + tmp,1,1,n);
					printf("%d %d\n",l-1,r-1);
					updata(l,r,1,1,1,n); //把花都插进去
				}
			}
			if (k == 2) {
				scanf("%d%d",&l,&r);
				l++; r++;
				printf("%d\n",query(l,r,1,1,n));
//				printf("l=%d r=%d\n",l,r);
				updata(l,r,0,1,1,n);
			}
		}
		printf("\n");
	}
	return 0;
}
算法

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