手动博客搬家：本文发表于20170822 21:30:17, 原地址https://blog.csdn.net/suncongbo/article/details/77488127
URL: http://acm.hdu.edu.cn/showproblem.php?pid=2795题目大意:有一个hw的木板 (h, w<=1e9), 现在有n (n<=2e5)张1xi的海报要贴在木板上，按1~n的顺序每次贴海报时会选择最上的一排的最左边贴 (海报不能互相覆盖), 求每张海报会被贴在哪一行。最上方的一行编号为1, 以此类推。
样例解析:
如下
column 12345
row 1: 11333
row 2: 2222X
row 3: 444XXX: 未摆放;
对应行列上的数是摆放在此的海报的编号思路分析:本题实际上是一个贪心的思想。
每次可以从最上一行向下枚举剩余的空间，找到第一个能够贴上第i个海报的行，然后输出，更新即可。
时间复杂度O(n^2), 无法AC.
于是我们可以考虑二分的思想:
用线段树维护每一行剩余的空间的大小的最大值。
每次查询时，采用类似于二分答案的方法，每到达线段树的一个节点，若它的左子树最大值>=xi, 则左子树中必存在合法的最大答案，查询左子树；
假如左子树中的行无法装下第i张海报，但右子树最大值<=xi, 此时说明右子树中存在合法的最大答案，于是“退而求其次”，查询右子树。
如果两棵子树最大值都>xi, 则无法张贴此海报，于是输出-1.
查询完毕后，做一个单点修改，将答案所在的行剩余空间减去xi.
其实，最后一种情况不需要考虑。
假如整个[1, h]区间的最大值<xi, 则直接输出-1, 无需查询。
但是我们无法开4e9 (4h)如此大的数组，怎么办呢？
其实假如h>n, 那么下面的(h-n)行全部浪费了，不影响结果。
因此，h=min(h,n);
只开8e5 (4n)的数组即可。
代码呈现:(Time: 3151 MS; 11256 KB; Code: 1576 B)
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 2e5;
struct Node
{
int left,right;
int maxi;
};
struct SegmentTree
{
Node nd[MAXN*4+8];
void init()
{
for(int i=1; i<=MAXN*4; i++)
{
nd[i].left = nd[i].right = nd[i].maxi = 0;
}
}
void build(int lbound,int rbound,int pos,int tot)
{
nd[pos].left = lbound;
nd[pos].right = rbound;
if(lbound==rbound)
{
nd[pos].maxi = tot;
return;
}
int mid = (lbound+rbound)/2;
build(lbound,mid,2*pos,tot);
build(mid+1,rbound,2*pos+1,tot);
nd[pos].maxi = tot;
}
void modify_subs(int bound,int val,int pos)
{
int mid = (nd[pos].left+nd[pos].right)/2;
if(nd[pos].left==nd[pos].right)
{
nd[pos].maxi-=val;
return;
}
if(bound<=mid) modify_subs(bound,val,2*pos);
else modify_subs(bound,val,2*pos+1);
nd[pos].maxi = max(nd[2*pos].maxi,nd[2*pos+1].maxi);
}
int query(int pos,int val)
{
int mid = (nd[pos].left+nd[pos].right)/2;
if(nd[pos].left==nd[pos].right) return nd[pos].left;
int ans;
if(val<=nd[2*pos].maxi) return query(2*pos,val);
else return query(2*pos+1,val);
}
};
SegmentTree sgt;
int n,m,p;
int main()
{
while(scanf("%d%d%d",&n,&m,&p)!=EOF)
{
if(n>p) n = p;
sgt.init();
sgt.build(1,n,1,m);
for(int i=1; i<=p; i++)
{
int x;
scanf("%d",&x);
if(sgt.nd[1].maxi < x)
{
printf("-1\n");
continue;
}
int ans = sgt.query(1,x);
printf("%d\n",ans);
if(ans>0) sgt.modify_subs(ans,x,1);
}
}
return 0;
}