题解 P2468 【[SDOI2010]粟粟的书架】

2019-02-16

字数统计: 1.4k字 | 阅读时长: 7min

看了这道题的其他题解，本蒟蒻发现大部分都是将其分成两道题二分加主席树做的，本蒟蒻便来分享一波自己的蒟蒻做法–用主席树维护二维矩阵的信息。

这道题全程用主席树，不过要分情况讨论，对于r=1的情况，直接上裸的主席树，对于r=200，c=200的情况我们用主席树来维护矩阵(0,0)到(x,y)的信息，它由(x-1,y)到(0,0)的信息加上(x,0)到(x,y)的信息得到。代码如下

for(register int i=1;i<=r;i++)
for(register int j=1;j<=c;j++)
{
	build(1,tot,root[i-1][j],root[i][j],m[i][j],tmp[m[i][j]]);
	int tt=root[i][j];
	for(register int t=1;t<j;t++) 
	build(1,tot,tt,root[i][j],m[i][t],tmp[m[i][t]]),qu[++cnt]=tt,tt=root[i][j];
}

而对于查询，则像二维前缀和一样；

inline int ask(int l,int r,int a,int b,int c,int d,int v)
{
	if(l==r) 
	{
		int t=tr[a].size+tr[b].size-tr[c].size-tr[d].size;
		while((int)(t-1)*tmp[l]>=v) t--;
		return t;
	}
	int mid=(l+r)>>1,siz=tr[tr[a].ls].size+tr[tr[b].ls].size-tr[tr[c].ls].size-tr[tr[d].ls].size;
	int k=tr[tr[a].ls].sum+tr[tr[b].ls].sum-tr[tr[c].ls].sum-tr[tr[d].ls].sum;
	if(k>=v)    return ask(l,mid,tr[a].ls,tr[b].ls,tr[c].ls,tr[d].ls,v);
	else return ask(mid+1,r,tr[a].rs,tr[b].rs,tr[c].rs,tr[d].rs,v-k)+siz;
}

然而！这样写是过不了这道题的；

对于构建主席树的过程中，我们不停的更新root[x][y],导致大量节点只是一个过程量，空间被大量浪费，所需空间在这道题的极限情况下高达600+MB;

接下来，蒟蒻将展示代码(带注释)，该问题的解决办法。

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 3e7;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

struct node
{
	int ls,size,rs,sum;
}tr[N];

int root[201][201],tcnt,rt[500001],tot;//因数据范围不同，分别用root[x][y],rt[x]来记录两种情况下的树根 
int m[201][201],mt[500001],tmp[500001];//m,mt同上记录数据，tmp离散化数组 
int qu; 

inline void build(int l,int r,int x,int &y,int k,int v)//k,为离散化后的值，v为离散化之前的值 
{
	if(qu)	y=qu,qu=0;//qu记录无用节点，循环利用 
	else 	y=++tcnt;
	tr[y]=tr[x];tr[y].sum+=v,tr[y].size+=1;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(k<=mid) build(l,mid,tr[x].ls,tr[y].ls,k,v);
	else     build(mid+1,r,tr[x].rs,tr[y].rs,k,v);
}

inline int ask(int l,int r,int a,int b,int c,int d,int v)
{
	if(l==r) 
	{
		int t=tr[a].size+tr[b].size-tr[c].size-tr[d].size;//一个值可能有多个，我们并不是全部都需要 
		while((int)(t-1)*tmp[l]>=v) t--;
		return t;
	}
	int mid=(l+r)>>1,ss=tr[tr[a].ls].size+tr[tr[b].ls].size-tr[tr[c].ls].size-tr[tr[d].ls].size;
	int k=tr[tr[a].ls].sum+tr[tr[b].ls].sum-tr[tr[c].ls].sum-tr[tr[d].ls].sum;
	if(k>=v)    return ask(l,mid,tr[a].ls,tr[b].ls,tr[c].ls,tr[d].ls,v);
	else return ask(mid+1,r,tr[a].rs,tr[b].rs,tr[c].rs,tr[d].rs,v-k)+ss;
}

int r,c,q;
int a,b,x,y;
int v;

int main()
{
	read(r),read(c),read(q);
	for(register int i=1;i<=r;i++)for(register int j=1;j<=c;j++)
	if(r==1) read(mt[j]),tmp[++tot]=mt[j];
	else     read(m[i][j]),tmp[++tot]=m[i][j];
	sort(tmp+1,tmp+1+tot,greater<int>());//从大到小排序 
	tot=unique(tmp+1,tmp+1+tot)-tmp-1;
	if(r==1)//分类讨论 
	{
		for(register int i=1;i<=c;i++) mt[i]=lower_bound(tmp+1,tmp+1+tot,mt[i],greater<int>())-tmp;
		for(register int i=1;i<=c;i++) build(1,tot,rt[i-1],rt[i],mt[i],tmp[mt[i]]);
		for(register int i=1;i<=q;i++)
		{
			read(y),read(x),read(b),read(a),read(v);
			if(v>(tr[rt[a]].sum-tr[rt[x-1]].sum)) printf("Poor QLW\n");
			else printf("%d\n",ask(1,tot,rt[a],0,rt[x-1],0,v));
		}
	}
	else
	{
		for(register int i=1;i<=r;i++)for(register int j=1;j<=c;j++) m[i][j]=lower_bound(tmp+1,tmp+1+tot,m[i][j],greater<int>())-tmp;
		for(register int i=1;i<=r;i++)for(register int j=1;j<=c;j++)
		{ 
			if(j>=i)//root[i][j]无论从root[i-1][j]更新出来，还是从root[i][j-1]都是一样的，但是一个需重建i个节点，另一个需要重建j个节点。我们根据情况来判断那种情况更省空间 
			{
				build(1,tot,root[i][j-1],root[i][j],m[i][j],tmp[m[i][j]]);
				int tt=root[i][j]; 
				for(register int t=1;t<i;t++) 
				build(1,tot,tt,root[i][j],m[t][j],tmp[m[t][j]]),qu=tt,tt=root[i][j];
			}
			else
			{
				build(1,tot,root[i-1][j],root[i][j],m[i][j],tmp[m[i][j]]);
				int tt=root[i][j];
				for(register int t=1;t<j;t++) 
				build(1,tot,tt,root[i][j],m[i][t],tmp[m[i][t]]),qu=tt,tt=root[i][j];
			}
		}
		for(register int i=1;i<=q;i++)
		{
			read(x),read(y),read(a),read(b),read(v);
			if(v>(tr[root[a][b]].sum+tr[root[x-1][y-1]].sum-tr[root[a][y-1]].sum-tr[root[x-1][b]].sum)) printf("Poor QLW\n");
			else printf("%d\n",ask(1,tot,root[x-1][y-1],root[a][b],root[a][y-1],root[x-1][b],v));
		}
	}
	return 0;
}

好了，题解到此结束。结束撒花！！

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/e1a316a0.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！