Description:

给你一个 $R\times C$ 的矩阵，多次询问在矩阵 $[x1,y1,x2,y2]$ 中最少选几个数之和大于 $H$ 。

对于 $50\%$ 的数据， $1\le R,C\le 200$ $1\le Q\le 200000$

对于另 $50\%$ 的数据， $R=1,C=500000$ $1\le Q\le 20000$

Solution:

数据点分治。。。

对于前 $50\%$ ，看数据应该有一个 $log$ ，有一个二分思路就是二分选几个看是否大于 $H$ ，发现选 $K$ 个的和不好处理，想一想发现首先应该从大到小选数，于是可以二分最小的数，预处理出 $val[i][j][k]$ 表示 $[1,1,i,j]$ 中大于等于 $k$ 的数的和， $num[i][j][k]$ 表示 $[1,1,i,j]$ 中大于等于 $k$ 的数的个数于是就可以二分了，还要注意同一个数可能只选多个中的几个。

对于后 $50\%$ ，看数据还应给有一个 $log$ ， $R=1$ ，所以是一个区间问题，选最大的 $K$ 个可以用主席树处理，还要注意同一个数可能只选多个中的几个。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,q;

int val[201][201][1001];

int num[201][201][1001];

int read()

{

    char c = getchar();

    int res = 0;

    while(c < '0' || c > '9')c = getchar();

    while('0' <= c && c <= '9')

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int getval(int x1,int y1,int x2,int y2,int h)

{

    return val[x2][y2][h] - val[x1 - 1][y2][h] - val[x2][y1 - 1][h] + val[x1 - 1][y1 - 1][h];

}

int getnum(int x1,int y1,int x2,int y2,int h)

{

    return num[x2][y2][h] - num[x1 - 1][y2][h] - num[x2][y1 - 1][h] + num[x1 - 1][y1 - 1][h];

}

void work1()

{

    int p;

    for(int i = 1;i <= n;++i)

    {

        for(int j = 1;j <= m;++j)

        {

        	p = read();

            for(int k = 1;k <= 1000;++k)

            {

                val[i][j][k] = val[i - 1][j][k] + val[i][j - 1][k] - val[i - 1][j - 1][k] + (p >= k ? p : 0);

                num[i][j][k] = num[i - 1][j][k] + num[i][j - 1][k] - num[i - 1][j - 1][k] + (p >= k ? 1 : 0);

            }

        }

    }

    int x1,x2,y1,y2,h;

    for(int i = 1;i <= q;++i)

    {

        x1 = read();y1 = read();x2 = read();y2 = read();h = read();

        if(getval(x1,y1,x2,y2,1) < h)

        {

            puts("Poor QLW");

            continue;

        }

        int l = 0,r = 1001,ans;

        while(l < r - 1)

        {

            int mid = ((l + r) >> 1);//cout << mid << " " << getval(x1,y1,x2,y2,mid) << endl;

            if(getval(x1,y1,x2,y2,mid) >= h)

            {

                l = mid;ans = mid;

            }

            else

            {

                r = mid;

            }

        }

        printf("%d\n",getnum(x1,y1,x2,y2,ans) - (getval(x1,y1,x2,y2,ans) - h) / ans);

    }

    return;

}

struct node

{

    int c[2],sum,siz;

    node(){c[0] = c[1] = sum = siz = 0;}

}t[500000 * 10];

int ptr = 0;

int newnode(){return ++ptr;}

void build(int rt,int l,int r)

{

    if(l == r)return;

    int mid = ((l + r) >> 1);

    build(t[rt].c[0] = newnode(),l,mid);

    build(t[rt].c[1] = newnode(),mid + 1,r);

    return;

}

void insert(int &rt,int rt_,int p,int l,int r)

{

    rt = newnode();

    t[rt] = t[rt_];

    t[rt].siz += 1;

    t[rt].sum += p;

    if(l == r)return;

    int mid = ((l + r) >> 1);

    if(p <= mid)insert(t[rt].c[0],t[rt_].c[0],p,l,mid);

    else insert(t[rt].c[1],t[rt_].c[1],p,mid + 1,r);

    return;

}

int root[500010];

void work2()

{

    build(root[0] = newnode(),1,1000);

    for(int i = 1;i <= m;++i)

    {

        insert(root[i],root[i - 1],read(),1,1000);

    }

    int x1,y1,x2,y2,h;

    for(int i = 1;i <= q;++i)

    {

        x1 = read();y1 = read();x2 = read();y2 = read();h = read();

        int l = 1,r = 1000;

        int res = 0,tmp;

        int cur1 = root[y1 - 1],cur2 = root[y2];

        if(h > t[cur2].sum - t[cur1].sum)

        {

            puts("Poor QLW");

            continue;

        }

        while(l < r)

        {

            tmp = t[t[cur2].c[1]].sum - t[t[cur1].c[1]].sum;

            if(h <= tmp)

            {

                l = ((l + r) >> 1) + 1;

                cur1 = t[cur1].c[1];cur2 = t[cur2].c[1];

            }

            else

            {

                r = ((l + r) >> 1);

                res += t[t[cur2].c[1]].siz - t[t[cur1].c[1]].siz;

                cur1 = t[cur1].c[0];cur2 = t[cur2].c[0];

                h -= tmp;

            }

        }

        cout << res + (int)ceil((double)h / (double)l) << endl;

    }

    return;

}

int main()

{

    n = read();m = read();q = read();

    if(n != 1)work1();

    else work2();

    return 0;

}