KIDx的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4027
加了输入外挂之后,排第二,还不错!
下面的代码没加外挂,运行时间是:375ms,还可以
#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define M 100005
#define Max 26
#define LL __int64
struct Node{
int l, r;
LL v;
}N[M<<2];
LL v[M];
void create (int u, int a, int b)
{
N[u].l = a, N[u].r = b;
if (a == b)
{
N[u].v = v[a];
return ;
}
int mid = (a + b) >> 1, lc = u+u, rc = u+u+1;
create (lc, a, mid);
create (rc, mid+1, b);
N[u].v = N[lc].v + N[rc].v;
}
void update (int u, int a, int b)
{
if (N[u].v == N[u].r - N[u].l + 1) //说明从l到r都是1,不用往下更新了
return ;
if (N[u].l == N[u].r)
{
N[u].v = LL(sqrt ((double)N[u].v)); //自底向上更新
return ;
}
int lc = u+u, rc = u+u+1;
if (a <= N[lc].r)
update (lc, a, b);
if (b >= N[rc].l)
update (rc, a, b);
N[u].v = N[lc].v + N[rc].v;
}
LL find (int u, int a, int b)
{
if (N[u].v == N[u].r - N[u].l + 1) //同理lazy一下
return min (N[u].r, b) - max (N[u].l, a) + 1;
if (a <= N[u].l && b >= N[u].r)
return N[u].v;
LL m1 = 0, m2 = 0;
int lc = u+u, rc = u+u+1;
if (a <= N[lc].r)
m1 = find (lc, a, b);
if (b >= N[rc].l)
m2 = find (rc, a, b);
return m1+m2;
}
int main()
{
char ch[2];
int n, i, m, cc = 1, a, b;
while (~scanf ("%d", &n))
{
for (i = 1; i <= n; i++)
scanf ("%I64d", v+i);
create (1, 1, n);
scanf ("%d", &m);
printf ("Case #%d:\n", cc++);
while (m--)
{
scanf ("%s%d%d", ch, &a, &b);
if (a > b) a ^= b, b ^= a, a ^= b; //又是坑人的陷阱
if (ch[0] == '1') printf ("%I64d\n", find (1, a, b));
else update (1, a, b);
}
printf ("\n");
}
return 0;
}
- 大小: 12.3 KB
分享到:
相关推荐
标题与描述均提到了“hdu 1166线段树”,这表明文章的核心是关于线段树在解决特定问题中的应用。线段树是一种数据结构,主要用于处理区间查询和更新操作,尤其是在大规模数据集上。在本例中,通过分析给定的部分代码...
ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...
hdu 1166线段树代码
2. **区间加法更新** (`range addition update`): 在某些情况下,我们需要更新某个区间内的元素值,可以通过在线段树上打上标记的方式来快速完成,而不是逐个更新每个元素。 #### 六、总结 线段树是一种非常强大的...
线段树的核心思想是将一个区间分解成多个子区间,然后对每个子区间进行预处理,存储区间的信息。这样,当我们需要查询或修改一个区间时,可以通过查询或修改子区间来快速得到结果。线段树通常用二叉树的形式表示,每...
- **HDU 1698** 和 **POJ 3468**:成段更新问题。这类问题要求能够快速更新某个区间的所有元素,并且还能够查询某些特定的信息。解决方案通常是在线段树的节点中额外存储一些辅助信息,例如区间更新值等,同时采用...
**线段树**是一种用于高效处理区间查询与更新操作的数据结构。它可以用来解决一系列与区间有关的问题,例如区间求和、区间最值等问题。相较于其他数据结构如平衡二叉搜索树等,线段树在实现上更加简洁且易于理解。 ...
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
对于每个区间,从`bi+1`开始插入,直到`b(i+1)`,每次插入都会更新线段树中对应区间的`value`。 5. 插入完成后,可以通过查询线段树得到每个区间 `[ai, bi]` 内不同数字的和。 **时间复杂度分析**: - 每个数字...
2. **线段树**:线段树是一种数据结构,用于高效地处理区间查询和更新操作。它可以实时维护一个区间内的信息,如求和、最大值或最小值。线段树在处理动态区间问题时非常有效,如在数组上进行区间加法、区间求和等...
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
例如,"zscas060102"可能是一道关于计算几何或图论的题目,源代码可能会涉及到线段树、优先队列等高级数据结构,以及动态规划或回溯搜索等算法。"yfndq2"可能是一个字符串处理或模式匹配的问题,可能用到了KMP、...
9. **计算几何**:包括线段树、最近点对问题、多边形碰撞检测等,这些算法在图形学、游戏开发等领域有着广泛应用。 10. **数学基础**:如数论、组合数学、线性代数等,良好的数学基础对于理解和设计算法至关重要。 ...
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
6. **数据结构**:线段树、斐波那契堆、平衡树(AVL、红黑树)、字典树(Trie)、并查集等,这些高级数据结构可以高效地解决区间查询、维护、集合操作等问题。 7. **几何算法**:二维和三维几何问题,如点线面的...
- **1247**:这道题目可能涉及到高级数据结构,如并查集、线段树等。 ### 其他算法 除了上述主要类别外,还有一系列其他类型的算法和技术也非常重要,包括但不限于贪心算法、搜索算法等。 - **1086**:这道题目...
通过在线段树中进行查询和更新,我们可以解决区间问题。 十一、博弈、树形dp 在多个题目中,我们学习了博弈、树形dp的应用。博弈、树形dp是一种动态规划算法,用于解决游戏相关的问题。通过定义状态转移方程式,...
在该文件中,线段树是一个典型的线段树问题,要求使用线段树来解决区间查询问题。解题时需要熟悉线段树的定义和性质,并了解其应用场景。 11. KMP(2) : KMP(2) 是一个典型的 KMP 算法问题,要求使用 KMP 算法来...