洛谷官方题单--线段树

· 浏览次数 : 7

小编点评

前言发现线段树根本不会写，所以想要完成洛谷官方题单来稍微提升一下... 持续更新ing P3870 [TJOI2009] 开关明确了写线段树要思考的几个点： 1. 如何update，即如何合并子节点的信息，这里就是直接将子节点的灯的数量相加即可 2. 如何modify，即如何根据tag修改该节点的值，这里就是节点长度-灯的数量就行，还有如何下传tag，这里直接^就行神奇的代码 ```cpp #include #include #include #include #include #include #include #include using namespace std; #define endl '\' typedef long long LL; typedef unsigned long long ULL; typedef pair PII; const int INF = 0x3f3f3f3f; const int N = 1e5 + 10; struct Node { int add; int x; } seg[N * 4]; Node operator+(const Node &a, const Node &b) { Node c; c.x = a.x + b.x; return c; } void settag(int u, int l, int r, int add) { if (add == 1) { int len = r - l + 1; seg[u].x = len - seg[u].x; seg[u].add ^= add; } } void pushdown(int u, int l, int r) { int mid = l + r >> 1; settag(u * 2, l, mid, seg[u].add); settag(u * 2 + 1, mid + 1, r, seg[u].add); seg[u].add = 0; } void update(int u) { seg[u].x = seg[u * 2].x + seg[u * 2 + 1].x; } void modify(int u, int l, int r, int ql, int qr, int add) { assert(l <= ql and qr <= r); if (l == ql and r == qr) { settag(u, l, r, add); } else { pushdown(u, l, r); int mid = l + r >> 1; if (qr <= mid) modify(u * 2, l, mid, ql, qr, add); else if (ql >= mid + 1) modify(u * 2 + 1, mid + 1, r, ql, qr, add); else { modify(u * 2, l, mid, ql, mid, add); modify(u * 2 + 1, mid + 1, r, mid + 1, qr, add); } update(u); } } Node query(int u, int l, int r, int ql, int qr) { assert(l <= ql and qr <= r); if (l == ql and r == qr) return seg[u]; else { pushdown(u, l, r); int mid = l + r >> 1; if (qr <= mid) return query(u * 2, l, mid, ql, qr); else if (ql >= mid + 1) return query(u * 2 + 1, mid + 1, r, ql, qr); else { auto L = query(u * 2, l, mid, ql, mid); auto R = query(u * 2 + 1, mid + 1, r, mid + 1, qr); Node res = L + R; return res; } } update(u); } void solve() { int n, m; cin >> n >> m; while (m--) { int c, a, b; cin >> c >> a >> b; if (c == 0) { modify(1, 1, n, a, b, 1); } else { cout<< query(1, 1, n, a, b).x<< endl; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) { solve(); } return 0; } ``` P1438 无聊的数列区间加等差数列，单点求和直接转化为差分，区间加就行用树状数组也能做神奇的代码 ```cpp #include #include #include #include #include #include #include #include using namespace std; #define endl '\' typedef long long LL; typedef unsigned long long ULL; typedef pair PII; const int INF = 0x3f3f3f3f; const int N = 1e5 + 10; LL a[N], b[N]; struct Node { LL add; LL x; } seg[N * 4]; void update(int u) { seg[u].x = seg[u * 2].x + seg[u * 2 + 1].x; } void build(int u, int l, int r) { assert(l <= r); if (l == r) seg[u].x = b[l]; else { int mid = l + r >> 1; build(u * 2, l, mid); build(u * 2 + 1, mid + 1, r); update(u); } } void settag(int u, int l, int r, LL add) { int len = r - l + 1; seg[u].x += len * add; seg[u].add += add; } void pushdown(int u, int l, int r) { int mid = l + r >> 1; settag(u * 2, l, mid, seg[u].add); settag(u * 2 + 1, mid + 1, r, seg[u].add); seg[u].add = 0; } void modify(int u, int l, int r, int ql, int qr, LL add) { assert(l <= ql and qr <= r); if (l == ql and r == qr) { settag(u, l, r, add); } else { pushdown(u, l, r); int mid = l + r >> 1; if (qr <= mid) modify(u * 2, l, mid, ql, qr, add); else if (ql >= mid + 1) modify(u * 2 + 1, mid + 1, r, ql, qr, add); else { modify(u * 2, l, mid, ql, mid, add); modify(u * 2 + 1, mid + 1, r, mid + 1, qr, add); } update(u); } } Node query(int u, int l, int r, int ql, int qr) { assert(l <= ql and qr <= r); if (l == ql and r == qr) return seg[u]; else { pushdown(u, l, r); int mid = l + r >> 1; if (qr <= mid) return query(u * 2, l, mid, ql, qr); else if (ql >= mid + 1) return query(u * 2 + 1, mid + 1, r, ql, qr); else { Node res; auto L = query(u * 2, l, mid, ql, mid); auto R = query(u * 2 + 1, mid + 1, r, mid + 1, qr); res.x = L.x + R.x; return res; } } update(u); } void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) b[i] = a[i] - a[i - 1]; build(1, 1, n); while (m--) { int op; cin >> op; if (op == 1) { LL l, r, k, d; cin >> l >> r >> k >> d; modify(1, 1, n, l, l, k); if (l + 1 < r) modify(1, 1, n, l + 1, r, -(k + (r - l) * d)); if (r + 1 < n) modify(1, 1, n, r + 1, r + 1, -(k + (r - l) * d)); } else { int p; cin >> p; cout<< query(1, 1, n, 1, p).x<< endl; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) { solve(); } return 0; } ``` 归纳总结以上内容，生成内容时需要带简单的排版

正文

前言

发现线段树根本不会写，所以想要完成洛谷官方题单来稍微提升一下...
持续更新ing

[========]

P3870 [TJOI2009] 开关
明确了写线段树要思考的几个点
1.如何update，即如何合并子节点的信息，这里就是直接将子节点的灯的数量相加即可
2.如何modify，即如何根据tag修改该节点的值，这里就是节点长度-灯的数量就行
还有如何下传tag，这里直接^就行

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<assert.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const int N=1e5+10;
struct Node{
    int add;
    int x;
}seg[N*4];

Node operator+(const Node& a,const Node& b){
    Node c;
    c.x=a.x+b.x;
    return c;
}

void settag(int u,int l,int r,int add){
    if(add==1){
        int len=r-l+1;
        seg[u].x=len-seg[u].x;
        seg[u].add^=add;
    }
}

void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    settag(u*2,l,mid,seg[u].add);
    settag(u*2+1,mid+1,r,seg[u].add);
    seg[u].add=0;
}

void update(int u){
    seg[u].x=seg[u*2].x+seg[u*2+1].x;
}

void modify(int u,int l,int r,int ql,int qr,int add){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)settag(u,l,r,add);
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)modify(u*2,l,mid,ql,qr,add);
        else if(ql>=mid+1)modify(u*2+1,mid+1,r,ql,qr,add);
        else{
            modify(u*2,l,mid,ql,mid,add);
            modify(u*2+1,mid+1,r,mid+1,qr,add);
        }
        update(u);
    }
}

Node query(int u,int l,int r,int ql,int qr){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)return seg[u];
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)return query(u*2,l,mid,ql,qr);
        else if(ql>=mid+1)return query(u*2+1,mid+1,r,ql,qr);
        else{
            auto L=query(u*2,l,mid,ql,mid);
            auto R=query(u*2+1,mid+1,r,mid+1,qr);
            Node res=L+R;
            return res;
        }
        update(u);
    }
}

void solve(){
    int n,m;
    cin>>n>>m;

    while(m--){
        int c,a,b;
        cin>>c>>a>>b;
        if(c==0){
            modify(1,1,n,a,b,1);
        }else{
            cout<<query(1,1,n,a,b).x<<endl;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

[========]

P1438 无聊的数列
区间加等差数列，单点求和
直接转化为差分，区间加就行
用树状数组也能做

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<assert.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const int N=1e5+10;
LL a[N],b[N];
struct Node{
    LL add;
    LL x;
}seg[N*4];

void update(int u){
    seg[u].x=seg[u*2].x+seg[u*2+1].x;
}

void build(int u,int l,int r){
    assert(l<=r);
    if(l==r)seg[u].x=b[l];
    else{
        int mid=l+r>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        update(u);
    }
}

void settag(int u,int l,int r,LL add){
    int len=r-l+1;
    seg[u].x+=len*add;
    seg[u].add+=add;    
}

void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    settag(u*2,l,mid,seg[u].add);
    settag(u*2+1,mid+1,r,seg[u].add);
    seg[u].add=0;
}

void modify(int u,int l,int r,int ql,int qr,LL add){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)settag(u,l,r,add);
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)modify(u*2,l,mid,ql,qr,add);
        else if(ql>=mid+1)modify(u*2+1,mid+1,r,ql,qr,add);
        else{
            modify(u*2,l,mid,ql,mid,add);
            modify(u*2+1,mid+1,r,mid+1,qr,add);
        }
        update(u);
    }
}

Node query(int u,int l,int r,int ql,int qr){
    assert(l<=ql and qr<=r);
    if(l==ql and r==qr)return seg[u];
    else{
        pushdown(u,l,r);
        int mid=l+r>>1;
        if(qr<=mid)return query(u*2,l,mid,ql,qr);
        else if(ql>=mid+1)return query(u*2+1,mid+1,r,ql,qr);
        else{
            Node res;
            auto L=query(u*2,l,mid,ql,mid);
            auto R=query(u*2+1,mid+1,r,mid+1,qr);
            res.x=L.x+R.x;
            return res;
        }
        update(u);
    }
}

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
    build(1,1,n);

    while(m--){
        int op;cin>>op;
        if(op==1){
            LL l,r,k,d;
            cin>>l>>r>>k>>d;
            modify(1,1,n,l,l,k);
            if(l+1<=r)modify(1,1,n,l+1,r,d);
            if(r+1<=n)modify(1,1,n,r+1,r+1,-(k+(r-l)*d));
        }else{
            int p;cin>>p;
            cout<<query(1,1,n,1,p).x<<endl;
        }
    }  
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}