[数据结构与算法]线段树的一些基础应用

线段树基础应用

线段树

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?10^4)$个房间,有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?10^5)$ 个矩形，以及n个矩形的四个顶点坐标$(0?x,y?10^9)$，求这n个矩形面积的并。

2. 题目思路：

1.首先想到暴力for求出，但看到数据范围显然MLE + TLE。

2.再想到利用容斥定理先求出所有矩形面积之和再减去重叠部分，但过于麻烦。

那么应该怎么处理这个问题呢，可以想到分割图形求解，如同往一个盒子里灌水求体积一样，用一个数据结构来模拟逐渐上升的线，然后利用截线段长度乘上升的高度就可以得到部分的面积。显然，最佳的分割方式是每次遇到一条横边做为分割处。

3.考虑到矩形顶点可以到1e9则用离散化处理，此时问题变为了求某一段区间有线的长度（因为上升高度可以直接得出）随着截线的上升有线长度也会相应变化，既然问题涉及到了区间求解，则可以使用线段树来维护，以x轴作为区间，建一颗线段树，线段树节点保存节点对应的左右区间内被矩形覆盖的区域有多长。则问题可以得到解决。

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

int 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;
}

可持续化线段树