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

题意

题目链接

给出一个矩形,每个点都有一些值,每次询问一个子矩阵最少需要拿几个数才能构成给出的值

Sol

这题是真坑啊。。

首先出题人强行把两个题拼到了一起,

对于前$50 \%$的数据,考虑二分答案。

用$f[i][j][k]$表示从$(1, 1)$到$(i, j) >= k$的个数,$g[i][j][k]$表示从$(1, 1)$到$(i, j) >= k$的和

这两个数组都可以递推出来

对于后$50 \%$,直接用主席树维护。。

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;
inline int read() {
    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;
namespace SubTask1 {
    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++) {
                a[i][j] = read();
                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 l1 = read(), r1 = read(), l2 = read(), r2 = read(), H = read();
            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);
        }
    }
}
namespace SubTask2 {
    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--) {
            int l1 = read(), x = read(), l2 = read(), y = read(), H = read();
            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);
    N = read(); M = read(); Q = read();
    if(N != 1) SubTask1::work();
    else SubTask2::work();
    return 0;
}
/*
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏idba

order by 原理以及优化

一 简介 偏向于业务的(MySQL)DBA或者业务的开发者来说,order by 排序是一个常见的业务功能,将结果根据指定的字段排序,满足前端展示的需求。然而...

1223
来自专栏互联网开发者交流社区

Oracle-函数大全

2065
来自专栏芋道源码1024

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

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

4558
来自专栏逸鹏说道

C# 温故而知新:Stream篇(二)

TextReader 和StreamReader 目录: 为什么要介绍 TextReader? TextReader的常用属性和方法 TextReader 示例...

3485
来自专栏技术碎碎念

sql server 使用函数辅助查询

函数是所有语言系统下都具备的内部数据处理过程,SQL SERVER也同样内置了许多函数。在SQL SERVER中,函数是由一个或多个T-SQL语句组成的子程序。...

3494
来自专栏JetpropelledSnake

Django学习笔记之Models与ORM操作

1196
来自专栏xiaoxi666的专栏

Mybatis foreach标签含义

这种方式非常方便,我们只要把查询条件写出来,剩下的操作都由mysql来处理。而在实际场景中,为了减少底层耦合,我们一般不通过mysql中的子查询方式联表查询,而...

2131
来自专栏Java帮帮-微信公众号-技术文章全总结

Oracle应用实战六——函数+集合

函数 字符函数 接收字符输入返回字符或者数值,dual是伪表 1. 把小写的字符转换成大小的字符 upper('smith') ? 2. 把大写字符变成小写字符...

3055
来自专栏数据小魔方

MySQL基础入门系列之——字符与日期数据处理

今天这一篇分享MySQL中的字符串处理工具与日期时间处理,这一部分内容虽然看似不多,但是往往是输出处理中的的痛点。 我的MySQL数据库中已经建好了一个包含两列...

3659
来自专栏程序猿DD

10分钟让你明白MySQL是如何利用索引的

一、前言 在MySQL中进行SQL优化的时候,经常会在一些情况下,对MySQL能否利用索引有一些迷惑。 譬如: MySQL 在遇到范围查询条件的时候就停止匹配了...

3629

扫码关注云+社区

领取腾讯云代金券