【主席树】洛谷 P2468 粟粟的书架
2021-04-12 15:57:00 # ACM

题链

分析

前50%的数据

$val[i][j][k]$ 表示 $[1,1]$$[i,j]$ 大于等于 $k$ 的值 的总和；
$size[i][j][k]$ 表示 $[1,1]$$[i,j]$ 大于等于 $k$ 的值 的个数；
在 $[1,1000]$ 之内二分查找；

后50%的数据

建立主席树（可持久化权值线段树），节点信息除了左右子节点还有 区间个数$size$ 与 区间和$val$;
当插入一个值 $pos$ 时，递归到末节点，$size++$，$val+=pos$；

注意

若所给数字都是没有重复的，那查找就很好做；
但是题目说明有重复，假设题给目标值 $tar$，应当查找在所给区间从大到小选择数字，一选就是一打（一打意思就是选择一个数字 $num$，无论 $num$ 有几个都选上），选择直到刚刚好小于目标值，再选一个就超过目标值了；
记录现在已经选的数字总和 $sum$，数字个数 $size$，最小数字 $minn$ 和 再选择一个数字 $num$ 就超过题给目标值；
由于 $num$ 可能不止一个，所以得一次次选择 $num$ 直到达到目标值；

代码

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
#define MS 500009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long 
#define MAXN 20000009

int n,m,k;
int tot;
int rtpos[MS];
struct node{
	int l,r;
	int val;
	int size;
}p[MS*30];

void push_up(int rt){
	p[rt].size = p[p[rt].l].size + p[p[rt].r].size;
	p[rt].val = p[p[rt].l].val + p[p[rt].r].val;
}

int build(int l,int r){
	int rt = ++tot;
	if(l == r){
		return rt;
	}
	int m = l+r>>1;
	p[rt].l = build(l,m);
	p[rt].r = build(m+1,r);
	return rt;
}

int update(int lart,int l,int r,int pos){
	int rt = ++tot;
	p[rt] = p[lart];
	if(l == r && l == pos){
		p[rt].size++;
		p[rt].val += pos;
		return rt;
	}
	int m = l+r>>1;
	if(m >= pos) p[rt].l = update(p[lart].l,l,m,pos);
	else p[rt].r = update(p[lart].r,m+1,r,pos);
	push_up(rt);
	return rt;
}

int getCnt(int L,int R,int l,int r,int tar){
	if(l == r){
		if(tar > 0) return (tar-1)/l+1;
		else return 0; 
	}
	int x = p[p[R].r].val - p[p[L].r].val;
	int y = p[p[R].r].size - p[p[L].r].size;
	int m = l+r>>1;
	if(x >= tar) return getCnt(p[L].r,p[R].r,m+1,r,tar);
	else return y + getCnt(p[L].l,p[R].l,l,m,tar-x);
}

void solve1(){
	rtpos[0] = build(1,1000);
	for(int i=1;i<=m;i++){
		int x;
		cin >> x;
		rtpos[i] = update(rtpos[i-1],1,1000,x);
	} 
	while(k--){
		int L,R;
		int tar;
		cin >> L >> L >> R >> R >> tar;
		L = rtpos[L-1];
		R = rtpos[R];
		if(p[R].val - p[L].val < tar) cout << "Poor QLW\n";
		else cout << getCnt(L,R,1,1000,tar) << "\n";
	}
}

int a[209][209];
int val[209][209][1009];
int size[209][209][1009];

void solve2(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	for(int o=1;o<=1000;o++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				val[i][j][o] = val[i-1][j][o]+val[i][j-1][o]-val[i-1][j-1][o];
				val[i][j][o] += (a[i][j] >= o? a[i][j] : 0);
				size[i][j][o] = size[i-1][j][o]+size[i][j-1][o]-size[i-1][j-1][o];
				size[i][j][o] += (a[i][j] >= o? 1 : 0);
			}
		}
	}
	while(k--){
		int l1,r1,l2,r2;
		int tar;
		cin >> l1 >> r1 >> l2 >> r2 >> tar;
		int sumlr = val[l2][r2][1]-val[l1-1][r2][1]-val[l2][r1-1][1]+val[l1-1][r1-1][1];
		if(sumlr < tar){
			cout << "Poor QLW\n";
			continue;
		}
		int l=1,r=1001;
		int ansval,anssize;
		int sumval;
		while(l <= r){
			int mid = l+r>>1;
			int x = val[l2][r2][mid]-val[l1-1][r2][mid]-val[l2][r1-1][mid]+val[l1-1][r1-1][mid];
			int y = size[l2][r2][mid]-size[l1-1][r2][mid]-size[l2][r1-1][mid]+size[l1-1][r1-1][mid];
			if(x >= tar) l = mid+1;
			else{
				sumval = x;
				ansval = mid;
				anssize = y;
				r = mid-1;
			}
		}
		anssize += (tar-sumval-1)/(ansval-1)+1;
		cout << anssize << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> k;
	if(n == 1) solve1();
	else solve2();
	
	return 0;
}

Prev
2021-04-12 15:57:00 # ACM
Next