线段树的成段更新，需要用到延迟标记
就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候
否则就会退化到O(n)的复杂度
1.hdu 1698 Just a Hook
大意是每次把某一段所有数的值改变成某个值，最后求总和。
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
int left, right, mid;
int cover, len, sum;
}tree[4 * MAXN];
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) / 2;
tree[C].len = tree[C].right - tree[C].left + 1;
tree[C].cover = 1;
tree[C].sum = tree[C].cover * tree[C].len;
if(s == e)
return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void up(int C)
{
tree[C].sum = tree[L(C)].sum + tree[R(C)].sum;
}
void down(int C)
{
if(tree[C].cover)
{
tree[L(C)].cover = tree[R(C)].cover = tree[C].cover;
tree[L(C)].sum = tree[L(C)].len * tree[L(C)].cover;
tree[R(C)].sum = tree[R(C)].len * tree[R(C)].cover;
tree[C].cover = 0;
}
}
void update(int s, int e, int k, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
tree[C].cover = k;
tree[C].sum = tree[C].cover * tree[C].len;
return;
}
down(C);
if(tree[C].mid < s) update(s, e, k, R(C));
else if(tree[C].mid >= e) update(s, e, k, L(C));
else
{
update(s, tree[C].mid, k, L(C));
update(tree[C].mid + 1, e, k, R(C));
}
up(C);
}
int main()
{
//freopen("d:/data.in","r",stdin);
//freopen("d:/data.out","w",stdout);
int t, n, i, x, y, z, cas = 0, m;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
make_tree(1, n, 1);
scanf("%d", &m);
for(i = 0; i < m; i++)
{
scanf("%d%d%d", &x, &y, &z);
update(x, y, z, 1);
}
printf("Case %d: The total value of the hook is %d.\n", ++cas, tree[1].sum);
}
return 0;
}
2. POJ 3468A Simple Problem with Integers
这题比上面那道的操作稍微复杂了一点，把某个区间的数统一加上某个值。
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
int left, right, mid;
__int64 cover, len;
__int64 sum;
}tree[4 * MAXN];
__int64 a[100005];
void up(int C)
{
tree[C].sum = tree[L(C)].sum + tree[R(C)].sum;
}
void down(int C)
{
if(tree[C].cover)
{
tree[L(C)].cover += tree[C].cover;
tree[R(C)].cover += tree[C].cover;
tree[L(C)].sum += tree[C].cover * tree[L(C)].len;
tree[R(C)].sum += tree[C].cover * tree[R(C)].len;
tree[C].cover = 0;
}
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) / 2;
tree[C].cover = 0;
tree[C].sum = 0;
tree[C].len = tree[C].right - tree[C].left + 1;
if(s == e)
{
tree[C].sum = a[s];
return;
}
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
up(C);
}
void update(int s, int e, __int64 k, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
tree[C].cover += k;
tree[C].sum += k * tree[C].len;
return;
}
down(C);
if(tree[C].mid < s) update(s, e, k, R(C));
else if(tree[C].mid >= e) update(s, e, k, L(C));
else
{
update(s, tree[C].mid, k, L(C));
update(tree[C].mid + 1, e, k, R(C));
}
up(C);
}
__int64 query(int s, int e, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
return tree[C].sum;
down(C);
__int64 tmp = 0;
if(tree[C].mid < s) tmp += query(s, e, R(C));
else if(tree[C].mid >= e) tmp += query(s, e, L(C));
else
{
tmp += query(s, tree[C].mid, L(C));
tmp += query(tree[C].mid + 1, e, R(C));
}
return tmp;
}
int main()
{
//freopen("d:/data.in","r",stdin);
//freopen("d:/data.out","w",stdout);
int n, m, i, x, y;
__int64 z;
char s[5];
scanf("%d%d", &n, &m);
for(i = 1; i <= n; i++)
scanf("%I64d", &a[i]);
make_tree(1, n, 1);
while(m--)
{
scanf("%s", s);
if(s[0] == 'Q')
{
scanf("%d%d", &x, &y);
printf("%I64d\n",query(x, y, 1));
}
else if(s[0] == 'C')
{
scanf("%d%d%I64d", &x, &y, &z);
update(x, y, z, 1);
}
}
return 0;
}
3.poj 2528 Mayor’s posters
大意就是往墙上按区间涂色，看最后能看见的颜色个数
比较麻烦的就是离散化的事情，先把所有的坐标存下来，去重后映射一下，这时就有些问题了，比如原始坐标是1, 3, 6, 10，映射完了是0, 1, 2, 3，3和6本来中间还有几块的，离散完了成相邻的了，所以这里就要处理一下，1,3,6, 10就要处理成1,2,3,4,6,7,10之类的，总之相邻的坐标之差如果大于1了，就在中间添加一个适当的数表示这之间还有块。
然后就建线段树，查询的时候查整个线段树中颜色的个数就行了。
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
int left, right, mid;
int cover;
}tree[16 * MAXN];
int a[4 * MAXN];
int l[MAXN];
int r[MAXN];
int ans, n;
bool used[MAXN];
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].cover = -1;
tree[C].mid = (s + e) / 2;
if(s == e) return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void down(int C)
{
if(tree[C].cover != -1)
{
tree[L(C)].cover = tree[R(C)].cover = tree[C].cover;
tree[C].cover = -1;
}
}
void update(int s, int e, int k, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
tree[C].cover = k;
return;
}
down(C);
if(tree[C].mid < s) update(s, e, k, R(C));
else if(tree[C].mid >= e) update(s, e, k, L(C));
else
{
update(s, tree[C].mid, k, L(C));
update(tree[C].mid + 1, e, k, R(C));
}
}
void query(int C)
{
if(tree[C].cover != -1)
{
if(!used[tree[C].cover])
{
ans++;
used[tree[C].cover] = 1;
}
return;
}
if(tree[C].left == tree[C].right)
return;
query(L(C));
query(R(C));
}
int b_search(int v)
{
int left = 0, right = n - 1;
while(left <= right)
{
int mid = (left + right) / 2;
if(a[mid] == v) return mid;
else if(a[mid] > v) right = mid - 1;
else left = mid + 1;
}
return 0;
}
int main()
{
//freopen("d:/data.in","r",stdin);
//freopen("d:/data.out","w",stdout);
int t, m, i;
scanf("%d", &t);
while(t--)
{
ans = 0;
memset(used, 0, sizeof(used));
scanf("%d", &m);
int cnt = 0;
for(i = 0; i < m; i++)
{
scanf("%d%d", &l[i], &r[i]);
a[cnt++] = l[i];
a[cnt++] = r[i];
}
sort(a, a + cnt);
n = unique(a, a + cnt) - a;
for(i = n - 1; i > 0; i--)
{
if(a[i] - a[i - 1] != 1) a[n++] = a[i - 1] + 1;
}
sort(a, a + n);
n = unique(a, a + n) - a;
make_tree(0, n - 1, 1);
for(i = 0; i < m; i++)
{
int ll = b_search(l[i]);
//printf("ll %d\n", ll);
int rr = b_search(r[i]);
update(ll, rr, i, 1);
//printf("rr %d\n", rr);
}
query(1);
printf("%d\n", ans);
}
return 0;
}
然后更神的是这道题可以用并查集做
从acmol的空间看的http://blog.acmol.com/?p=751
/*
ID: sdj22251
PROG: inflate
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 9*9*9*9
#define INF 1000000000
using namespace std;
int hash[10000005];
int father[40005];
int a[10005], b[10005], x[20005];
bool v[40005];
int find(int x)
{
if(father[x] == -1) return x;
int t = find(father[x]);
father[x] = t;
return t;
}
int main()
{
int T, n;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d%d", &a[i], &b[i]);
x[2 * i] = a[i];
x[2 * i + 1] = b[i];
}
sort(x, x + 2 * n);
int cnt = unique(x, x + 2 * n) - x;
hash[x[0]] = 0;
for(int i = 1; i < cnt; i++)
{
int flag = 0;
if(x[i - 1] + 1 != x[i]) flag = 1;
hash[x[i]] = hash[x[i - 1]] + flag + 1;
}
int ans = 0;
memset(v, 0, sizeof(v));
memset(father, -1, sizeof(father));
for(int i = n - 1; i >= 0; i--)
{
bool flag = false;
int fa = find(hash[a[i]]), fb;
for(int j = hash[b[i]]; j >= hash[a[i]]; j = fb - 1)
{
fb = find(j);
if(!v[fb]) v[fb] = flag = true;
if(fa != fb) father[fb] = fa;
}
if(flag) ans++;
}
printf("%d\n", ans);
}
return 0;
}
4.POJ 2777 Count Color
几乎与2528一摸一样的题，只不过更加裸了
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 100005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
int left, right, mid;
int cover;
}tree[4 * MAXN];
bool used[33];
int ans;
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].cover = 1;
tree[C].mid = (s + e) / 2;
if(s == e) return;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void down(int C)
{
if(tree[C].cover != -1)
{
tree[L(C)].cover = tree[R(C)].cover = tree[C].cover;
tree[C].cover = -1;
}
}
void update(int s, int e, int k, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
tree[C].cover = k;
return;
}
down(C);
if(tree[C].mid < s) update(s, e, k, R(C));
else if(tree[C].mid >= e) update(s, e, k, L(C));
else
{
update(s, tree[C].mid, k, L(C));
update(tree[C].mid + 1, e, k, R(C));
}
}
void query(int s, int e, int C)
{
if(tree[C].cover != -1)
{
if(!used[tree[C].cover])
{
ans++;
used[tree[C].cover] = 1;
}
return;
}
if(tree[C].left == tree[C].right)
return;
if(tree[C].mid < s) query(s, e, R(C));
else if(tree[C].mid >= e) query(s, e, L(C));
else
{
query(s, tree[C].mid, L(C));
query(tree[C].mid + 1, e, R(C));
}
}
int main()
{
//freopen("d:/data.in","r",stdin);
//freopen("d:/data.out","w",stdout);
int n, m, t, x, y, z, i;
char s[5];
scanf("%d%d%d", &n, &m, &t);
make_tree(1, n, 1);
while(t--)
{
scanf("%s", s);
if(s[0] == 'C')
{
scanf("%d%d%d", &x, &y, &z);
if(x > y) swap(x, y);
update(x, y, z, 1);
}
else
{
scanf("%d%d", &x, &y);
ans = 0;
memset(used, 0, sizeof(used));
query(x, y, 1);
printf("%d\n", ans);
}
}
return 0;
}
分享到：
相关推荐
线段树是一种非常有效的数据结构，主要用于解决区间查询和更新的问题，常用于算法竞赛和实际应用中的问题求解。接下来，我们将详细探讨“线段树六题”中各个题目的相关知识点。 ### 1. PKU2352 star2 校门外的树 **...
核心操作之一是区间分解，即将一个给定的区间分解成线段树中的一系列不重叠的子区间。 1. **操作过程**： - 从根节点开始递归进行区间分解。 - 走到节点[L, R]时，如果要分解的区间正好是[L, R]，则找到了一个...
- **ZOJ 3279**：这是一道简单的线段树题目，要求改变level的数量，并查询第几个的level是多少。解决此类问题时，重点在于如何在线段树中正确地维护和更新这些level信息。 - **HDU 3397**：这道题需要设计两个标记...
通过以上分析可以看出，《蛇》问题主要考察了线段树的基本插入、删除和查找操作，并结合了区间操作的特点，是一道很好的练习题。 综上所述，线段树作为一种高效的数据结构，不仅可以处理一维区间上的问题，还可以...
线段树是一种数据结构，常用于处理区间查询与更新的问题，它能高效地支持动态维护区间最值、求和等问题。在本题“POJ 3264”中，我们可能面临的是一个区间最值或者区间求和的计算任务。线段树的基本思想是将数组或...
9. **我的日程安排表 III**：这类问题可能涉及时间区间冲突检测，线段树可以帮助快速检查两个时间段是否有交集。 10. **掉落的方块**：对于这类动态规划问题，线段树可以用于优化状态转移，减少不必要的计算。 在...
线段树则是一种数据结构，主要用于高效地处理区间查询和更新操作。它可以快速回答关于区间最大值、最小值、求和等问题。线段树的基本思想是将一维数组划分为若干个重叠的子区间，并对每个子区间维护一个代表性的信息...
树链剖分的核心思想是将树拆分成多个链，这样就可以通过线段树等数据结构快速查询链上的信息。具体步骤如下： 1. **预处理：** 进行DFS遍历树，计算每个节点的深度以及每个节点的重儿子（即连接节点与其重儿子之间...
在这个模版中，线段树被用于处理更复杂的区间操作，例如成段更新。 3. **动态更新和查询**： ACM题目通常要求在给定的输入序列中进行动态更新和查询。在这个模版中，我们看到两种类型的命令：类型1是进行加法更新...
为了高效解决这类问题，我们可以考虑使用**线段树**或者**差分数组**来处理动态更新和查询操作。线段树是一种非常高效的解决区间问题的数据结构，它可以在`O(log n)`的时间复杂度内完成单点更新和区间查询操作。对于...
此外，书中还讲解了线段树的单点更新和区间更新，以及线段树的应用、字符串匹配问题和图的连通性问题，这些都是高级的数据结构和算法应用。 该攻略还通过N诺平台提供了配套的精讲视频资源，帮助考生更直观地理解...
- **特点**：线段树通过构建一棵覆盖了整个区间的树形结构，使得区间查询和更新操作都可以在 O(log n) 的时间内完成。 - **应用场景**：例如，查询某一区间的和、最小值或最大值等。 #### 七、字母树（Trie树） ...
压缩包内的“Line tree.docx”文件可能是包含线段树理论讲解、示例代码和练习题的文档。通过阅读这份文档，学习者可以深入理解线段树的工作原理，如何构建线段树，以及如何利用线段树解决实际问题。它还可能涵盖了...
树套树是一种基于线段树的数据结构，可以处理二维空间中的查询和更新问题。在本题中，可以将问题视为在一个二维平面上的染色问题，使用树套树来维护每个节点的状态，并根据查询需求进行相应的操作。这种方法的时间...
- 构建一棵线段树，每个节点表示一段区间 `[l, r)` 的和。 - 更新操作：找到覆盖这个元素的节点并更新。 - 查询操作：合并所有覆盖查询区间的节点的和。 #### 62. Unique Paths **知识点：** - **问题描述：**...
- **线段树**：用于处理区间查询和修改问题，常用于求区间最值、和等问题。 - **并查集**：处理集合的连接和查询是否连通的问题，路径压缩可以提高效率。 4. **其他算法**： - **点在多边形内的判断**：用于二维...
本题要求设计一种能够有效存储和检索像素点的四叉树结构，并支持多边形绘制。关键在于如何合理地将像素点分配到四叉树的节点上。 **扩展知识**: - 四叉树的每个内部节点有四个子节点，分别对应其所在区域的四个象限...