题目大意

有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 ;
}

最新文章

  1. 对C语言islower、isupper、isdigit函数的测试
  2. 基于webapi的移动互联架构
  3. 二十七、EFW框架BS系统开发中的MVC模式探讨
  4. [windows驱动]windows8.1驱动调试前戏
  5. Fast-paced Multiplayer
  6. Redis学习手册(Hashes数据类型)
  7. RHCS集群理论暨最佳实践
  8. 【转】android 物理按键
  9. WSImport
  10. iOS工程上传AppStore时遇到的问题“ERROR ITMS-90046”解析
  11. poj 1204 Word Puzzles(字典树)
  12. c#二进制、十进制、16进制之间的转换
  13. AsParallel 用法
  14. 如何用VMware打开vmdk文件
  15. Java笔记—— 格式化的输入和输出
  16. redisi应用--布隆过滤器
  17. 185. [USACO Oct08] 挖水井
  18. React入门——制作一个TodoList App
  19. inode 与black 特点与简介
  20. mongodb的Limit|skip|投影|排序|消除重复

热门文章

  1. Python 2.7教程
  2. Java 面向对象编程——第一章 初识Java
  3. Protocol Buffers in HBase
  4. 关于Linux下C编译错误(警告)cast from &#39;void*&#39; to &#39;int&#39; loses precision
  5. 基于MVC的应用框架之Struts前奏
  6. zoj 2112 动态区间求第k大
  7. JSONObject put,accumulate,element的区别(转载)
  8. 从协议VersionedProtocol开始1
  9. [Swift2.0系列]Defer/Guard 基础语法
  10. js 弹出div窗口 可移动 可关闭 (转)