[SDOI2010粟粟的书架]主席树

题目大意

给定一个$N*M$的矩阵,每次查询对一个给定的小矩阵使得选最少的数大于等于给定的值

分析

观察数据范围,发现这道题是一个二合一的题…

对于$R,C\leq 200$可以直接二维前缀和维护一下:

  • 令$sum[i][j][k]$表示在$1\rightarrow i,1\rightarrow j$的范围内值大于等于$k$的数字和
  • 令$f[i][j][k]$表示$1\rightarrow i,1\rightarrow j$的范围内值大于等于$k$的数字个数

接下来二分选择大于等于$x$的数字,区间为$[1,1000]$,对于每次$check$可以直接判断当前的$sum$是否满足条件

在最后输出答案的时候需要注意如果我们选择$k$及以上的数字,$k$可以选择部分而$k+1$需要全部选择,需要计算一下

这里数据好像有误,区间应该设为$[0,1000]$…我也不知道诶(反正改了就对了)

对于$R=1$可以考虑主席树

我们建一棵权值线段树,区间为$[1,1000]$,对于每一个位置记录一下数字个数即可

可以思考求区间第$k$小的主席树做法,每次插入一个数建主席树,最后答案减一下即可

另外我们在$query$的时候每次应该优先往右边走,因为我们要尽可能的选择大的数

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
// luogu-judger-enable-o2
/***************************************************************
File name: P2468.cpp
Author: ljfcnyali
Create time: 2019年07月08日 星期一 20时14分58秒
***************************************************************/
#include<bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i )
#define mem(a) memset ( (a), 0, sizeof ( a ) )
#define str(a) strlen ( a )
#define ls(x) Tree[x].l
#define rs(x) Tree[x].r

const int maxn = 210;
const int maxm = 500010;

int n, m, q, f[maxn][maxn][1010], sum[maxn][maxn][1010];
int X1, X2, Y1, Y2, cnt, Root[maxm], a[maxm], tot;

inline int Check(int x)
{
int tot = sum[X2][Y2][x] - sum[X1 - 1][Y2][x] - sum[X2][Y1 - 1][x] + sum[X1 - 1][Y1 - 1][x];
return tot;
}

inline void Solve()
{
REP(i, 1, n) REP(j, 1, m) { int x; scanf("%d", &x); ++ f[i][j][x]; sum[i][j][x] += x; }
for ( int o = 1000; o >= 0; -- o )
{
REP(i, 1, n) REP(j, 1, m)
{
f[i][j][o] += f[i - 1][j][o] + f[i][j - 1][o] - f[i - 1][j - 1][o];
sum[i][j][o] += sum[i - 1][j][o] + sum[i][j - 1][o] - sum[i - 1][j - 1][o];
}
REP(i, 1, n) REP(j, 1, m)
{
f[i][j][o] += f[i][j][o + 1];
sum[i][j][o] += sum[i][j][o + 1];
}
}
while ( q -- )
{
scanf("%d%d%d%d%d", &X1, &Y1, &X2, &Y2, &cnt);
int l = 0, r = 1000, ans = -1;
while ( l <= r )
{
int Mid = l + r >> 1;
if ( Check(Mid) >= cnt ) { l = Mid + 1; ans = Mid; }
else r = Mid - 1;
}
if ( ans == -1 ) { printf("Poor QLW\n"); continue ; }
int x = ans + 1, tot = Check(x);
ans = f[X2][Y2][x] - f[X1 - 1][Y2][x] - f[X2][Y1 - 1][x] + f[X1 - 1][Y1 - 1][x];
-- x;
ans += (cnt - tot - 1) / x + 1;
printf("%d\n", ans);
}
}

struct node
{
int l, r, size, sum;
} Tree[maxm * 20];

inline int Build(int l, int r)
{
int root = ++ tot;
ls(root) = rs(root) = Tree[root].sum = Tree[root].size = 0;
if ( l == r ) return root;
int Mid = l + r >> 1;
ls(root) = Build(l, Mid); rs(root) = Build(Mid + 1, r);
return root;
}

inline int Update(int now, int l, int r, int val)
{
int root = ++ tot; Tree[root] = Tree[now];
++ Tree[root].size; Tree[root].sum += val;
if ( l == r ) return root;
int Mid = l + r >> 1;
if ( val <= Mid ) ls(root) = Update(ls(root), l, Mid, val);
else rs(root) = Update(rs(root), Mid + 1, r, val);
return root;
}

inline int Query(int p, int q, int l, int r, int k)
{
if ( l == r ) return (k - 1) / l + 1;
int Mid = l + r >> 1;
int sum = Tree[rs(p)].sum - Tree[rs(q)].sum;
if ( sum < k ) return Tree[rs(p)].size - Tree[rs(q)].size + Query(ls(p), ls(q), l, Mid, k - sum);
else return Query(rs(p), rs(q), Mid + 1, r, k);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
scanf("%d%d%d", &n, &m, &q);
if ( n != 1 ) { Solve(); return 0; }
REP(i, 1, m) scanf("%d", &a[i]);
Root[0] = Build(1, 1000);
REP(i, 1, m) Root[i] = Update(Root[i - 1], 1, 1000, a[i]);
while ( q -- )
{
scanf("%d%d%d%d%d", &X1, &Y1, &X2, &Y2, &cnt);
int x = Root[Y1 - 1], y = Root[Y2];
// printf("%d %d\n", Tree[y].sum, Tree[x].sum);
if ( Tree[y].sum - Tree[x].sum < cnt ) { printf("Poor QLW\n"); continue ; }
printf("%d\n", Query(y, x, 1, 1000, cnt));
}
return 0;
}