[ACM]线段树 线段树 Mayor's posters Balanced Lineup Can you answer these queries? 数列分块2
1____线段树概念
1.1____引入
有一类这样的问题 RMQ（ Range Minimum/Maximum Query ）问题，求区间最大值或最小值。设有长度为 (n) 的数列 {(a_1,a_2,...,a_n)} ，需要进行以下操作。
（1）求最值：给定 (i,j le n) 求 {(a_1,a_2,...,a_n)} 中的最值。
（2）修改元素：给定 k 和 x 把，(a_k) 改为 x 。
1.2____什么是线段树
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构，用完全二叉树来构造。
线段树可以在 (Theta (logN)) 的时间复杂度内实现单点修改、单点查询、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
1.3____线段树的表示
线段树是建立在线段（或区间）基础上的树，树的每个结点代表一条线段 ([L,R])。
我们一般用struct来存储线段树的结点（也可以用多个数组来模拟，看个人喜好）
const int N = 1e5 + 5;
strcut Node
{
int l,r;
int sum;
}Tree[N>>2];
- 线段树的会提前把所有的会用到的结点的内存提前分配好，通过建树来初始化每一个结点使得区间和输入数组相对应。
- (l，r) 表示此结点在在输入数组中所表示的区间，sum看问题而定，可以是区间和，区间最值等等。
- 叶子结点的 (l) 值与 (r) 值相等，表示输入数组的下标（从1开始，为的是方便计算左右儿子）在 (l) （或 (r)）处的元素值。
- 每个非叶子结点都代表某些相邻叶子结点的合并。
- 由于线段树用完全二叉树构造，一个结点的左右儿子结点不用存储，直接通过公式计算。
假如我们的输入数组为 { 1 , 3 , 5 , 7 , 9 , 11 }
在数组中的结构：
Tree[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, NULL, NULL, 7, 9, NULL, NULL}
1.4____线段树的空间计算
如果 (n) 是2的幂次方，那么就不会出现有结点为NULL的情况，也就是说没有空间的浪费。在此情况下，线段树的结点个数为2n-1，有n个叶子结点，以及n-1个内部结点（非叶子结点）。
（可以数一下图中的内部结点和叶子结点的个数）
如果 (n) 不是2的幂次方，那么线段树的结点个数为 2x-1 （x为第一个比 (n) 大的2的幂次方数），但是在我们做题的时候通常直接多乘个 (2) 就好了( T[N*4] || T[N>>2] )
1.5____关于取左右儿子的问题
在之前的树形结构中，我们都是用指针来指向左右儿子。由于线段树基于完全二叉树实现，这一特性，我们可以直接算出每个结点对应的左右儿子结点的坐标。通过坐标的随意存取访问在效率上肯定是比指针更高的，但是别忘了完全二叉树存在空间的浪费，所以各有各的好，我们选择在比赛中对我们更好的解决办法。
-
左儿子：rt * 2rt >> 1 -
右儿子：rt * 2 + 1rt >> 1|1这里用位运算，可以提升运行效率，
2____单点修改，单点查询，区间查询
2.1____建树
建树我们是通过从 ([1,n]) 开始，递归的把树建立起来（其过程有点像DFS）
后面的代码都是以求区间和为例
void push_up(int rt)
{
Tree[rt].sum = Tree[rt << 1].sum + Tree[rt << 1|1].sum
}
void build(int rt,int l,int r)
{
Tree[rt].l = l , Tree[rt].r = r;
if( l == r ){ /// 递归到了叶结点
Tree[rt].sum = A[r]; /// A为输入数组
return ;
}
int mid = l + r >> 1;
build( rt<<1 , l , mid );
build( rt<<1|1, mid + 1 , r );
push_up( rt );
}
2.2____单点更修改
单点修改的过程和建树的过程类似，其过程相当于在树上二分。
在更新 (a_i) 的值时，需要对包含 (i) 所有区间对应结点的值重新进行计算。在更新时，可以从下面的结点开始向上不断更新，把每个结点的值更新为左右两个儿子的值的和就好。
一般这个过程我们用push_up函数来解决，在建树的时候我们也会执行这个操作。
void update(int rt,int pos,int val)
{
if( Tree[rt].l == Tree[rt].r ){ /// 如果到了pos这个位置就更新
A[pos] +=val;
Tree[rt].sum +=val;
return ; /// 一定要return
}
int mid = ( Tree[rt].l + Tree[rt].r ) >> 1;
if( pos <= mid ) update( rt << 1,pos,val ); /// 注意思考什么时候是if-else，什么时候是if-if
else update( rt << 1|1, pos, val );
push_up(rt); /// 更新父结点
}
2.3____单点查询
单点查询和单点更新基本相同
int update(int rt,int pos)
{
if( Tree[rt].l == Tree[rt].r ){ /// 如果到了pos这个位置就更新
return Tree[rt].sum; /// 一定要return
}
int mid = ( Tree[rt].l + Tree[rt].r ) >> 1;
int res = 0;
if( pos <= mid ) res = update( rt << 1,pos ); /// 注意思考什么时候是if-else，什么时候是if-if
else res = update( rt << 1|1, pos );
return res;
}
2.4____区间查询
区间查询和我们单点查询在思想上有点不同，还记得我前面代码中的注释吗？
区别if-else 以及if-if ，我们在单点修改的时候，我们的搜索树只会遍历到一个结点的左结点或右结点。但是在区间修改中，a我们可能把一个结点的左右儿子都遍历了，因为我们要求的区间在多数情况下是无法直接取得的（也就是说没有一个结点直接代表我们要求的整个区间）。
所有通常情况下，我们求解的区间是很多个区间的叠加，这也是线段树最难的地方，在后面因为区间取值的问题，我们会有很多复杂的操作（人话就是做好心理准备）。
int update(int rt,int l,int r)
{
if( l <= Tree[rt].l && r >= Tree[rt].r ){ /// 如果到了pos这个位置就更新
return Tree[rt].sum; /// 一定要return
}
int mid = ( Tree[rt].l + Tree[rt].r ) >> 1;
int res = 0;
if( l <= mid ) res += update( rt << 1,l,r ); /// 注意思考什么时候是if-else，什么时候是if-if
if( r > mid ) res += update( rt << 1|1, l,r );
return res;
}
2.5____例题
例1
给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1 之间。
可以对这列数进行两种操作：
- 添加操作：向序列后添加一个数，序列长度变成 n+1；
- 询问操作：询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始，整数序列为空。
一共要对整数序列进行 m 次操作。
写一个程序，读入操作的序列，并输出询问操作的答案。
输入格式
第一行有两个正整数 m,p，意义如题目描述；
接下来 m 行，每一行表示一个操作。
如果该行的内容是
Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；如果是
A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。
输出格式
对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 L 个数的最大数。
数据范围
(1≤m≤2×10^5)
(1≤p≤2×10^9)
0≤t<p输入样例：
10 100 A 97 Q 1 Q 1 A 17 Q 2 A 63 Q 1 Q 1 Q 3 A 99输出样例：
97 97 97 60 60 97样例解释
最后的序列是 97,14,60,96
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct Node{
int l,r;
int sum;
}T[N<<2];
void push_up(int rt)
{
T[rt].sum = max(T[rt << 1].sum , T[rt << 1|1].sum);
}
void build(int rt,int l, int r)
{
T[rt] = {l,r,0};
if( T[rt].l == T[rt].r ){
return ;
}
int mid = (l + r) >> 1;
build(rt << 1,l,mid),build(rt <<1|1,mid+1,r);
push_up(rt);
}
void update(int rt,int pos,int val)
{
if( T[rt].l == T[rt].r && T[rt].r == pos ){
T[rt].sum = val;
return ;
}
int mid = ( T[rt].l + T[rt].r ) >>1;
if( pos <= mid ) update(rt <<1,pos,val);
else update(rt <<1|1,pos,val);
push_up(rt);
}
int query(int rt,int l,int r)
{
if( l <= T[rt].l && r >= T[rt].r ){
return T[rt].sum;
}
int mid = (T[rt].l + T[rt].r) >> 1;
int l_son = 0,r_son = 0;
if( l <= mid ) l_son = query(rt <<1,l,r);
if( r > mid ) r_son += query(rt <<1|1,l,r);
return max(l_son,r_son);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n,p,res = 0 ,cnt = 1;
cin >> n >> p;
build(1,1,n);
for(int i = 0; i < n ; i++){
char c;
int x;
cin>> c>>x;
if( c == 'A' ){
update(1,cnt++, (x+res)%p );
}else{
res = query( 1,cnt - x,cnt-1 );
cout <<res << "
";
}
}
return 0;
}
3____区间修改，Lazy标记
3.1____故事引入
如果要求修改区间 ([l,r]) ，把所有包含在区间 ([l,r]) 中的节点都遍历一次、修改一次，时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。
我们在线段树的 struct Node 中，新加一个lazy标记，表示此结点的懒惰标记值。
A 有两个儿子，一个是 B，一个是 C。
有一天 A 要建一个新房子，没钱。刚好过年嘛，有人要给 B 和 C 红包，两个红包的钱数相同都是 (1) 元，然而因为 A 是父亲所以红包肯定是先塞给 A 咯~
理论上来讲 A 应该把两个红包分别给 B 和 C，但是……缺钱嘛，A 就把红包偷偷收到自己口袋里了。
A 高兴地说：「我现在有 (2) 份红包了！我又多了 (2 imes1=2) 元了！哈哈哈~」
但是 A 知道，如果他不把红包给 B 和 C，那 B 和 C 肯定会不爽然后导致家庭矛盾最后崩溃，所以 A 对儿子 B 和 C 说：「我欠你们每人 (1) 份 (1) 元的红包，下次有新红包给过来的时候再给你们！这里我先做下记录……嗯……我欠你们各 (1) 元……」
儿子 B、C 有点恼怒：「可是如果有同学问起我们我们收到了多少红包咋办？你把我们的红包都收了，我们还怎么装？」
父亲 A 赶忙说：「有同学问起来我就会给你们的！我欠条都写好了不会不算话的！」
这样 B、C 才放了心。
在这个故事中我们不难看出，A 就是父节点，B 和 C 是 A 的子节点，而且 B 和 C 是叶子节点，分别对应一个数组中的值。
D表示的是区间的sum值，b表示区间的lazy标记，因为 A 区间是 B ，C区间的父节点，所有我在第一次加到 A 区间的时候，就把他所有的子节点的值都加上，并把值添加到lazy标记中。
所以 A 区间的 D 中的值为 (2 imes 1) ，我们lazy标记 b 的值还是为 (1)
如果这时候我们要查询区间 ([1,1])（即节点 B 的值），A 就把它欠的还给 B，此时的操作称为 下传懒惰标记。
3.2____push_down lazy 标记下传
void push_down(int rt)
{
/// 如果lazy标记非空，我们就把标记下传
if( Tree[rt].lazy != 0 ){
int mid = (Tree[rt].l + Tree[rt].r) >> 1;
/// 更新子节点
Tree[rt << 1].sum += Tree[rt].lazy * ( mid - Tree[rt].l + 1); /// 注意这后面的值
Tree[rt << 1 | 1].sum += Tree[rt].lazy * ( Tree[rt].r - mid) ; /// 注意这后面的值
/// 继续把标记下传
Tree[rt << 1].lazy += Tree[rt].lazy;
Tree[rt << 1|1].lazy += Treert].lazy;
/// 清空当前节点的lazy标记
Tree[rt].lazy = 0;
}
}
3.3____带lazy标记的，区间修改
void rangeUpdate(int rt, int l,int r,int val)
{
if( l <= Tree[rt].l && r >= Tree[rt].r ){
Tree[rt].sum += val * (Tree[rt].r - Tree[rt].l + 1); /// 把所有的区间中的值都先修改
Tree[rt].lazy += val;
return ;
}
int mid = ( Tree[rt].l + Tree[rt].r ) >> 1;
push_down(rt); /// 标记下传
if( l <= mid ) rangeUpdate( rt << 1,l,r,val );
if( r > mid ) rangeUpdate( rt << 1|1,l,r,val );
push_up(rt); /// 区间值上传
}
3.4____带标记下传的区间查询
ll rangeQuery(int rt,int l ,int r)
{
if( l <= Tree[rt].l && r >= Tree[rt].r ){
return Tree[rt].sum;
}
ll mid = ( Tree[rt].l + Tree[rt].r ) >> 1;
push_down(rt); /// 标记下传
ll son = 0;
if( l <= mid ) son += rangeQuery(rt << 1,l,r); /// 查询左儿子
if( r > mid ) son += rangeQuery(rt << 1|1,l,r); /// 查询右儿子
push_up(rt);
return son;
}
3.5____例题
A Simple Problem with Integers - POJ 3468
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4Sample Output
4 55 9 15
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll a[N];
struct Node
{
ll l ,r;
ll sum;
ll lazy;
}T[N<<2];
void push_up(int rt)
{
T[rt].sum = T[rt << 1].sum + T[rt << 1|1].sum;
}
void push_down(int rt)
{
if( T[rt].lazy != 0 ){
int mid = (T[rt].l + T[rt].r) >> 1;
T[rt << 1].sum += T[rt].lazy * ( mid - T[rt].l + 1);
T[rt << 1 | 1].sum += T[rt].lazy * ( T[rt].r - mid) ;
T[rt << 1].lazy += T[rt].lazy;
T[rt << 1|1].lazy += T[rt].lazy;
T[rt].lazy = 0;
}
}
void build(int rt,int l,int r)
{
T[rt] = {l,r,0,0};
if( l == r ){
T[rt].sum = a[l];
return ;
}
int mid = (l + r) >> 1;
build(rt<<1,l,mid),build(rt <<1|1,mid+1,r);
push_up(rt);
}
void rangeUpdate(int rt, int l,int r,int val)
{
if( l <= T[rt].l && r >= T[rt].r ){
T[rt].sum += val * (T[rt].r - T[rt].l + 1);
T[rt].lazy += val;
return ;
}
int mid = ( T[rt].l + T[rt].r ) >> 1;
push_down(rt);
if( l <= mid ) rangeUpdate( rt << 1,l,r,val );
if( r > mid ) rangeUpdate( rt << 1|1,l,r,val );
push_up(rt);
}
ll rangeQuery(int rt,int l ,int r)
{
if( l <= T[rt].l && r >= T[rt].r ){
return T[rt].sum;
}
ll mid = ( T[rt].l + T[rt].r ) >> 1;
push_down(rt);
ll son = 0;
if( l <= mid ) son += rangeQuery(rt << 1,l,r);
if( r > mid ) son += rangeQuery(rt << 1|1,l,r);
push_up(rt);
return son;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
build(1,1,n);
for(int i = 0 ; i < m ; i++ ){
char op ;
ll x,y,z;
cin >> op;
if( op == 'C' ){
cin >> x >> y >> z;
rangeUpdate(1,x,y,z);
}else{
cin >> x >> y;
cout << rangeQuery(1,x,y) << "
";
}
}
return 0;
}
4____习题
Mayor's posters
AB市，字节城的市民无法忍受在市长竞选活动中，候选人随心所欲的在各处张贴选举海报。所以字节城的市民最终决定建立一个选民墙来介绍这些信息，规则如下：
每个候选人都可以在墙上贴一张海报。
每张海报高度和这个选民墙的高度一致；宽度可以是任意的整数字节（字节是整个城市的长度单位）。
这个信息墙被分成几段，每段的宽度是一个字节。
每张海报必须完全覆盖连续的墙段。
字节城的市民建立了一个长度为 $ 1e7$ 的选民墙（如此就有足够的空间给候选人来张贴自己的海报）。当竞选活动重新开始时，候选人在墙上张贴自己的海报，海报与海报之间的宽度相差很大。此外，候选人开始把他们的海报张贴在已经被其他海报占据的墙上。字节城的每个人都很好奇，在选举的最后一天，谁的海报会被看到(全部或部分)。
你的任务是计数到最后有多少张海报可以被看到。
#include <set>
#include <algorithm>
#include <iostream>
#include <vector>
#define ls rt << 1
#define rs rt << 1|1
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Node
{
int l,r;
int tp;
int lazy;
}T[N << 2];
inline void push_down(int rt)
{
if( T[rt].lazy != 0 ){
T[ls].tp = T[rt].lazy;
T[ls].lazy = T[rt].lazy;
T[rs].tp = T[rt].lazy;
T[rs].lazy = T[rt].lazy;
T[rt].lazy = 0;
}
}
inline void push_up(int rt)
{
if( T[ls].tp != T[rs].tp ) T[rt].tp = INF;
else T[rt].tp = T[ls].tp;
}
void build(int rt,int l,int r)
{
T[rt] = {l,r,0,0};
if( l == r ){
return;
}
int mid = (l + r) >> 1;
build(ls,l,mid),build(rs,mid+1,r);
}
inline void rangeUpdate(int rt,int l,int r,int val)
{
if( l <= T[rt].l && r >= T[rt].r ){
T[rt].tp = val;
T[rt].lazy = val;
return ;
}
int mid = (T[rt].l + T[rt].r) >>1;
push_down(rt);
if( l <= mid ) rangeUpdate( ls,l,r,val );
if( r > mid ) rangeUpdate( rs,l,r,val );
push_up(rt);
}
inline int getTpye(int rt,int pos)
{
if( T[rt].l == T[rt].r && T[rt].l == pos ){
return T[rt].tp;
}
int mid = ( T[rt].l + T[rt].r ) >>1;
int son = 0;
push_down(rt);
if(pos <= mid) son = getTpye( ls,pos );
else son = getTpye(rs,pos);
return son;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int k;
cin >> k;
while(k--){
int n;
cin >> n;
///离散化
vector<pair<int,int> > a(n);
vector<int> ans;
for(int i = 0; i < n ; i ++){
cin >> a[i].first >> a[i].second;
ans.push_back(a[i].first);
ans.push_back(a[i].second);
}
sort(ans.begin(),ans.end());
ans.erase( unique(ans.begin(),ans.end()),ans.end() );
int len = ans.size();
for(int i = 1 ; i < len; i ++){
if( ans[i] - ans[i-1] > 1 ){
ans.push_back( ans[i-1] + 1 );
}
}
sort(ans.begin(),ans.end());
// for(int i = 0 ; i < ans.size() ; i++ ){
// cout << ans[i] << "
"[i == ans.size()];
// }
build(1,1,ans.size());
/// 贴海报
len = a.size();
for(int i =0 ; i < len ; i++){
int x = lower_bound(ans.begin(), ans.end() , a[i].first) - ans.begin() + 1;
int y = lower_bound(ans.begin(), ans.end() , a[i].second) - ans.begin() + 1;
rangeUpdate( 1,x,y,i+1 );
}
//cout <<endl;
len = ans.size();
set<int> se;
for(int i = 1 ; i <= len ; i++ ){
int te = getTpye(1,i);
se.insert( te );
}
se.erase(0);
cout <<se.size() <<endl;
}
return 0;
}
Balanced Lineup
在日常的挤奶任务中，John的 N 头牛总是排成一条线，并且顺序不会改变。一天，John决定和一些奶牛组织一场极限飞盘游戏。为了方便，他会选择在牛群中连续的一群牛来玩这个游戏。然而为了让所有的牛都能愉快的玩耍，所选的牛之间的升高差距不能太大。
他需要你的帮助来确定这群牛中最矮和最高的牛之间的身高差异。
维护区间最大值，最小值
Can you answer these queries?
数列分块2
#include <bits/stdc++.h>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define Mid ((T[rt].l + T[rt].r)>>1)
#define L ( T[rt].l)
#define R (T[rt].r)
using namespace std;
const int N = 5e4+10;
void file()
{
#ifdef ONLINE_JUDGE
#else
freopen( "d:/workProgram/test.in","r",stdin );
#endif
}
struct Node
{
int l,r;
int ma,mi;
int lazy ;
}T[N << 2];
int a[N];
void up(int rt)
{
T[rt].ma = max( T[ls].ma, T[rs].ma );
T[rt].mi = min( T[ls].mi , T[rs].mi );
}
void down(int rt)
{
if( T[rt].lazy != 0 ){
T[ls].lazy += T[rt].lazy;
T[rs].lazy += T[rt].lazy;
T[ls].ma += T[rt].lazy;
T[rs].ma += T[rt].lazy;
T[ls].mi += T[rt].lazy;
T[rs].mi += T[rt].lazy;
T[rt].lazy = 0;
}
}
void build(int rt,int l ,int r)
{
T[rt] = {l,r,0,0,0};
if( l == r){
T[rt].ma = T[rt].mi = a[l];
return ;
}
int mid = (l + r) >> 1;
build(ls,l,mid),build(rs,mid+1,r);
up(rt);
}
void rangeUpdate(int rt,int l,int r,int val)
{
if( l <= L && r >= R ){
T[rt].ma += val;
T[rt].mi += val;
T[rt].lazy += val;
return ;
}
down(rt);
if( l <= Mid ) rangeUpdate( ls, l,r,val );
if( r > Mid ) rangeUpdate(rs,l,r,val);
up(rt);
}
int rangeQuery(int rt,int l,int r,int x)
{
if( T[rt].mi >= x ) return 0;
if( l <= L && r >= R && T[rt].ma < x ){
return T[rt].r - T[rt].l + 1;
}
down(rt);
int cnt = 0;
if( l <= Mid ) cnt += rangeQuery(ls,l,r,x);
if( r > Mid ) cnt += rangeQuery(rs,l,r,x);
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
//file();
int n;
cin >> n;
for(int i = 1 ; i <= n ; i++){
cin >> a[i];
}
build(1,1,n);
for(int i = 0; i < n ; i++){
int op,l,r,x;
cin >> op >> l >> r >>x;
//cout << "--"<< i <<endl;
if( op == 0 ){
rangeUpdate(1,l,r,x);
}else{
cout <<rangeQuery(1,l,r,x*x) <<endl;
}
}
//system("pause");
return 0;
}