【[SDOI2010]粟粟的书架】

时间：2023-03-09 02:53:46
【[SDOI2010]粟粟的书架】

第一问的做法好像不太一样

首先第二问非常简单，直接在主席树上二分就好了，单次查询的复杂度\(O(logn)\)

第一问并没有想到有二分这种神仙操作，依旧用的是主席树

我们可以对矩阵建出主席树，也就是像二维前缀和那样的主席树

但是众所周知我们写二维前缀和的时候是这么写的

	pre[x][y]+=pre[x-1][y]+pre[x][y-1]-pre[x-1][y-1]

我们发现这个样子我们根本没有办法优秀的建出主席树，因为这个样子还需要容斥

我们可以按照高维前缀和的思路来处理

for(re int i=1;i<=n;i++)

		for(re int j=1;j<=m;j++) c[i][j]+=c[i][j-1];

for(re int i=1;i<=n;i++)

		for(re int j=1;j<=m;j++) c[i][j]+=c[i-1][j];

也就是我们可以直接按照上面的方式来处理，所一我们每次需要的只有像一个主席树里添加一个点和把两个主席树合并的操作了

添加一个点是常规操作，合并两个主席树自然是需要线段树合并了

不过这里启发式合并好像更能保证复杂度的样子

单次查询像第二问一样就可以了，就是拎出四棵主席树来差分就好了

尽管现在预处理变得有些慢，但是现在单次查询的复杂度还是非常优秀的\(O(log(nm))=O(logn+logm)\)

这个题值域范围非常小，于是可以直接用二维前缀和进行二分，好像也是非常优秀的\(O(log(\text{值域范围}))\)

于是这个方法被吊打了

还是放上代码吧

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define re register

#define maxn 500005

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int n,m,Q;

namespace solve1

{

	int rt[201][201];

	int a[201][201],b[201*201],c[201][201];

	int l[201*201*801],r[201*201*801],d[201*201*801],sum[201*201*801];

	int sz,cnt;

	inline int find(int x)

	{

		int l=1,r=sz;

		while(l<=r)

		{

			int mid=l+r>>1;

			if(b[mid]==x) return mid;

			if(b[mid]<x) l=mid+1;

				else r=mid-1;

		}

		return 0;

	}

	int change(int pre,int pos,int val,int x,int y)

	{

		int root=++cnt;

		d[root]=d[pre]+1,sum[root]=sum[pre]+val;

		if(x==y) return root;

		l[root]=l[pre],r[root]=r[pre];

		int mid=x+y>>1;

		if(pos<=mid) l[root]=change(l[pre],pos,val,x,mid);

			else r[root]=change(r[pre],pos,val,mid+1,y);

		return root;

	}

	int merge(int a,int b,int x,int y)

	{

		if(!a) return b;if(!b) return a;

		int root=++cnt;

		if(x==y)

		{

			sum[root]=sum[a]+sum[b];

			d[root]=d[a]+d[b];

			return root;

		}

		int mid=x+y>>1;

		l[root]=merge(l[a],l[b],x,mid),r[root]=merge(r[a],r[b],mid+1,y);

		d[root]=d[l[root]]+d[r[root]],sum[root]=sum[l[root]]+sum[r[root]];

		return root;

	}

	int query(int p1,int p2,int p3,int p4,int x,int y,int k)

	{

		if(x==y)

		{

			int t=-b[x];

			if(k%t==0) return k/t;

			return k/t+1;

		}

		int now=sum[l[p1]]+sum[l[p2]]-sum[l[p3]]-sum[l[p4]];

		int mid=x+y>>1;

		if(now<k) return query(r[p1],r[p2],r[p3],r[p4],mid+1,y,k-now)+d[l[p1]]+d[l[p2]]-d[l[p3]]-d[l[p4]];

		return query(l[p1],l[p2],l[p3],l[p4],x,mid,k);

	}

	inline void solve()

	{

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++) a[i][j]=c[i][j]=read(),a[i][j]=-1*a[i][j],b[++sz]=a[i][j];

		std::sort(b+1,b+sz+1);

		sz=std::unique(b+1,b+sz+1)-b-1;

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++) a[i][j]=find(a[i][j]);

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++) rt[i][j]=change(rt[i][j-1],a[i][j],c[i][j],1,sz);

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++) rt[i][j]=merge(rt[i-1][j],rt[i][j],1,sz);

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++) c[i][j]+=c[i][j-1];

		for(re int i=1;i<=n;i++)

			for(re int j=1;j<=m;j++) c[i][j]+=c[i-1][j];

		int sx,sy,dx,dy,K;

		while(Q--)

		{

			sx=read(),sy=read(),dx=read(),dy=read(),K=read();

			if(c[dx][dy]+c[sx-1][sy-1]-c[dx][sy-1]-c[sx-1][dy]<K) puts("Poor QLW");

			else printf("%d\n",query(rt[dx][dy],rt[sx-1][sy-1],rt[dx][sy-1],rt[sx-1][dy],1,sz,K));

		}

	}

}

namespace solve2

{

	int rt[maxn];

	int l[maxn*40],r[maxn*40],d[maxn*40],sum[maxn*40];

	int a[maxn],b[maxn],c[maxn];

	int sz,cnt;

	inline int find(int x)

	{

		int l=1,r=sz;

		while(l<=r)

		{

			int mid=l+r>>1;

			if(b[mid]==x) return mid;

			if(b[mid]<x) l=mid+1;

				else r=mid-1;

		}

		return 0;

	}

	int change(int pre,int pos,int val,int x,int y)

	{

		int root=++cnt;

		d[root]=d[pre]+1,sum[root]=sum[pre]+val;

		if(x==y) return root;

		l[root]=l[pre],r[root]=r[pre];

		int mid=x+y>>1;

		if(pos<=mid) l[root]=change(l[pre],pos,val,x,mid);

			else r[root]=change(r[pre],pos,val,mid+1,y);

		return root;

	}

	int query(int p1,int p2,int x,int y,int k)

	{

		if(x==y)

		{

			int t=-b[x];

			if(k%t==0) return k/t;

			return k/t+1;

		}

		int now=sum[l[p1]]-sum[l[p2]];

		int mid=x+y>>1;

		if(now<k) return query(r[p1],r[p2],mid+1,y,k-now)+d[l[p1]]-d[l[p2]];

		return query(l[p1],l[p2],x,mid,k);

	}

	inline void solve()

	{

		std::swap(n,m);

		for(re int i=1;i<=n;i++) a[i]=-1*read(),b[++sz]=a[i],c[i]=-1*a[i];

		std::sort(b+1,b+sz+1);

		sz=std::unique(b+1,b+sz+1)-b-1;

		for(re int i=1;i<=n;i++) a[i]=find(a[i]);

		for(re int i=1;i<=n;i++) rt[i]=change(rt[i-1],a[i],c[i],1,sz);

		for(re int i=1;i<=n;i++) c[i]+=c[i-1];

		int o,x,y,K;

		while(Q--)

		{

			o=read(),x=read(),o=read(),y=read(),K=read();

			if(c[y]-c[x-1]<K) puts("Poor QLW");

			else printf("%d\n",query(rt[y],rt[x-1],1,sz,K));

		}

	}

}

int main()

{

	n=read(),m=read(),Q=read();

	if(n<=200&m<=200) solve1::solve();

		else solve2::solve();

	return 0;

}

相关文章