- 浏览: 118701 次
- 性别:
- 来自: 北京
最新评论
又一道线段树
#include <cstdio> #include <cstring> #include <algorithm> using std::sort; const int size = 10000000 + 5, maxn = (10000 + 5) * 2; int n, p[maxn * 2], lp, hash[size]; struct seg_t { int li, ri; } seg[maxn]; int A, B, color, tree[maxn * 2 * 3]; bool exist[maxn]; void add(int low, int high, int node) { if (A <= low && high <= B) { tree[node] = color; } else if (low <= B && A <= high) { if (tree[node] != -1) tree[node * 2] = tree[node * 2 + 1] = tree[node]; int mid = (low + high) / 2; add(low, mid, node * 2); add(mid + 1, high, node * 2 + 1); if (tree[node * 2] == tree[node * 2 + 1]) tree[node] = tree[node * 2]; else tree[node] = -1; } } int query(int low, int high, int node) { if (A <= low && high <= B && tree[node] != -1) { if (!exist[tree[node]]) { exist[tree[node]] = true; return 1; } } else if (low <= B && A <= high && low < high) { int mid = (low + high) / 2; return query(low, mid, node * 2) + query(mid + 1, high, node * 2 + 1); } return 0; } int main() { int tcs; scanf("%d", &tcs); while (tcs--) { scanf("%d", &n); lp = 0; for (int i = 1; i <= n; ++i) { scanf("%d%d", &seg[i].li, &seg[i].ri); p[lp++] = seg[i].li; p[lp++] = seg[i].ri; } sort(p, p + lp); int cnt = 1, left, right; left = hash[p[0]] = cnt; for (int i = 1; i < lp; ++i) { if (p[i] == p[i - 1]) continue; else { if (p[i - 1] + 1 < p[i]) ++cnt; hash[p[i]] = ++cnt; } } right = hash[p[lp - 1]]; memset(tree, 0xff, sizeof(tree)); for (int i = 1; i <= n; ++i) { A = hash[seg[i].li], B = hash[seg[i].ri]; color = i; add(left, right, 1); } memset(exist, false, sizeof(exist)); A = left, B = right; printf("%d\n", query(left, right, 1)); } return 0; }
发表评论
-
lower_bound and upper_bound
2012-02-09 00:36 1159/** * @brief Finds the ... -
HDU 3954
2012-02-05 10:43 844线段树变种,也是在2logn段上面做文章 /* * ... -
HDU 4027
2012-02-04 22:09 859线段树变种 在2logn段上面做文章,swap(x, y)太阴 ... -
ICPC编码建议
2011-10-28 09:52 893写代码最重要的是清晰,包括思路的清晰和代码结构的清晰。我们无法 ... -
[转载]TopCoder插件
2011-09-08 22:13 979转载自:http://acm.cugb.edu.cn/blog ... -
UVALive 5112 - Sales Prediction
2011-01-06 10:19 1192封装了矩阵类 比赛做得很郁闷,为什么别人写得很长、很罗嗦的代码 ... -
hdu 3236
2010-12-12 14:10 801终于能过这道题了,算是背包必做题之一吧 /* * Au ... -
pku 1018
2010-12-11 15:18 608写了两三个版本,最后这个效率最高 #include < ... -
布斯(Booth)乘法
2010-10-07 19:59 1144源自http://watashi.ws/blog/1515/z ... -
高斯消元
2010-10-07 14:18 806import java.util.*; import j ... -
整数划分
2010-10-07 10:38 842#include <cstdio> #inc ... -
Treap
2010-09-18 22:19 983// Treap // Tested: bjtu1057 ... -
矩阵快速幂
2010-09-18 14:24 1053typedef LL matrix[55][55]; ... -
maximum clique 最大团
2010-09-02 18:12 1136最大团模板 #include <cstdio> ... -
计算Jacobi符号
2010-08-31 13:15 1298Quadratic reciprocity The Jacob ... -
Java 高效I/O
2010-08-19 16:54 783static BufferedReader cin = ... -
DLX pku 3076
2010-08-11 23:45 882标准数独,精确覆盖 // pku3076.cpp #in ... -
DLX hust 1017
2010-08-11 16:50 851“精确覆盖”问题 #include <cstdio& ... -
DLX hdu 3498
2010-08-11 16:48 1044“多重覆盖”或“重复覆盖”问题 #include < ... -
hdu 3509
2010-08-09 11:22 1007推导公式的题目,矩阵幂关键就在于构造系数矩阵 备忘: S(n, ...
相关推荐
pku 1904 King's Quest 的AC代码
pku部分题代码,不多,试一下怎么上传文件!
pascal source code for http://acm.pku.edu.cn/JudgeOnline/problem?id=3728
pku1000 pku1000程序 解题报告
pku经典题目解题报告 pku经典题目解题报告
深度优先遍历 搜索算法 ACM PKU 1011 S.doc
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训练集,主要是说明相似度计算的样例数据。