正题

评测记录:

题目大意

对于每一个询问，求一个区域内最少取多少个数使它们的和不小于a。

解题思路

我们肯定取最大的

对于前50%的数据，用

sum_{i,j,k}

表示

(1, 1)

到

(i, j)

超过

k

的数字和

num_{i,j,k}

表示

(1, 1)

到

(i, j)

超过

k

的数字个数

然后二分一下。

对于后50%的数据，其实就是询问 $l r$ 这个区间最少多少个数使它们的和不小于a。

我们可以用一个主席树，对于每个节点我们维护两个值sum,w。w是这个节点代表区域的数字个数，sum是这些数的和。然后用第

r

棵减去第

l - 1

棵就是一个区域内的值。之后更具sum跑，统计w就好了。

code

#include
   
    #include
    
     #define N50 210#define N 500010using namespace std;int r,c,m;int sum[N50][N50][1100],num[N50][N50][1100],a[N50][N50];int get_sum(int x1,int y1,int x2,int y2,int k){
   	return sum[x2][y2][k]-sum[x1-1][y2][k]		  -sum[x2][y1-1][k]+sum[x1-1][y1-1][k];}int get_num(int x1,int y1,int x2,int y2,int k){
   	return num[x2][y2][k]-num[x1-1][y2][k]		  -num[x2][y1-1][k]+num[x1-1][y1-1][k];}void work1()//前50%{
   	int maxs=-1e9-7;	for(int i=1;i<=r;i++)	  for(int j=1;j<=c;j++)	  {
   	  	  scanf("%d",&a[i][j]);	  	  maxs=max(maxs,a[i][j]);	  }	for(int k=1;k<=maxs;k++)	  for(int i=1;i<=r;i++)	    for(int j=1;j<=c;j++)	      if(a[i][j]>=k)	      {
   	    	  sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+a[i][j];	    	  num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]+1;		  }		  else		  {
   		  	  sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[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];		  }	int x1,x2,y1,y2,h;	for(int i=1;i<=m;i++)	{
   		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);        if(get_sum(x1,y1,x2,y2,1)
     
      >1;            if(get_sum(x1,y1,x2,y2,mid)>=h)l=mid;            else r=mid-1;        }        printf("%d\n",get_num(x1,y1,x2,y2,l)-(get_sum(x1,y1,x2,y2,l)-h)/l);	}}struct tree_node{
   	int l,r,ls,rs,w,sum;}t[10000010];int cnt,root[N];int build(int l,int r)//建空树{
       int k=++cnt;    t[k].l=l,t[k].r=r;    if (l==r) return k;    int mid=(l+r)>>1;    t[k].ls=build(l,mid);    t[k].rs=build(mid+1,r);    return k;}int addt(int k,int z)//加新树{
       int nb=++cnt;    t[nb]=t[k];t[nb].w++;    t[nb].sum+=z;    if (t[k].l==z&&t[k].r==z) return nb;    int mid=(t[k].l+t[k].r)>>1;    if (z<=mid) t[nb].ls=addt(t[k].ls,z);    else t[nb].rs=addt(t[k].rs,z);    return nb;}int query(int k1,int k2,int k)//询问{
       if (t[k1].l==t[k1].r) return (k+t[k1].l-1)/t[k1].l;    int w=t[t[k2].rs].sum-t[t[k1].rs].sum;    if (k<=w) return query(t[k1].rs,t[k2].rs,k);    else return query(t[k1].ls,t[k2].ls,k-w)+t[t[k2].rs].w-t[t[k1].rs].w; }void work2()//后50%的数据{
   	int x;	root[0]=1;	build(1,1000);	for(int i=1;i<=c;i++)	{
   	  	scanf("%d",&x);	  	root[i]=cnt+1;	  	addt(root[i-1],x);	}	int x1,x2,y1,y2,h;	for(int i=1;i<=m;i++)	{
   		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);		y1--;		if(t[root[y2]].sum-t[root[y1]].sum