`

【线段树 成段更新】HDU 4027

阅读更多

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
1
1
分享到:
评论

相关推荐

    hdu 1166线段树

    标题与描述均提到了“hdu 1166线段树”,这表明文章的核心是关于线段树在解决特定问题中的应用。线段树是一种数据结构,主要用于处理区间查询和更新操作,尤其是在大规模数据集上。在本例中,通过分析给定的部分代码...

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    hdu acm1166线段树

    hdu 1166线段树代码

    线段树完整版

    2. **区间加法更新** (`range addition update`): 在某些情况下,我们需要更新某个区间内的元素值,可以通过在线段树上打上标记的方式来快速完成,而不是逐个更新每个元素。 #### 六、总结 线段树是一种非常强大的...

    线段树入门学习(兼解HDU1754)

    线段树的核心思想是将一个区间分解成多个子区间,然后对每个子区间进行预处理,存储区间的信息。这样,当我们需要查询或修改一个区间时,可以通过查询或修改子区间来快速得到结果。线段树通常用二叉树的形式表示,每...

    线段树题目

    - **HDU 1698** 和 **POJ 3468**:成段更新问题。这类问题要求能够快速更新某个区间的所有元素,并且还能够查询某些特定的信息。解决方案通常是在线段树的节点中额外存储一些辅助信息,例如区间更新值等,同时采用...

    HH神总结的线段树专辑-超经典的

    **线段树**是一种用于高效处理区间查询与更新操作的数据结构。它可以用来解决一系列与区间有关的问题,例如区间求和、区间最值等问题。相较于其他数据结构如平衡二叉搜索树等,线段树在实现上更加简洁且易于理解。 ...

    线段树入门

    线段树入门资料,有利于初学者学习,让他们详细了解线段树。

    hdu 3333 turing tree 解题报告

    对于每个区间,从`bi+1`开始插入,直到`b(i+1)`,每次插入都会更新线段树中对应区间的`value`。 5. 插入完成后,可以通过查询线段树得到每个区间 `[ai, bi]` 内不同数字的和。 **时间复杂度分析**: - 每个数字...

    hdu 300+ AC 代码

    2. **线段树**:线段树是一种数据结构,用于高效地处理区间查询和更新操作。它可以实时维护一个区间内的信息,如求和、最大值或最小值。线段树在处理动态区间问题时非常有效,如在数组上进行区间加法、区间求和等...

    【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源

    【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源

    hdu-acm源代码(上百道源代码)

    例如,"zscas060102"可能是一道关于计算几何或图论的题目,源代码可能会涉及到线段树、优先队列等高级数据结构,以及动态规划或回溯搜索等算法。"yfndq2"可能是一个字符串处理或模式匹配的问题,可能用到了KMP、...

    HDU算法讲解的PPT

    9. **计算几何**:包括线段树、最近点对问题、多边形碰撞检测等,这些算法在图形学、游戏开发等领域有着广泛应用。 10. **数学基础**:如数论、组合数学、线性代数等,良好的数学基础对于理解和设计算法至关重要。 ...

    【题解】「HDU1166」敌兵布阵(线段树)

    题面 【题目描述】 有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为正...

    hdu ACM代码 每种算法都有分类

    6. **数据结构**:线段树、斐波那契堆、平衡树(AVL、红黑树)、字典树(Trie)、并查集等,这些高级数据结构可以高效地解决区间查询、维护、集合操作等问题。 7. **几何算法**:二维和三维几何问题,如点线面的...

    HDU题目分类

    - **1247**:这道题目可能涉及到高级数据结构,如并查集、线段树等。 ### 其他算法 除了上述主要类别外,还有一系列其他类型的算法和技术也非常重要,包括但不限于贪心算法、搜索算法等。 - **1086**:这道题目...

    个人训练实用知识库分享知识分享

    通过在线段树中进行查询和更新,我们可以解决区间问题。 十一、博弈、树形dp 在多个题目中,我们学习了博弈、树形dp的应用。博弈、树形dp是一种动态规划算法,用于解决游戏相关的问题。通过定义状态转移方程式,...

    ACM知识点.docx

    在该文件中,线段树是一个典型的线段树问题,要求使用线段树来解决区间查询问题。解题时需要熟悉线段树的定义和性质,并了解其应用场景。 11. KMP(2) : KMP(2) 是一个典型的 KMP 算法问题,要求使用 KMP 算法来...

Global site tag (gtag.js) - Google Analytics