ZOJ Problem Set - 3635

题目大意

有n个从1..n标号的座位,按时间顺序给出每个客人来的时候是坐在第几个空座位,最后给若干个询问问第i号客人坐在哪里

分析

线段树+二分

 // Fast Sequence Operations II
// Rujia Liu
// 输入格式:
// n m 数组范围是a[1]~a[n],初始化为0。操作有m个
// 1 L R v 表示设a[L]=a[L+1]=...=a[R] = v。其中v > 0
// 2 L R 查询a[L]~a[R]的sum, min和max
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxnode = <<; int _sum, _min, _max, op, qL, qR, v;
int vist[maxnode];
struct IntervalTree {
int sumv[maxnode], minv[maxnode], maxv[maxnode], setv[maxnode]; // 维护信息
void maintain(int o, int L, int R) {
int lc = o*, rc = o*+;
if(R > L) {
sumv[o] = sumv[lc] + sumv[rc];
minv[o] = min(minv[lc], minv[rc]);
maxv[o] = max(maxv[lc], maxv[rc]);
}
if(setv[o] >= ) { minv[o] = maxv[o] = setv[o]; sumv[o] = setv[o] * (R-L+); }
} // 标记传递
void pushdown(int o) {
int lc = o*, rc = o*+;
if(setv[o] >= ) { //本结点有标记才传递。注意本题中set值非负,所以-1代表没有标记
setv[lc] = setv[rc] = setv[o];
setv[o] = -; // 清除本结点标记
}
} void update(int o, int L, int R) {
int lc = o*, rc = o*+;
if(qL <= L && qR >= R) { // 标记修改
setv[o] = v;
} else {
pushdown(o);
int M = L + (R-L)/;
if(qL <= M) update(lc, L, M); else maintain(lc, L, M);
if(qR > M) update(rc, M+, R); else maintain(rc, M+, R);
}
maintain(o, L, R);
} void query(int o, int L, int R) {
if(setv[o] >= ) { // 递归边界1:有set标记
_sum += setv[o] * (min(R,qR)-max(L,qL)+);
_min = min(_min, setv[o]);
_max = max(_max, setv[o]);
} else if(qL <= L && qR >= R) { // 递归边界2:边界区间
_sum += sumv[o]; // 此边界区间没有被任何set操作影响
_min = min(_min, minv[o]);
_max = max(_max, maxv[o]);
} else { // 递归统计
int M = L + (R-L)/;
if(qL <= M) query(o*, L, M);
if(qR > M) query(o*+, M+, R);
}
}
}; const int INF = ; IntervalTree tree; int main() {
int n, m,num;
while(scanf("%d", &n) !=EOF){
memset(&tree, , sizeof(tree));
memset(tree.setv, -, sizeof(tree.setv));
tree.setv[] = ;
v=;
qL=;
qR=n;
tree.update(,,n);
tree.query(,,n);
for(int i=;i<=n;i++)
{
scanf("%d",&num);
qL=;qR=n;
_sum = ;
int l=,r=n,mid;
while(l<r)
{
mid=(l+r)/;
qR=mid;
tree.query(, , n);
if(_sum>=num)
r=mid;
else
l=mid+;
_sum = ;
}
vist[i]=l;
v=;
qL=l;
qR=l;
tree.update(,,n);
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d",&num);
printf("%d",vist[num]);
if(i!=m)
printf(" "); }
printf("\n");
}
return ;
}
上一篇:C# 如何判断数据是否为 NaN


下一篇:高性能 CSS3 动画