「SDOI2010」粟粟的书架 - 主席树 + 二分答案

题目链接：传送门

Description

幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j页厚。粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头都难以摘到。不过她发现，如果在脚下放上几本书，就可以够着苹果；她同时注意到，对于第i天指定的那个苹果，只要她脚下放置书的总页数之和不低于Hi，就一定能够摘到。由于书架内的书过多，父母担心粟粟一天内就把所有书看完而耽误了上幼儿园，于是每天只允许粟粟在一个特定区域内拿书。这个区域是一个矩形，第i天给定区域的左上角是上数第x1i行的左数第y1i本书，右下角是上数第x2i行的左数第y2i本书。换句话说，粟粟在这一天，只能在这﹙x2i－x1i＋1﹚×﹙y2i－y1i＋1﹚本书中挑选若干本垫在脚下，摘取苹果。粟粟每次取书时都能及时放回原位，并且她的书架不会再撤下书目或换上新书，摘苹果的任务会一直持续M天。给出每本书籍的页数和每天的区域限制及采摘要求，请你告诉粟粟，她每天至少拿取多少本书，就可以摘到当天指定的苹果。

Hint

对于50%的数据，满足R, C≤200，M≤200000；另有50%的数据，满足R＝1，C≤500000，M≤20000 对于100%的数据，满足1≤Pi,j≤1000，1≤Hi≤2000000000

Sample Input

5 5 7 14 15 9 26 53 58 9 7 9 32 38 46 26 43 38 32 7 9 50 28 8 41 9 7 17 1 2 5 3 139 3 1 5 5 399 3 3 4 5 91 4 1 4 1 33 1 3 5 4 185 3 3 4 3 23 3 1 3 3 108

Sample Output

6 15 2 Poor QLW 9 1 3

Solution

这是一道二合一的题前50%中R,C<=200，我们可以设val[i][j][k]表示(1,1)到(i,j)这个矩阵中大于等于k的值的总和,num[i][j][k]表示(1,1)到(i,j)这个矩阵中大于等于k的值的个数。然后用这个前缀和+二分答案即可后50%中，R=1，也就是变成了数列上的问题。然后我们用主席树维护区间前k大数的和，然后也用二分答案去做即可

Summary

这道题打得非常快，但是调了好久。。。数组各种原因开炸，一开始数组开小了结果WA掉了，检查好久代码没发现问题把数组开大点就全RE，最后仔细算了一下要开的数组的大小，修改之后就A了。。。

Code

#include <bits/stdc++.h>
#define x1 hk
#define x2 is
#define y1 so
#define y2 clever

using namespace std;

const int Maxn = 200 + 10, Maxm = 500000 + 100;

int N, M, Q;
int val[Maxn][Maxn][1000 + 10];
int num[Maxn][Maxn][1000 + 10];

inline int calc_val (int x1, int y1, int x2, int y2, int x)
{
    return val[x2][y2][x] - val[x2][y1 - 1][x] - val[x1 - 1][y2][x] + val[x1 - 1][y1 - 1][x];
}

inline int calc_num (int x1, int y1, int x2, int y2, int x)
{
    return num[x2][y2][x] - num[x2][y1 - 1][x] - num[x1 - 1][y2][x] + num[x1 - 1][y1 - 1][x];
}

inline void Subtask1()
{
    int A[Maxn][Maxn];
    memset(A, 0, sizeof(A));
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            scanf("%d", &A[i][j]);

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            for (int k = 0; k <= 1000; ++k)
                val[i][j][k] = val[i][j - 1][k] + val[i - 1][j][k] - val[i - 1][j - 1][k] + (A[i][j] >= k ? A[i][j] : 0),
                num[i][j][k] = num[i][j - 1][k] + num[i - 1][j][k] - num[i - 1][j - 1][k] + (A[i][j] >= k);

    int x1, y1, x2, y2, x;
    while (Q--)
    {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &x);
        //cout<<calc_val(x1, y1, x2, y2, 0)<<endl;
        if (calc_val(x1, y1, x2, y2, 0) < x){puts("Poor QLW"); continue;}
        int l = 0, r = 1000, pos = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (calc_val(x1, y1, x2, y2, mid) >= x) l = mid + 1, pos = mid;
            else r = mid - 1;
        }
        printf("%d\n", calc_num(x1, y1, x2, y2, pos) - (calc_val(x1, y1, x2, y2, pos) - x) / pos);
    }
}

int Root[Maxm], Cnt;

struct tree
{
    int lson, rson, val, sum;
}Tree[Maxm * 20];

inline void push_up (int root)
{
    Tree[root].val = Tree[Tree[root].lson].val + Tree[Tree[root].rson].val;
    Tree[root].sum = Tree[Tree[root].lson].sum + Tree[Tree[root].rson].sum;
}

inline void build(int &root, int l, int r)
{
    root = ++ Cnt;
    if (l == r)
        return ;
    int mid = (l + r) >> 1;
    build (Tree[root].lson, l, mid);
    build (Tree[root].rson, mid + 1, r);
}

inline void Insert (int pre, int &now, int l, int r, int x)
{
    now = ++ Cnt;
    Tree[now].lson = Tree[pre].lson;
    Tree[now].rson = Tree[pre].rson;
    Tree[now].val = Tree[pre].val;
    Tree[now].sum = Tree[pre].sum;
    if (l == r)
    {
        Tree[now].val ++;
        Tree[now].sum += x;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Insert(Tree[pre].lson, Tree[now].lson, l, mid, x);
    else Insert(Tree[pre].rson, Tree[now].rson, mid + 1, r, x);
    push_up(now);
}

inline int Query (int pre, int now, int l, int r, int x)
{
    //cout<<pre<<" "<<Tree[pre].sum<<" "<<now<<" "<<Tree[now].sum<<endl;
    if (l == r)
        return !(Tree[now].val - Tree[pre].val) ? (Tree[now].sum - Tree[pre].sum) : (Tree[now].sum - Tree[pre].sum) / (Tree[now].val - Tree[pre].val) * x;
    int mid = (l + r) >> 1;
    int right = Tree[Tree[now].rson].val - Tree[Tree[pre].rson].val;
    if (right >=  x)
        return Query(Tree[pre].rson, Tree[now].rson, mid + 1, r, x);
    else return Tree[Tree[now].rson].sum - Tree[Tree[pre].rson].sum + Query(Tree[pre].lson, Tree[now].lson, l, mid, x - right);
}

int Sum[Maxm];
int A[Maxm];
inline void Subtask2()
{
    N = M;
    build(Root[0], 1, 1000);
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &A[i]);
        Sum[i] = Sum[i - 1] + A[i];
        Insert(Root[i - 1], Root[i], 1, 1000, A[i]);
    }
    int x, y, h;
    while (Q--)
    {
        scanf("%*d%d%*d%d%d", &x, &y, &h);
        if (Sum[y] - Sum[x - 1] < h)
        {
            puts("Poor QLW");
            continue;
        }
        int l = 0, r = N, pos = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (Query(Root[x - 1], Root[y], 1, 1000, mid) >= h) r = mid - 1, pos = mid;
            else l = mid + 1;
        }
        printf("%d\n", pos);
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d%d", &N, &M, &Q);
    if (N != 1)
        Subtask1();
    else Subtask2();
    return 0;
}