luogu2468 [SDOI2010]粟粟的书架

二合一……
#include <iostream>

#include <cstdio>

using namespace std;

int r, c, m, a[205][205], val[205][205][1005], num[205][205][1005];

int xu, yu, xv, yv, hi, rot[500005], lson[7200005], rson[7200005];

int sum[7200005], siz[7200005], cnt, w[500005];

int getVal(int xu, int yu, int xv, int yv, int hi){

	return val[xv][yv][hi]-val[xu-1][yv][hi]-val[xv][yu-1][hi]+val[xu-1][yu-1][hi];

}

int getNum(int xu, int yu, int xv, int yv, int hi){

	return num[xv][yv][hi]-num[xu-1][yv][hi]-num[xv][yu-1][hi]+num[xu-1][yu-1][hi];

}

void work1(){

	for(int i=1; i<=r; i++)

		for(int j=1; j<=c; j++)

			scanf("%d", &a[i][j]);

	for(int k=1; k<=1000; k++)

		for(int i=1; i<=r; i++)

			for(int j=1; j<=c; j++){

				val[i][j][k] = val[i-1][j][k] + val[i][j-1][k] - val[i-1][j-1][k] + ((a[i][j]>=k)?a[i][j]:0);

				num[i][j][k] = num[i-1][j][k] + num[i][j-1][k] - num[i-1][j-1][k] + ((a[i][j]>=k)?1:0);

			}

	while(m--){

		scanf("%d %d %d %d %d", &xu, &yu, &xv, &yv, &hi);

		if(getVal(xu, yu, xv, yv, 1)<hi)	printf("Poor QLW\n");

		else{

			int l=1, r=1000, mid, ans;

			while(l<=r){

				mid = (l + r) >> 1;

				if(getVal(xu, yu, xv, yv, mid)>=hi){

					ans = mid;

					l = mid + 1;

				}

				else	r = mid - 1;

			}

			ans = getNum(xu, yu, xv, yv, ans) - (getVal(xu, yu, xv, yv, ans)-hi) / ans;//并不是说>=ans的都要选，==ans的只选一部分

			printf("%d\n", ans);

		}

	}

}

int build(int l, int r){

	int rt=++cnt;

	int mid=(l+r)>>1;

	if(l==r)	return rt;

	if(l<=mid)	lson[rt] = build(l, mid);

	if(mid<r)	rson[rt] = build(mid+1, r);

	return rt;

}

int update(int pre, int l, int r, int x){

	int rt=++cnt;

	int mid=(l+r)>>1;

	lson[rt] = lson[pre]; rson[rt] = rson[pre];

	siz[rt] = siz[pre] + 1;

	sum[rt] = sum[pre] + x;

	if(l==r)	return rt;

	if(x<=mid)	lson[rt] = update(lson[pre], l, mid, x);

	if(mid<x)	rson[rt] = update(rson[pre], mid+1, r, x);

	return rt;

}

int query(int qwq, int qaq, int l, int r, int h){

	int mid=(l+r)>>1;

	int tmp=sum[rson[qaq]]-sum[rson[qwq]];

	if(l==r)	return (h%l==0)?(h/l):(h/l+1);

	if(h<=tmp)	return query(rson[qwq], rson[qaq], mid+1, r, h);

	else	return query(lson[qwq], lson[qaq], l, mid, h-tmp)+siz[rson[qaq]]-siz[rson[qwq]];

}

void work2(){

	for(int i=1; i<=c; i++)

		scanf("%d", &w[i]);

	rot[0] = build(1, 1000);

	for(int i=1; i<=c; i++)

		rot[i] = update(rot[i-1], 1, 1000, w[i]);

	while(m--){

		scanf("%d %d %d %d %d", &xu, &yu, &xv, &yv, &hi);

		if(sum[rot[yv]]-sum[rot[yu-1]]<hi)	printf("Poor QLW\n");

		else	printf("%d\n", query(rot[yu-1], rot[yv], 1, 1000, hi));

	}

}

int main(){

	cin>>r>>c>>m;

	if(r!=1)	work1();

	else	work2();

	return 0;

}
巴特西

luogu2468 [SDOI2010]粟粟的书架

最新文章

热门文章
