粟粟的书架（主席树+二维前缀和）

粟粟的书架

一下子做了两个题？
题意：一个问题求区间前K大的和，另一个问题求矩形内前K大的和。

思路：

1. 前一个问题直接上主席树+二分搞定
2. 后一个问题由于数据范围比较小，用 $cnt\left[i\right]\left[j\right]\left[k\right]$cnt[i][j][k]记录前缀矩形中大于等于 $k$k的数有多少个，用 $pre\left[i\right]\left[j\right]\left[k\right]$pre[i][j][k]记录前缀矩形中大于等于 $k$k的数的和。利用这两个东西套两个二分即可
3. 代码清晰易懂，就不讲了

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int n, m, t, tot;
int h[maxn], T[maxn<<5];
int sz[maxn<<5], L[maxn<<5], R[maxn<<5];
ll sum[maxn<<5];

void update(int x, int l, int r, int pre, int &now) {
    now=++tot;
    L[now]=L[pre], R[now]=R[pre], sz[now]=sz[pre]+1, sum[now]=sum[pre]+x;
    if(l==r) return;
    int m=(l+r)/2;
    if(x<=m) update(x,l,m,L[pre],L[now]);
    else update(x,m+1,r,R[pre],R[now]);
}

ll qksum(int k, int x, int y, int l, int r) {
    if(l==r) return k*l;
    int s=sz[R[y]]-sz[R[x]];
    int m=(l+r)/2;
    if(s>=k) return qksum(k,R[x],R[y],m+1,r);
    else return sum[R[y]]-sum[R[x]]+qksum(k-s,L[x],L[y],l,m);
}

ll pre[205][205][1005];
int cnt[205][205][1005];

inline int QAQ(int k, int x1, int y1, int x2, int y2) {
    return cnt[x2][y2][k]-cnt[x2][y1-1][k]-cnt[x1-1][y2][k]+cnt[x1-1][y1-1][k];
}

inline ll qsum(int k, int x1, int y1, int x2, int y2) {
    int l=1, r=1001, mid=(l+r)/2;
    while(l<r) {
        if(QAQ(mid,x1,y1,x2,y2)<k) r=mid;
        else l=mid+1;
        mid=(l+r)/2;
    }
    int cnt=QAQ(mid,x1,y1,x2,y2);
    ll sum=pre[x2][y2][mid]-pre[x2][y1-1][mid]-pre[x1-1][y2][mid]+pre[x1-1][y1-1][mid];
    return sum+=1ll*(k-cnt)*(mid-1);
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read(), t=read();
    if(n==1) { //前一个问题，主席树
        for(int i=1; i<=m; ++i) update(read(),1,1000,T[i-1],T[i]);
        for(int i=0; i<t; ++i) {
            int x1=read(), y1=read()-1, x2=read(), y2=read(), H=read();
            int l=1, r=y2-y1+1, mid=(l+r)/2;
            while(l<r) {
                if(qksum(mid,T[y1],T[y2],1,1000)<H) l=mid+1;
                else r=mid;
                mid=(l+r)/2;
            }
            if(mid==y2-y1+1) printf("Poor QLW\n");
            else printf("%d\n", mid);
        }
    }
    else { //后一个问题，后一个问题二维前缀和
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=m; ++j) {
                int k=read();
                pre[i][j][k]=k, cnt[i][j][k]=1;
            }
        }
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=m; ++j) {
                for(int k=1000; k; --k)
                    pre[i][j][k]+=pre[i][j][k+1], cnt[i][j][k]+=cnt[i][j][k+1];
                for(int k=1000; k; --k) {
                    pre[i][j][k]+=pre[i-1][j][k]+pre[i][j-1][k]-pre[i-1][j-1][k];
                    cnt[i][j][k]+=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k];
                }
            }
        }
        for(int i=0; i<t; ++i) {
            int x1=read(), y1=read(), x2=read(), y2=read(), H=read();
            int tot=(x2-x1+1)*(y2-y1+1);
            int l=1, r=tot+1, mid=(l+r)/2;
            while(l<r) {
                if(qsum(mid,x1,y1,x2,y2)<H) l=mid+1;
                else r=mid;
                mid=(l+r)/2;
            }
            if(mid==tot+1) printf("Poor QLW\n");
            else printf("%d\n", mid);
        }
    }
}