- 浏览: 118238 次
- 性别:
- 来自: 北京
最新评论
查询最左端的连续空房间,思想是二分,不过是在线段树上做的二分,所以线段树结点上需要记录一些附加信息,为二分提供条件
又WA了几次才过的,总结经验就是:
更新区间的过程,递归进入子节点前,如果父节点被完全覆盖(在之前的操作中整个区间被修改为住人或空房),那么要相应地修改子节点;从子节点回溯出来后,根据子节点的情况更新父节点。
查询区间的过程也是,要考虑父节点被完全覆盖的情况,这时就不用再往下递归了
又WA了几次才过的,总结经验就是:
更新区间的过程,递归进入子节点前,如果父节点被完全覆盖(在之前的操作中整个区间被修改为住人或空房),那么要相应地修改子节点;从子节点回溯出来后,根据子节点的情况更新父节点。
查询区间的过程也是,要考虑父节点被完全覆盖的情况,这时就不用再往下递归了
#include <cstdio> const int maxN = 50000 + 5; struct node_t { int ll, mm, rr; } tree[maxN * 3]; int max3(int x, int y, int z) { x = x > y ? x : y; x = x > z ? x : z; return x; } int left, right; bool checkIn; void check(int low, int high, int node) { if (left <= low && high <= right) { tree[node].ll = tree[node].mm = tree[node].rr = (checkIn ? 0 : high - low + 1); } else if (left <= high && low <= right) { node_t &lch = tree[node * 2], &rch = tree[node * 2 + 1]; int mid = (low + high) / 2; if (tree[node].mm == high - low + 1) { lch.ll = lch.mm = lch.rr = mid - low + 1; rch.ll = rch.mm = rch.rr = high - mid; } if ((tree[node].ll | tree[node].mm | tree[node].rr) == 0) { lch.ll = lch.mm = lch.rr = 0; rch.ll = rch.mm = rch.rr = 0; } check(low, mid, node * 2); check(mid + 1, high, node * 2 + 1); tree[node].ll = lch.ll + (lch.ll == mid - low + 1 ? rch.ll : 0); tree[node].rr = (rch.rr == high - mid ? lch.rr : 0) + rch.rr; tree[node].mm = max3(lch.rr + rch.ll, lch.mm, rch.mm); } } int need; int find(int low, int high, int node) { if (tree[node].mm == high - low + 1 || (tree[node].ll | tree[node].mm | tree[node].rr) == 0) { if (tree[node].mm >= need) return low; } else if (low < high) { if (tree[node].ll >= need) return low; int mid = (low + high) / 2; node_t &lch = tree[node * 2], &rch = tree[node * 2 + 1]; if (tree[node].mm >= need) { if (lch.mm >= need) return find(low, mid, node * 2); if (lch.rr + rch.ll >= need) return mid - lch.rr + 1; if (rch.mm >= need) return find(mid + 1, high, node * 2 + 1); } if (tree[node].rr >= need) return high - tree[node].rr + 1; } return 0; } int main() { int N, M, req, X, D; scanf("%d%d", &N, &M); left = 1, right = N, checkIn = false; check(1, N, 1); while (M--) { scanf("%d", &req); if (req == 1) { scanf("%d", &D); need = D; X = find(1, N, 1); printf("%d\n", X); if (X != 0) { left = X, right = X + D - 1, checkIn = true; check(1, N, 1); } } else { scanf("%d%d", &X, &D); left = X, right = X + D - 1, checkIn = false; check(1, N, 1); } } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1149/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 838线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 849线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 884写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 969转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1184封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 797终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 599写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1133源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 796import java.util.*; import j ... -
整数划分
2010-10-07 10:38 836#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 977// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1047typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1130最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1289Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 771static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 874标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 843“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1037“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1003推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ...
相关推荐
pku部分题代码,不多,试一下怎么上传文件!
pku1000 pku1000程序 解题报告
pku经典题目解题报告 pku经典题目解题报告
pku1664源代码
PKU JudgeOnline FAQ 中文版 常见问题解答
8数码代码pku1077,300ms(哈希+广度搜索)
ppt word PKU 课件 五星级灰常强大
ACM代码 北大pku。 搞ACM的可以参考一下。代码还是挺规范的。有接近150道题目的代码。
benchmark (PKU-MMD) for continuous multi-modality 3D human action understanding and cover a wide range of complex human activities with well annotated information. PKU-MMD contains 1076 long video ...
PKU 2339 Rock, Scissors, Paper 源代码
有一些代码是pku上的,希望大家看后给我留言,看看我的代码那里有问题??
pku acm 1469 COURSES 代码 二分图的最大匹配的匈牙利算法 解题报告请访问:http://blog.csdn.net/china8848
这是关于PKU上的题目分类 很详细 适合不同水平的童鞋们参考
北京大学pku2317 Questions and answers c++标程 文件名为2371.cpp
我写的解题报告,关于度限制生成树的 网址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1639<br>题目:Picnic Planning 来源:East Central North America 2000
PKU的oj分类 可以通过分类进行练习~~~
分词训练用的pku训练集,主要是说明相似度计算的样例数据。
pku acm 1042 贪心法
pku2482--Stars in Your Window的源程序