正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P2468

---

題目大意

對于每一個詢問，求一個區域內最少取多少個數使它們的和不小于a。

---

解題思路

我們肯定取最大的
對于前50%的數據，用
$su{m}_{i,j,k}$表示$(1,1)$到$(i,j)$超過$k$的數字和
$nu{m}_{i,j,k}$表示$(1,1)$到$(i,j)$超過$k$的數字個數
然后二分一下。

對于后50%的數據，其實就是詢問$lr$這個區間最少多少個數使它們的和不小于a。
我們可以用一個主席樹，對于每個節點我們維護兩個值sum,w。w是這個節點代表區域的數字個數，sum是這些數的和。然后用第$r$棵減去第$l?1$棵就是一個區域內的值。之后更具sum跑，統計w就好了。

---

code

#include<cstdio> #include<algorithm> #define N50 210 #define N 500010 using 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)<h){printf("Poor QLW\n");continue;}int l=1,r=maxs,mid;while(l<r){mid=(l+r+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<h) printf("Poor QLW\n");else printf("%d\n",query(root[y1],root[y2],h));} } int main() {scanf("%d%d%d",&r,&c,&m);if(r==1) work2();else work1(); }

總結

以上是生活随笔為你收集整理的P2468-[SDOI2010]粟粟的书架【主席树,二维前缀和】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。