这几天在做线段树的题目,回忆一下以前的东西,同时也再进一步提高一点,结果在做一道简单的题的时候又出现了错误,调试了整整两天,找同学问了问才找到了问题所在。
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1698
just a hook
经验:要考虑怎样标记分裂和 何时分裂
错误源代码:
#include <stdio.h>
#define N 200010
typedef struct{
int l, r, mid;
int kind;
int sum;
}NODE;
NODE nod[4 * N];
void build(int ll, int rr, int ind)
{
nod[ind].l = ll;
nod[ind].r = rr;
nod[ind].kind = 1;
if(ll == rr)
{
nod[ind].sum = 1;
return ;
}
nod[ind].mid = (ll + rr) >> 1;
build(ll, nod[ind].mid, ind * 2);
build(nod[ind].mid + 1, rr, ind * 2 + 1);
nod[ind].sum = nod[ind * 2].sum + nod[ind * 2 + 1 ].sum;
}
void update(int ll, int rr, int k, int ind)
{
if(ll == nod[ind].l && rr == nod[ind].r)
{
nod[ind].kind = k;
nod[ind].sum = k * (rr - ll + 1);
return ;
}
//nod[ind].kind = -1;
if((nod[ind].sum != nod[ind * 2].sum + nod[ind * 2 + 1].sum))
//错误就出在这,只有当父节点被完全覆盖时,这才对,否则就会丢失修改或者改成其他的。
// 反例:
// 2 --test case number
// 4 --4 hooks
// 2 -- two operations
// 1 1 2 -- the first hook change into 2
// 2 4 2 -- the last 3 hooks change into 2
//另一个好例子:
/*
40
4
4
2 2 3
3 4 2
1 4 2
1 1 3
*/
{
nod[ind * 2].kind = nod[ind].kind;
nod[ind * 2 + 1].kind = nod[ind].kind;
nod[ind * 2].sum = nod[ind].kind * (nod[ind * 2].r - nod[ind * 2].l + 1);
nod[ind * 2 + 1].sum = nod[ind].kind * (nod[ind * 2 + 1].r - nod[ind * 2 + 1].l + 1);
//nod[ind] = -1;
}
if(rr <= nod[ind].mid)
{
update(ll, rr, k, ind * 2);
}
else if(ll > nod[ind].mid)
update(ll, rr, k, ind * 2 + 1);
else
{
update(ll, nod[ind].mid, k, ind * 2);
update(nod[ind].mid + 1, rr, k, ind * 2 + 1);
}
nod[ind].sum = nod[ind * 2].sum + nod[ind * 2 + 1].sum;
}
int main()
{
int tc;
int n;
int i, j;
int x, y, k, q;
while(scanf("%d", &tc) == 1)
{
for(j = 1; j <= tc; j++)
{
scanf("%d", &n);
build(1, n, 1);
scanf("%d", &q);
for(i = 0; i < q; i++)
{
scanf("%d%d%d", &x, &y, &k);
if(x > y)
{
int t = x;
x = y;
y = t;
}
update(x, y, k, 1);
}
printf("Case %d: The total value of the hook is %d.\n", j, nod[1].sum);
}
}
return 0;
}
正确代码:
#include <stdio.h>
#define N 200010
typedef struct{
int l, r, mid;
int kind;
int sum;
}NODE;
NODE nod[4 * N];
void build(int ll, int rr, int ind)
{
nod[ind].l = ll;
nod[ind].r = rr;
nod[ind].kind = 1;
if(ll == rr)
{
nod[ind].sum = 1;
return ;
}
nod[ind].mid = (ll + rr) >> 1;
build(ll, nod[ind].mid, ind * 2);
build(nod[ind].mid + 1, rr, ind * 2 + 1);
nod[ind].sum = nod[ind * 2].sum + nod[ind * 2 + 1 ].sum;
}
void update(int ll, int rr, int k, int ind)
{
if(ll == nod[ind].l && rr == nod[ind].r)
{
nod[ind].kind = k;
nod[ind].sum = k * (rr - ll + 1);
return ;
}
//if((nod[ind].sum != nod[ind * 2].sum + nod[ind * 2 + 1].sum)|| (nod[ind].kind != nod[ind * 2].kind) || (nod[ind].kind != nod[ind * 2 + 1].kind))
if(nod[ind].kind != -1)//如果没有被分裂,要分裂 ,或者说两边的都已经更新完了
{
nod[ind * 2].kind = nod[ind].kind;
nod[ind * 2 + 1].kind = nod[ind].kind;
nod[ind * 2].sum = nod[ind].kind * (nod[ind * 2].r - nod[ind * 2].l + 1);
nod[ind * 2 + 1].sum = nod[ind].kind * (nod[ind * 2 + 1].r - nod[ind * 2 + 1].l + 1);
nod[ind].kind = -1;//标记已被分裂
}
if(rr <= nod[ind].mid)
{
update(ll, rr, k, ind * 2);
}
else if(ll > nod[ind].mid)
update(ll, rr, k, ind * 2 + 1);
else
{
update(ll, nod[ind].mid, k, ind * 2);
update(nod[ind].mid + 1, rr, k, ind * 2 + 1);
}
nod[ind].sum = nod[ind * 2].sum + nod[ind * 2 + 1].sum;
}
int main()
{
int tc;
int n;
int i, j;
int x, y, k, q;
while(scanf("%d", &tc) == 1)
{
for(j = 1; j <= tc; j++)
{
scanf("%d", &n);
build(1, n, 1);
scanf("%d", &q);
for(i = 0; i < q; i++)
{
scanf("%d%d%d", &x, &y, &k);
if(x > y)
{
int t = x;
x = y;
y = t;
}
update(x, y, k, 1);
}
printf("Case %d: The total value of the hook is %d.\n", j, nod[1].sum);
}
}
return 0;
}
分享到:
相关推荐
线段树完全版,涉及到线段树的所有用法。 包括单点更新(增减,替换),区间求和,区间最值。 区间求最大值的位置。 成段更新(延迟标记,增减)。 离散化 扫描线
ACM竞赛中线段树的原理及应用。如何处理区间问题,区间快速求和求RMQ。将朴素O(n)的复杂度编程O(logn)
原理就大概如图所示,线段树的每个节点都是原数组的一段区间和,而叶子节点就是原数组对应 的值 建树代码: void build(int p,int lf,int rt){//建树 ans[p]=0; if(lf==rt) { ans[p]=A[lf]; return ; } int mid...
线段树Java实现——SegmentTree.txt 与文章中的讲解一致,几乎每句代码均有注释 阅读更方便,详细解析线段树 以区间求和为例进行代码的书写和解析。
本项目旨在利用C++语言实现线段树和树状数组,以解决在计算机科学和工程中的区间查询和修改问题。线段树和树状数组是处理静态和动态区间操作的高效数据结构,广泛应用于数据分析、图像处理和游戏开发等领域。 模块...
校门外的树 (线段树, 区间合并, 分块思想) P1161 开灯 (异或) P1321 单词覆盖还原 (想想这种方法,怎么这么简单!!) P2415 集合求和 (数学) P1518 两只塔姆沃斯牛 The Tamworth Two (存储历史状态,用于判断是否存在...
构造线段树的算法 段树理论 查找范围总和 有三种重叠类型 查找范围和流 查找范围和算法 更新操作 时间复杂度 比较 回顾段树 段树是二叉树 树底层的节点对应数组元素 其他节点包含处理范围查询所需的信息 最小范围...
+ [线段树](#线段树) + [单调队列](#单调队列) + [哈希表](#哈希表) + [Splay](#splay) * [图论](#图论) + [图论](#图论-1) + [模型建立](#模型建立) + [网络流](#网络流) + [最短路](#最短路) + [欧拉路]...
14.3 区间树 思考题 本章注记 第四部分 高级设计和分析技术 第15章 动态规划 15.1 钢条切割 15.2 矩阵链乘法 15.3 动态规划原理 15.4 最长公共子序列 15.5 最优二叉搜索树 思考题 本章...
但是,我们也指出了递归树的最佳用途,即利用它来产生猜测,再利用替代方法对猜测进行验证。 ·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,...
但是,我们也指出了递归树的最佳用途,即利用它来产生猜测,再利用替代方法对猜测进行验证。 ·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,...