# 洛谷P2468 [SDOI2010]粟粟的书架(二分答案 前缀和 主席树)

## Sol

mdzz死活有一个点RE。。

```#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define LL long long
// #define int long long
using namespace std;
const int MAXN = 1001, INF = 1e9 + 7, mod = 998244353, MAX = 5500002;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M, Q;
int a[202][202], f[202][202][1002], g[202][202][1002];
//f[i][j][k] 从(1, 1)到(i, j) >= k的个数
//g[i][j][k] 从(1, 1)到(i, j) >= k的和
int Get(int k, int l1, int r1, int l2, int r2, int H) {
return g[l2][r2][k] - g[l1 - 1][r2][k] - g[l2][r1 - 1][k] + g[l1 - 1][r1 - 1][k];
}
int Query(int k, int l1, int r1, int l2, int r2) {
return f[l2][r2][k] - f[l1 - 1][r2][k] - f[l2][r1 - 1][k] + f[l1 - 1][r1 - 1][k];
}
void work() {
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
for(int k = 0; k <= 1000; k++) {
f[i][j][k] = f[i - 1][j][k] + f[i][j - 1][k] - f[i - 1][j - 1][k] + (a[i][j] >= k);
g[i][j][k] = g[i - 1][j][k] + g[i][j - 1][k] - g[i - 1][j - 1][k] + (a[i][j] >= k) * a[i][j];
}
}
}
while(Q--) {
int l = 0, r =  1000, ans = -1;
while(l <= r) {
int mid = l + r >> 1;
int X = Get(mid, l1, r1, l2, r2, H);
if(X >= H) ans = Query(mid, l1, r1, l2, r2) - (X - H) / mid, l = mid + 1;
else r = mid - 1;
}
if(ans == -1) {puts("Poor QLW"); continue;}
printf("%d\n", ans);
}
}
}
int a[MAX];
int ls[MAX], rs[MAX], sum[MAX], siz[MAX], rt[MAX], tot = 0;
void Insert(int &k, int p, int l, int r, int pos) {
k = ++tot;
rs[k] = rs[p]; ls[k] = ls[p]; siz[k] = siz[p]; sum[k] = sum[p];
siz[k]++; sum[k] += pos;
if(l == r) return ;
int mid = (l + r) >> 1;
if(pos <= mid) Insert(ls[k], ls[p], l, mid, pos);
else Insert(rs[k], rs[p], mid + 1, r, pos);
}
int Query(int x, int y, int l, int r, int val) {
if(l == r) return (val + l - 1) / l;
int mid = l + r >> 1;
int rsum = sum[rs[y]]- sum[rs[x]];
if(rsum >= val) return Query(rs[x], rs[y], mid + 1, r, val);
else return Query(ls[x], ls[y], l, mid, val - rsum) + siz[rs[y]] - siz[rs[x]];
}
void work() {
for(int i = 1; i <= M; i++) a[i] = read(), Insert(rt[i], rt[i - 1], 1, 1000, a[i]);
while(Q--) {
if(l1 != 1 || l2 != 1) {puts("Poor QLW"); continue;}
if(sum[rt[y]] - sum[rt[x - 1]] < H) {puts("Poor QLW"); continue;}
int ans = Query(rt[x - 1], rt[y], 1, 1000, H);
printf("%d\n", ans);
}
}
}
main() {
// freopen("a.in", "r", stdin);
//  freopen("c.out", "w", stdout);
return 0;
}
/*
*/```

1811 篇文章120 人订阅

0 条评论

## 相关文章

1223

2065

### 数据库中间件 Sharding-JDBC 源码分析 —— SQL 解析（一）之语法解析

1. 概述 2. Lexer 词法解析器 3. Token 词法标记 3.2.1 Literals.IDENTIFIER 词法关键词 3.2.2 Litera...

4558

3485

3494

1196

2131

3055

3659

3629