【粟粟的书架】【题解】

题目传送门

Solution

数据范围分为两部分，第一部分二分，第二部分主席树。
其实一开始没想到第一部分怎么做，因为我原本想直接二分排名，但前缀和没法维护排名。

但是实际上二分选取的数的最小值一样能做，而且可以容易用前缀和维护。（可以记住这个trick）

第二部分就是主席树的模板了，把区间看做两个前缀主席树相减，如果右子树够用就递归到右子树，否则累计上右子树答案，再递归到左子树。

Code

#include
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
const int N=210,M=5e5+10,W=1010;
struct node{
	int ls,rs,sum,cnt;
}t[M*15];
int sum[N][N][W],cnt[N][N][W];
int tot,a[M],rt[M];
int n,m,T;
int build(int l,int r)
{
	int p=++tot;
	if(l==r) return p;
	int mid=l+r>>1;
	t[p].ls=build(l,mid);
	t[p].rs=build(mid+1,r);
	return p;
}
void pushup(int x)
{
	t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
	t[x].cnt=t[t[x].ls].cnt+t[t[x].rs].cnt;
}
int insert(int x,int l,int r,int pos)
{
	int p=++tot;
	t[p]=t[x];
	if(l==r){
		t[p].cnt++;
		t[p].sum+=l;
		return p;
	}
	int mid=l+r>>1;
	if(pos<=mid) t[p].ls=insert(t[p].ls,l,mid,pos);
	else t[p].rs=insert(t[p].rs,mid+1,r,pos);
	pushup(p);
	return p;
}
int query(int p,int q,int l,int r,int val)
{
	if(l==r){
		if(val%l==0) return val/l;
		return val/l+1;
	}
	int mid=l+r>>1;
	int rsum=t[t[q].rs].sum-t[t[p].rs].sum,rcnt=t[t[q].rs].cnt-t[t[p].rs].cnt;
//	if(val==rsum) return rcnt;
	if(val<=rsum) return query(t[p].rs,t[q].rs,mid+1,r,val);
	return query(t[p].ls,t[q].ls,l,mid,val-rsum)+rcnt;
}
inline void write(int x)
{
	if(x<0) {putchar('-');x=~(x-1);}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int main()
{
    n=read();m=read();T=read();
    if(n==1)
    {
    	int maxn=0;
    	for(int i=1;i<=m;++i) {
    		a[i]=read();
    		maxn=max(maxn,a[i]);
		}
    	rt[0]=build(1,maxn);
    	for(int i=1;i<=m;++i){
    		rt[i]=insert(rt[i-1],1,maxn,a[i]);
		}
		for(int i=1;i<=T;++i)
		{
			int x[3],y[3];
			x[1]=read(),y[1]=read();
			x[2]=read(),y[2]=read();
			int h=read();
			if(t[rt[y[2]]].sum-t[rt[y[1]-1]].sum>1;
					if(sum[x[2]][y[2]][mid]-sum[x[1]-1][y[2]][mid]-sum[x[2]][y[1]-1][mid]+sum[x[1]-1][y[1]-1][mid]>=h) l=mid;
					else r=mid;
				}
				write(cnt[x[2]][y[2]][l+1]-cnt[x[1]-1][y[2]][l+1]-cnt[x[2]][y[1]-1][l+1]+cnt[x[1]-1][y[1]-1][l+1]+(int)ceil((h-(sum[x[2]][y[2]][l+1]-sum[x[1]-1][y[2]][l+1]-sum[x[2]][y[1]-1][l+1]+sum[x[1]-1][y[1]-1][l+1]))*1.0/l*1.0));
			    puts("");
			}
		}
	}
	return 0;
}