题解 SDOI2010 【栗栗的书架】

[Preface ]

看到这题洛谷标签有 主席树 ，还以为是什么二维主席树的玄学做法（雾

[Description ]

给出一个 (R×C) 的矩阵。

一共 (m) 次询问，每次询问给出一个五元组 ((x1,y1,x2,y2,h)) 。

求：在矩阵 ((x1,y1,x2,y2)) 里至少取多少个数，它们的和大于等于 (h)

无解输出 Poor QLW 。

[Solution ]

显然是贪心地取数，数取的越大，就可以越早使和大于等于 (h) 。

因此我们都考虑优先选择大的数，然后一步一步往小的数考虑。

所以我们可以把 " 矩阵内大于等于 (k) 的数 " 的和以及个数求出来，然后去二分取数的最小值，把最优性问题转化成一个判定性问题。

(~)

注意到：

对于50%的数据，满足R, C≤200，M≤200,000；

另有50%的数据，满足R＝1，C≤500,000，M≤20,000；

(~)

对于 (type1) ，可以直接用 (O(1000RC)) 的时间预处理（二维前缀和）。

(~)

对于 (type2) ，发现 (O(1000RC)) 的时间预处理会 (T) 飞。

观察到 (R=1) ，此时实质上这个矩阵是一个序列，解决 " 区间内大于等于 (k) 的数 " 的和以及个数正是主席树擅长的，用主席树维护一下即可。

[Code ]

#include<cstdio>

#define RI register int

using namespace std;

inline int read()
{
	int x=0,f=1;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}

const int N1=210,N2=500100,MLOGN=10001000;

const int MaxV=1000;

int n,m,Q;

int val[N1][N1];
int sum[N1][N1][MaxV+100],cnt[N1][N1][MaxV+100];

int GetSum(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 GetCnt(int x1,int y1,int x2,int y2,int k)
{
	return cnt[x2][y2][k]-cnt[x1-1][y2][k]-cnt[x2][y1-1][k]+cnt[x1-1][y1-1][k];
}

void Work1()
{
	for(RI i=1;i<=n;i++)
		for(RI j=1;j<=m;j++)
			val[i][j]=read();

	for(RI k=1;k<=MaxV;k++)
		for(RI i=1;i<=n;i++)
			for(RI j=1;j<=m;j++)
			{
				sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]+(val[i][j]>=k?val[i][j]:0);
				cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(val[i][j]>=k?1:0);
			}

	while(Q--)
	{
		int x1=read(),y1=read(),x2=read(),y2=read(),h=read();

		if(GetSum(x1,y1,x2,y2,1)<h)
		{
			puts("Poor QLW");
			continue;
		}

		int l=1,r=MaxV;
		while(l<r)
		{
			int mid=(l+r+1)/2;
			if(GetSum(x1,y1,x2,y2,mid)<h)
				r=mid-1;
			else
				l=mid;
		}

		printf("%d
",GetCnt(x1,y1,x2,y2,l)-(GetSum(x1,y1,x2,y2,l)-h)/l);
	}
}

int seq[N2];

int tot,root[N2];
struct SegmentTree{
	int lc,rc;
	int cnt;
	int sum;
}t[MLOGN];

int New()
{
	tot++;
	t[tot].lc=t[tot].rc=t[tot].cnt=t[tot].sum=0;
	return tot;
}

void insert(int &p,int now,int l,int r,int delta,int val1,int val2)
{
	p=New();
	t[p]=t[now];
	t[p].cnt+=val1;
	t[p].sum+=val2;
	if(l==r)return;
	int mid=(l+r)/2;
	if(delta<=mid)
		insert(t[p].lc,t[now].lc,l,mid,delta,val1,val2);
	else
		insert(t[p].rc,t[now].rc,mid+1,r,delta,val1,val2);
}

int ask(int p,int q,int l,int r,int h)
{
	if(l==r)return (h-1)/l+1;
	int mid=(l+r)/2;
	int rcnt=t[t[q].rc].cnt-t[t[p].rc].cnt,
		rsum=t[t[q].rc].sum-t[t[p].rc].sum;
	if(h<=rsum)
		return ask(t[p].rc,t[q].rc,mid+1,r,h);
	else
		return ask(t[p].lc,t[q].lc,l,mid,h-rsum)+rcnt;
}

void Work2()
{
	n=m;
	for(RI i=1;i<=n;i++)
		seq[i]=read();

	for(RI i=1;i<=n;i++)
		insert(root[i],root[i-1],1,MaxV,seq[i],1,seq[i]);

	while(Q--)
	{
		int l,r,h;
		read(),l=read(),read(),r=read(),h=read();

		if(t[root[r]].sum-t[root[l-1]].sum<h)
		{
			puts("Poor QLW");
			continue;
		}

		printf("%d
",ask(root[l-1],root[r],1,MaxV,h));
	}
}

int main()
{
	n=read(),m=read(),Q=read();

	if(n>1)
		Work1();
	else
		Work2();

	return 0; 
}

[Thanks for watching ]