赤裸裸的线段树,数据量很大,加了IO优化函数。
#include <stdio.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define MIN(a, b) (a) < (b) ? (a): (b)
#define MAX(a, b) (a) > (b) ? (a): (b)
#define inf 20000000
#define N 1000001
struct tree_node
{
int min, max;
};
struct tree_node tree[2097152];
int n, M;
int max[N], min[N];
/* IO优化 */
inline void put(int x){
static char s[20];
int bas;
if(x< 0) {
putchar('-');
x = -x;
}
if(x == 0) {
putchar('0');
return;
}
bas = 0;
for(;x;x/=10) s[bas++] = x%10+'0';
for(;bas--;) putchar(s[bas]);
}
inline void build_tree()
{
int i;
//不用的叶子节点
for (i = n+1; i%M != 1; i++) {
tree[(i%M)+M].min = inf;
tree[(i%M)+M].max = -inf;
}
//分支节点
for (i = M-1; i > 0 ; i--) {
tree[i].min = MIN(tree[i<<1].min, tree[(i<<1)+1].min);
tree[i].max = MAX(tree[i<<1].max, tree[(i<<1)+1].max);
}
}
inline void query(int s, int t)
{
int i;
i = s;
max[i] = -inf;
min[i] = inf;
for (s = s+M-1, t = t+M+1; (s^t) != 1; s >>= 1, t >>= 1) {
if (~s&1) {
max[i] = MAX(max[i], tree[s^1].max);
min[i] = MIN(min[i], tree[s^1].min);
}
if (t&1) {
max[i] = MAX(max[i], tree[t^1].max);
min[i] = MIN(min[i], tree[t^1].min);
}
}
}
int main()
{
int i, k;
scanf("%d %d", &n, &k);
for (M = 1; M < (n+2); M <<= 1);
for (i = M+1; i <= n+M; i++) {
scanf("%d", &tree[i].min);
tree[i].max = tree[i].min;
}
build_tree();
for (i = 1; i <= (n-k+1); i++) {
query(i, i+k-1);
}
put(min[1]);
for (i = 2; i <= (n-k+1); i++) {
putchar(' ');
put(min[i]);
}
putchar('\n');
put(max[1]);
for (i = 2; i <= (n-k+1); i++) {
putchar(' ');
put(max[i]);
}
putchar('\n');
return 0;
}
分享到:
相关推荐
在`poj2823.cpp`源代码中,我们可以看到实现线段树的具体细节,包括如何初始化、更新以及查询线段树。此外,代码可能还包括了问题的输入输出处理,错误检查,以及可能的优化策略,比如lazy propagation(惰性传播)...
在本教程中,我们将深入探讨线段树的基本概念,以及如何使用Java实现线段树来解决实际问题,如POJ3468题目。 首先,理解线段树的核心在于它的分治思想。线段树将一个大区间(通常是一维数组)分成多个小区间,每个...
线段树是一种数据结构,常用于处理区间查询与更新的问题,它能高效地支持动态维护区间最值、求和等问题。在本题“POJ 3264”中,我们可能面临的是一个区间最值或者区间求和的计算任务。线段树的基本思想是将数组或...
在本篇博文中,我们将深入探讨线段树的概念,以及如何实现懒惰更新(Lazy Propagation)策略,同时结合POJ1823问题进行实战应用。懒惰更新是优化线段树性能的关键技巧,它避免了频繁地对每个节点进行更新,从而减少...
标题中的“POJ3277.rar_3277 poj_poj3277_多个面积_线段树”是指一个与编程竞赛相关的压缩文件,特别提到了POJ(Problemset Online Judge)的第3277号问题。POJ是一个著名的在线编程竞赛平台,参与者需要解决各种...
### POJ 2352 Stars - 树状数组与线段树实现 #### 题目背景 POJ 2352 Stars 是一道经典的算法题目,它提供了使用树状数组或线段树来解决的可能性。这两种数据结构都是为了高效处理区间查询问题而设计的。在这篇...
10. **POJ 2528 线段树.txt**:这是第三个线段树相关的题目,解题报告可能会深入讲解线段树在不同场景下的应用。 通过阅读这些解题报告,你可以学习到各种高级算法的应用,如动态规划、搜索算法、数据结构(如线段...
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
- **ZOJ 1610** 和 **POJ 2777**:这两道题都是典型的线段覆盖问题,需要利用线段树来解决。基本思路是通过线段树维护每个区间是否被覆盖的状态。对于每个覆盖请求,更新线段树对应区间中的覆盖状态,并统计完全被...
### ACM数据结构之树状数组和线段树 #### 线段树 线段树是一种非常有效的数据结构,主要用于解决区间查询问题。它能够快速地处理区间内的各种操作,如查询、修改等。 ##### 线段树的定义与特性 线段树本质上是一...
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样
描述中提到的“POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。”揭示了问题的核心内容。这是一个涉及到线段树数据结构的编程问题,目标是计算某个区域的面积,可能是在二维平面上。线段树是一种高效...
- 线段树:如`poj2528, poj2828`。 - RMQ(区间查询):如`poj3264, poj3368`。 - 并查集的高级应用:如`poj1703, poj2492`。 - **搜索** - 最优化剪枝和可行性剪枝:如`poj3411, poj1724`。 - **动态规划** ...
* 线段树:例如 poj2528、poj2828、poj2777、poj2886、poj2750。 * 静态二叉检索树:例如 poj2482、poj2352。 * 树状树组:例如 poj1195、poj3321。 * RMQ:例如 poj3264、poj3368。 * 并查集的高级应用:例如 ...
在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...
poj2528、poj2777等是线段树的题目,poj2482、poj2352等涉及平衡树,poj1195、poj3321则训练了树状数组。 5. **搜索算法的优化**:poj1699、poj3411等训练搜索技巧和剪枝方法,poj3373、poj1691则介绍了记忆化搜索。...
线段树是一种常用的数据结构,线段树的核心思想是将数据存储在一个树形结构中,然后通过树的遍历进行搜索。例如,在搜索中,线段树可以用于快速地搜索数据。 树状数组是一种常用的数据结构,树状数组的核心思想是将...