题意： 给定n m 的矩阵 每个点有其权值 有q个询问
问 x1 y1 x2 y2 矩阵内 最少选多少个权值 使得权值和大于h
对于10%的数据，满足R, C≤10；
对于20%的数据，满足R, C≤40；
对于50%的数据，满足R, C≤200，M≤200,000；
另有50%的数据，满足R＝1，C≤500,000，M≤20,000；
对于100%的数据，满足1≤Pi,j≤1,000，1≤Hi≤2,000,000,000。
对于百分之五十的数据采用前缀和的做法
另外的百分之五十 用主席树维护
和之前多校的一题权值线段树很像 那题是维护最多的不超过x的个数 这个是维护最少的超过的
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RS(s) scanf("%s",s); #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define ull unsigned long long const int N=200+5; int num[N][N][1005],mp[N][N][1005]; int n,m,q,a[N][N]; int getsum(int x1,int yy,int x2,int y2,int k) { return mp[x2][y2][k]-mp[x1-1][y2][k]-mp[x2][yy-1][k]+mp[x1-1][yy-1][k]; } int getnum(int x1,int yy,int x2,int y2,int k) { return num[x2][y2][k]-num[x1-1][y2][k]-num[x2][yy-1][k]+num[x1-1][yy-1][k]; } void sol1() { int maxx=0; rep(i,1,n)rep(j,1,m)scanf("%d",&a[i][j]),maxx=max(maxx,a[i][j]); rep(i,1,n) rep(j,1,m) rep(k,0,maxx) { mp[i][j][k]=mp[i-1][j][k]+mp[i][j-1][k]-mp[i-1][j-1][k]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]; if(a[i][j]>=k)num[i][j][k]++,mp[i][j][k]+=a[i][j]; } int x1,yy,x2,y2,h; while(q--) { scanf("%d%d%d%d%d",&x1,&yy,&x2,&y2,&h); if(getsum(x1,yy,x2,y2,0)<h){printf("Poor QLW ");continue;} int L=0,R=maxx,ans; while(L<=R) { int mid=(L+R)>>1; if( getsum(x1,yy,x2,y2,mid)>=h )L=mid+1,ans=mid; else R=mid-1; } printf("%d ",getnum(x1,yy,x2,y2,ans)-(getsum(x1,yy,x2,y2,ans)-h)/ans); } } ////////////////////////////////////// const int M=500000+5; int T[M<<5],son[M<<5][2],t[M<<5],sum[M<<5],ncnt; void up(int x,int l,int r,int pre, int &pos) { pos=++ncnt; t[pos]=t[pre]+x; sum[pos]=sum[pre]+1; son[pos][0]=son[pre][0];son[pos][1]=son[pre][1]; if(l==r)return ; int m=(l+r)>>1; if(x<=m)up(x,l,m,son[pre][0],son[pos][0]); else up(x,m+1,r,son[pre][1],son[pos][1]); } int qsum(int k,int l,int r,int pre,int pos) { if(t[pos]-t[pre]<=k)return sum[pos]-sum[pre];//可加可不加 if(l==r)return (k+l-1)/l; int m=(l+r)>>1; int x=t[son[pos][1]]-t[son[pre][1]]; if( x>=k )return qsum(k,m+1,r,son[pre][1],son[pos][1]); else return sum[son[pos][1]]-sum[son[pre][1]]+qsum(k-x,l,m,son[pre][0],son[pos][0]); } void sol2() { n=m; rep(i,1,n){int x;scanf("%d",&x);up(x,1,1000,T[i-1],T[i]); } int x1,yy,x2,y2,h; while(q--) { scanf("%d%d%d%d%d",&x1,&yy,&x2,&y2,&h); if( t[T[y2]]-t[T[yy-1]]<h)printf("Poor QLW "); else printf("%d ",qsum(h,1,1000,T[yy-1],T[y2])); } } int main() { scanf("%d%d%d",&n,&m,&q); if(n==1)sol2(); else sol1(); }