线段树的一些基础应用"/>
线段树的一些基础应用
线段树基础应用
线段树
luoguP3373 线段树2
1.题目大意：
给定一个源数组，要求你实现区间加，区间乘，区间查询的功能。
2.题目思路：
一眼线段树（名字也是如此）但与最基本的线段树区别在于，这里需要多实现一个区间乘的操作，看起来只是多了一个新功能，但由此引出了一系列的问题：
1.首先一定想到的是lazytag的push_down问题，显然这里lazy不能初始化为0而是为1再者lazy也需要乘来修改。
2.既然想到了lazy，那么有一个更复杂的问题是一定难以绕过的，在这颗线段树中我们有两个操作，分别是加和乘，而因为这两种操作的结果会互相影响，所以在传递lazy的时候也会有两种的规则，
第一加法优先即tr[p << 1]=((tr[p << 1] + lazya[p]) * lazym[p])%pmod这时会发现，修改加法的lazy时乘法会被连带修改成小数，不仅麻烦还会产生精度问题，这是我们不希望看到的，所以要舍弃。
第二乘法优先即tr[p << 1] = ((tr[p << 1] * lazym[p]) + lazya[p] * len) % mod这时如果乘法修改只要同时乘加法的lazy，而加法时就只用修改加法lazy，不会产生小数也不会有精度问题。
解决了上面的问题，这个线段树就和普通的线段树没有什么区别了。下面是代码.
#### AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int MAX = 1e5 + 10;long long t[MAX << 2];
long long la[MAX << 2];
long long lam[MAX << 2];
int n, m, mod;inline int lson(int x){return x << 1;
}inline int rson(int x){return lson(x) | 1;
}void push_up(int p){t[p] = (t[lson(p)] + t[rson(p)]) % mod;
}void build(int p, int s, int e){//个人喜欢用这种方式建树，即节点只保存值而不保存区间左右界if(s == e){scanf("%lld", &t[p]);return;}int mid = s + ((e - s) >> 1);build(lson(p), s, mid);build(rson(p), mid + 1, e);push_up(p);
}void push_down(int p, int s, int e){if(la[p] == 0 && lam[p] == 1){return;}long long& lazy = la[p];long long& lazym = lam[p];int mid = s + ((e - s) >> 1);int ls = lson(p);int rs = rson(p);t[ls] = (t[ls] * lazym + lazy * (mid - s + 1)) % mod;t[rs] = (t[rs] * lazym + lazy * (e - mid)) % mod;la[ls] = (la[ls] * lazym + lazy) % mod;la[rs] = (la[rs] * lazym + lazy) % mod;lam[ls] = (lam[ls] * lazym) % mod;lam[rs] = (lam[rs] * lazym) % mod;lazy = 0;lazym = 1;
}long long query(int p, int s, int e, int l, int r){if(l <= s && e <= r){return t[p] % mod;}push_down(p, s, e);int mid = s + ((e - s) >> 1);long long ret = 0;if(l <= mid){ret = (ret + query(lson(p), s, mid, l, r)) % mod;}if(r > mid){ret = (ret + query(rson(p), mid + 1, e, l, r)) % mod;}return ret;
}void modifya(int p, int s, int e, int l, int r, int d){if(l <= s && e <= r){t[p] = (t[p] + d * (e - s + 1)) % mod;la[p] = (la[p] + d) % mod;return;}push_down(p, s, e);int mid = s + ((e - s) >> 1);if(l <= mid){modifya(lson(p), s, mid, l, r, d);}if(r > mid){modifya(rson(p), mid + 1, e, l , r, d);}push_up(p);
}void modifym(int p, int s, int e, int l, int r, int k){if(l <= s && e <= r){t[p] = (t[p] * k) % mod;la[p] = (la[p] * k) % mod;lam[p] = (lam[p] * k) % mod;return;}push_down(p, s, e);int mid = s + ((e - s) >> 1);if(l <= mid){modifym(lson(p), s, mid, l, r, k);}if(r > mid){modifym(rson(p), mid + 1, e, l, r, k);}push_up(p);
}void slove(int j){if(1 == j){int l, r, k;scanf("%d%d%d", &l, &r, &k);modifym(1, 1, n, l, r, k);}else if(2 == j){int l, r, d;scanf("%d%d%d", &l, &r, &d);modifya(1, 1, n, l, r, d);}else if(3 == j){int l, r;scanf("%d%d", &l, &r);long long ans = query(1, 1, n, l, r);printf("%lld\n", ans);}
}void Init(){build(1, 1, n);fill(lam, lam + n * 4 + 1, 1);
}int main(){// freopen("out.txt","w",stdout);scanf("%d%d%d", &n, &m, &mod);Init();while(m--){int me = 0;scanf("%d", &me);slove(me);}return 0;
}
线段树区间合并
luoguP2894 Hotel G
1.题目大意：
现在有n ( 1 ⩽ n ⩽ 5 ∗ 1 0 4 ) (1 \leqslant n \leqslant 5 * 10^4) (1⩽n⩽5∗104)个房间,有m个操作，接下来m行有先输入一个数。如果这个数为1，则再输入一个数x代表在1–n的区间内找到长度连续为x的空房，如果找到了就使其入住并输出左端点，如果找到多个则入住输出最小的。如果这个数为2，则在输入两个数x，y代表将x–x+y+1的房间退房。
2.题目思路：
对于这个问题，因为涉及到区间修改问题，考虑用线段树完成，第二个操作的实现很简单，就是区间赋值为0，但第一个问题，普通的线段树似乎难以解决，因为线段树并不能知道区间内空房的具体情况，考虑这样一种情况，对于两个相邻的区间，左区间连续空房为m，右区间连续空房为n，但并不能直接判断父区间的值为两个子区间的大者，因为在合并时左区间右边与右区间左边可能产生新的连续空房，且大于m或n。
解决这个问题也很简单，就是对于每一个节点额外记录左右区间的连续空房量，并且在push_up和push_down的时候按照一定方法即可
void push_up(int x){if(tr[lson(x)].len == tr[lson(x)].num){tr[x].numl = tr[lson(x)].num + tr[rson(x)].numl;}else{tr[x].numl = tr[lson(x)].numl;}if(tr[rson(x)].len == tr[rson(x)].num){tr[x].numr = tr[lson(x)].numr + tr[rson(x)].num;}else{tr[x].numr = tr[rson(x)].numr;}tr[x].num = max(tr[lson(x)].num, max(tr[rson(x)].num, tr[lson(x)].numr + tr[rson(x)].numl));
}
push_up的写法
void push_down(int p, int s, int e){if(tr[p].lazy == 0) return;int& la = tr[p].lazy;if(1 == la){int son = lson(p);tr[son].num = tr[son].numl = tr[son].numr = 0;tr[son].lazy = 1;son = rson(p);tr[son].num = tr[son].numl = tr[son].numr = 0;tr[son].lazy = 1;} if(2 == la){int son = lson(p);tr[son].num = tr[son].numl = tr[son].numr = tr[son].len;tr[son].lazy = 2;son = rson(p);tr[son].num = tr[son].numl = tr[son].numr = tr[son].len;tr[son].lazy = 2;}la = 0;
}
push_down的写法
3.AC代码：
#include <cstdio>
#include <iostream>
#include <assert.h>using namespace std;const int MAX = 5e4 + 10;int n, m;struct segt{int len;//节点代表区间的长度int num;//节点代表区间的最大连续空房数int numl;//以左端点为起点的连续空房数int numr;//以右端点为起点的连续空房数int lazy;//0代表无变化，1代表定房，2代表退房
} tr[MAX << 2];inline int lson(int x){return x << 1;
}inline int rson(int x){return lson(x) | 1;
}void push_up(int x){if(tr[lson(x)].len == tr[lson(x)].num){tr[x].numl = tr[lson(x)].num + tr[rson(x)].numl;}else{tr[x].numl = tr[lson(x)].numl;}if(tr[rson(x)].len == tr[rson(x)].num){tr[x].numr = tr[lson(x)].numr + tr[rson(x)].num;}else{tr[x].numr = tr[rson(x)].numr;}tr[x].num = max(tr[lson(x)].num, max(tr[rson(x)].num, tr[lson(x)].numr + tr[rson(x)].numl));
}void build(int p, int s, int e){tr[p].len = e - s + 1;if(s == e){tr[p].num = tr[p].numl = tr[p].numr = 1;tr[p].lazy = 0;return;}int mid = s + ((e - s) >> 1);build(lson(p), s, mid);build(rson(p), mid + 1, e);push_up(p);
}void push_down(int p, int s, int e){if(tr[p].lazy == 0) return;int& la = tr[p].lazy;if(1 == la){int son = lson(p);tr[son].num = tr[son].numl = tr[son].numr = 0;tr[son].lazy = 1;son = rson(p);tr[son].num = tr[son].numl = tr[son].numr = 0;tr[son].lazy = 1;} if(2 == la){int son = lson(p);tr[son].num = tr[son].numl = tr[son].numr = tr[son].len;tr[son].lazy = 2;son = rson(p);tr[son].num = tr[son].numl = tr[son].numr = tr[son].len;tr[son].lazy = 2;}la = 0;
}int query(int p, int s, int e, int x){if(s == e) return s;int mid = s + ((e - s) >> 1);push_down(p, s, e);if(tr[lson(p)].num >= x) return query(lson(p), s, mid, x);if(tr[lson(p)].numr + tr[rson(p)].numl >= x) return mid - tr[lson(p)].numr + 1;if(tr[rson(p)].num >= x) return query(rson(p),mid + 1, e, x);return 0;
}void checkin(int p, int s, int e, int l, int r){if(s >= l && e <= r){tr[p].num = tr[p].numl = tr[p].numr = 0;tr[p].lazy = 1;return;}push_down(p, s, e);int mid = s + ((e - s) >> 1);if(l <= mid) checkin(lson(p), s, mid, l, r);if(r > mid) checkin(rson(p), mid + 1, e, l, r);push_up(p);
}void checkout(int p, int s, int e, int l, int r){if(s >= l && e <= r){// printf("p = %d s = %d e = %d l = %d r = %d\n",p, s, e, l, r);tr[p].num = tr[p].numl = tr[p].numr = tr[p].len;tr[p].lazy = 2;return;}push_down(p, s, e);int mid = s + ((e - s) >> 1);if(l <= mid) checkout(lson(p), s, mid, l, r);if(r > mid) checkout(rson(p), mid + 1, e, l, r);push_up(p);
}int query_all(int p, int s, int e, int l, int r){if(s >= l && e <= r){return tr[p].num;}push_down(p, s, e);int ret = 0;int mid = s + ((e - s) >> 1);if(l <= mid) ret += query_all(lson(p), s, mid, l, r);if(r > mid) ret += query_all(rson(p), mid + 1, e, l, r);return ret;
}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;build(1, 1, n);for(int i = 1; i <= m; i++){int op;cin>>op;if(1 == op){int x;cin>>x;int l = query(1, 1, n, x);cout<<l<<endl;// cout<<query_all(1, 1, n, 2, 5)<<endl;if(l == 0) continue;checkin(1, 1, n, l, l + x - 1);}else if(2 == op){int x, y;cin>>x>>y;checkout(1, 1, n, x, x + y - 1);// cout<<query_all(1, 1, n, 3, 5)<<endl;}else{assert(op != 1 && op != 2);}}return 0;
}
权值线段树
线段树扫描线
luoguP5490（模板）
1. 题目大意：
给定n ( 1 ⩽ n ⩽ 1 0 5 ) (1 \leqslant n \leqslant 10^{5}) (1⩽n⩽105) 个矩形，以及n个矩形的四个顶点坐标 ( 0 ⩽ x , y ⩽ 1 0 9 ) (0 \leqslant x, y\leqslant 10^{9}) (0⩽x,y⩽109)，求这n个矩形面积的并。
2. 题目思路：
1.首先想到暴力for求出，但看到数据范围显然MLE + TLE。
2.再想到利用容斥定理先求出所有矩形面积之和再减去重叠部分，但过于麻烦。
那么应该怎么处理这个问题呢，可以想到分割图形求解，如同往一个盒子里灌水求体积一样，用一个数据结构来模拟逐渐上升的线，然后利用截线段长度乘上升的高度就可以得到部分的面积。显然，最佳的分割方式是每次遇到一条横边做为分割处。
3.考虑到矩形顶点可以到1e9则用离散化处理，此时问题变为了求某一段区间有线的长度（因为上升高度可以直接得出）随着截线的上升有线长度也会相应变化，既然问题涉及到了区间求解，则可以使用线段树来维护，以x轴作为区间，建一颗线段树，线段树节点保存节点对应的左右区间内被矩形覆盖的区域有多长。则问题可以得到解决。
AC代码：
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;#define int long longint N;const int MAX = 1e6 + 10;//需要开大一点，不然访问叶子节点的时候可能会re。struct scan_line{//扫描线int l, r, h;//记录每一条横边的左右端点（长度）以及高度。int isdown;//记录是上边还是下边，上1下-1；bool operator < (const scan_line&rhs)const{return h < rhs.h;}
}line[MAX << 1];int xx[MAX << 1];struct segt{int l ,r;int cover;//cover代表这个节点代表的线段是不是被完全覆盖；int len; //len代表节点所包含覆盖覆盖区域的长度；
} t[MAX << 3];//最多有2n个区间，所以要开8倍大小；int xx1, xx2, yy1, yy2;inline int lson(int x){return x << 1;
}inline int rson(int x){return lson(x) | 1;
}void push_up(int x){int l = t[x].l, r = t[x].r;if(t[x].cover) t[x].len = xx[r + 1] - xx[l];else t[x].len = t[lson(x)].len + t[rson(x)].len;// cout<<t[x].len<<endl;
}void build(int p, int s, int e){t[p].l = s, t[p].r = e;t[p].len = 0,t[p].cover = 0;if(s == e) return;int mid = s + ((e - s) >> 1);build(lson(p), s, mid);build(rson(p), mid + 1, e);
}void up_loud(int p, int l, int r, int d){int s = t[p].l, e = t[p].r;if(xx[e + 1] <= l || xx[s] >= r) return;if(xx[e + 1] <= r && xx[s] >= l){t[p].cover += d;push_up(p);return;}// printf("hrhr\n");up_loud(lson(p), l, r, d);up_loud(rson(p), l, r, d);push_up(p);
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>N;for(int i = 1; i <= N; i++){cin>>xx1>>yy1>>xx2>>yy2;xx[(i << 1) - 1] = xx1, xx[i << 1] = xx2;line[(i << 1) - 1] = scan_line{xx1, xx2, yy1, 1};line[i << 1] = scan_line{xx1,xx2,yy2, -1};}sort(line + 1, line + (N << 1) + 1);sort(xx + 1, xx + (N << 1) + 1);// for(int i = 1; i <= (N << 1); i++){// printf("x1 = %d x2 = %d, y = %d isdown = %d\n",line[i].l,line[i].r,line[i].h,line[i].isdown);// }int len = unique(xx + 1, xx + (N << 1) + 1) - xx - 1;build(1, 1, len - 1);long long ans = 0;for(int i = 1; i < (N << 1); i++){up_loud(1, line[i].l,line[i].r,line[i].isdown);ans += (line[i + 1].h - line[i].h) * t[1].len;}cout<<ans<<endl;return 0;
}
可持续化线段树
luogu P3919可持久化线段树1
题目大意：
对于一个给定的数组，要求实现单点修改和查询历史版本的操作，每一次操作形成一个新的版本。
大致思路：
可持久化线段树，考虑对于每一次修改被改变的路不去修改原值二十新建一条路去表示修改之后的路，每一次增加logn个节点，显然这样操作之后根节点的数目会超过一个，所以额外用一个数组来储存根节点，根节点也就表示版本号，修改和查询复杂度为nlogn。
struct node{int l, r, val;
} tr[MAX << 5];
使用的结构体，因为需要新建节点所以不能再使用左移一位及的方式去代表左右儿子，所以用一个变量来记录左右儿子信息
inline int clone(int p){//新建节点保存被修改的值top++;tr[top] = tr[p];return top;
}
建树操作
int build(int p, int s, int e){//建树操作，与普通线段树不同的是需要返回节点编号p = ++top;//top表示当前总节点数量if(s == e){tr[p].val = num[s];return top;}int mid = s + ((e - s) >> 1);tr[p].l = build(tr[p].l, s, mid);tr[p].r = build(tr[p].r, mid + 1, e);return p;
}
修改操作
int modify(int p, int s, int e, int pos, int nval){p = clone(p);//涉及就要修改需要新建节点if(s == e){tr[p].val = nval;return p;}int mid = s + ((e - s) >> 1);if(pos <= mid)tr[p].l = modify(tr[p].l, s, mid, pos, nval);else tr[p].r = modify(tr[p].r, mid + 1, e, pos, nval);//因为是单点修改所以可以直接elsereturn p;
}
查询操作
int query(int p, int s, int e, int pos){if(s == e){return tr[p].val;}int mid = s + ((e - s) >> 1);if(pos <= mid) return query(tr[p].l, s, mid, pos);else return query(tr[p].r, mid + 1, e, pos);
}
main函数，存根，修改的方式
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;rep(i, n){cin>>num[i];}root[0] = build(0, 1, n);rep(i, m){int ver, op, pos, value;cin>>ver>>op>>pos;if(op == 1){cin>>value;root[i] = modify(root[ver], 1, n, pos, value);//因为修改会返回被修改节点的编号，递归出来后也就是新根节点的编号，所以直接让第i个根等于第i次修改的返回值即可}else{cout<<query(root[ver], 1, n, pos)<<endl;root[i] = root[ver];//题目描述查询需要新建一个完全一样的版本，但为此去建边实在浪费于是直接让第i次查询产生的根节点等于其查询的历史版本即可}}return 0;
}
AC代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <functional>
#include <map>
#include <queue>
#include <vector>
#include <utility>#define ed end()
#define bg begin()
#define mp make_pair
#define pb push_back
#define all(x) x.bg,x.ed
#define newline puts("")
#define si(x) ((int)x.size())
#define rep(i,n) for(int i = 1; i <= n; ++i)
#define rrep(i,n) for(int i = 0; i < n; ++i)
#define srep(i,s,t) for(int i = s; i <= t; ++i)
#define drep(i,s,t) for(int i = t; i >= s; --i)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int MAX = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const ll INF_ll = 1ll*INF*INF;
const int MOD = 1e9 + 7;
const double eps = 1e-7;struct node{int l, r, val;
} tr[MAX << 5];int n, m;
int top;
int num[MAX];
int root[MAX];inline int clone(int p){top++;tr[top] = tr[p];return top;
}int build(int p, int s, int e){p = ++top;if(s == e){tr[p].val = num[s];return top;}int mid = s + ((e - s) >> 1);tr[p].l = build(tr[p].l, s, mid);tr[p].r = build(tr[p].r, mid + 1, e);return p;
}int modify(int p, int s, int e, int pos, int nval){p = clone(p);if(s == e){tr[p].val = nval;return p;}int mid = s + ((e - s) >> 1);if(pos <= mid)tr[p].l = modify(tr[p].l, s, mid, pos, nval);else tr[p].r = modify(tr[p].r, mid + 1, e, pos, nval);return p;
}int query(int p, int s, int e, int pos){if(s == e){return tr[p].val;}int mid = s + ((e - s) >> 1);if(pos <= mid) return query(tr[p].l, s, mid, pos);else return query(tr[p].r, mid + 1, e, pos);
}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;rep(i, n){cin>>num[i];}root[0] = build(0, 1, n);rep(i, m){int ver, op, pos, value;cin>>ver>>op>>pos;if(op == 1){cin>>value;root[i] = modify(root[ver], 1, n, pos, value);}else{cout<<query(root[ver], 1, n, pos)<<endl;root[i] = root[ver];}}return 0;
}
更多推荐
线段树的一些基础应用
发布评论