洛谷P2023 [AHOI2009]维护序列（线段树区间更新，区间查询）

洛谷P2023 [AHOI2009]维护序列

区间修改

当我们要修改一个区间时，要保证 \(ax+b\) 的形式，即先乘后加的形式。当将区间乘以一个数 \(k\) 时，原来的区间和为 \(ax+b\) ，乘以 \(k\) 得 \(k(ax+b)=kax+kb\) 。

区间加一个数更加简单，原来的区间和为 \(ax+b\) ，加上一个 \(k\) 为 \(ax+b+k\) ，合并 \(b\) ，\(k\) 得 \(ax+(b+k)\) 。

标记下传

\[a(a'x+b')+b = (aa')\cdot x + (ab'+b)
\]

#include<bits/stdc++.h>

using namespace std;

#define lson l, mid, root << 1

#define rson mid + 1, r, root << 1 | 1

const int maxn = 100005;

long long tree[maxn << 2];

int n, p, q;

struct L{

    long long mul, add;

}label[maxn << 2];

inline void pushUp(int root)

{

    tree[root] = (tree[root << 1] + tree[root << 1 | 1]) % p;

}

inline void pushDown(int root, int len)

{

    if(label[root].add == 0 && label[root].mul == 1) return;

    else{

        tree[root << 1] = (label[root].mul * tree[root << 1] + label[root].add * (len - (len >> 1))) % p;/***长度划分***/

        tree[root << 1 | 1] = (label[root].mul * tree[root << 1 | 1] + label[root].add * (len >> 1)) % p;

        label[root << 1].add = (label[root].mul * label[root << 1].add + label[root].add) % p;

        label[root << 1 | 1].add = (label[root].mul * label[root << 1 | 1].add + label[root].add) % p;

        label[root << 1].mul = (label[root << 1].mul * label[root].mul) % p;

        label[root << 1 | 1].mul = (label[root << 1 | 1].mul * label[root].mul) % p;

        label[root].add = 0; label[root].mul = 1;

    }

}

void build(int l, int r, int root)

{

    label[root].add = 0; label[root].mul = 1;

    if(l == r){

        scanf("%lld", &tree[root]); return;

    }

    int mid = (l + r) >> 1;

    build(lson); build(rson);

    pushUp(root);

}

void update(int l, int r, int root, int L, int R, int tag, int c)

{

    if(L == l && R == r){

        if(tag == 1){

            tree[root] = tree[root] * c % p;

            label[root].add = label[root].add * c % p;

            label[root].mul = label[root].mul * c % p;

        }else{

            tree[root] = (tree[root] + c * (r - l + 1)) % p;

            label[root].add = (label[root].add + c) % p;

        }

        return;

    }

    pushDown(root, r - l + 1);

    int mid = (l + r) >> 1;

    if(L >= mid + 1) update(rson, L, R, tag, c);

    else if(R <= mid) update(lson, L, R, tag, c);

    else{

        update(lson, L, mid, tag, c); update(rson, mid + 1, R, tag, c);

    }

    pushUp(root);

}

long long query(int l, int r, int root, int L, int R)

{

    if(L == l && R == r){

        return tree[root] % p;

    }

    pushDown(root, r - l + 1);

    int mid = (l + r) >> 1;

    if(L >= mid + 1) return (query(rson, L, R) % p);

    else if(R <= mid) return (query(lson, L, R) % p);

    else{

        return ((query(lson, L, mid) + query(rson, mid + 1, R)) % p);

    }

}

int main()

{

    scanf("%d%d", &n, &p);

    build(1, n, 1);

    scanf("%d", &q);

    for(int cas = 1; cas <= q; cas++){

        int tag, t, g, c;

        scanf("%d", &tag);

        if(tag == 1){

            scanf("%d%d%d", &t, &g, &c);

            update(1, n, 1, t, g, 1, c);

        }

        else if(tag == 2){

            scanf("%d%d%d", &t, &g, &c);

            update(1, n, 1, t, g, 2, c);

        }

        else{

            scanf("%d%d", &t, &g);

            printf("%lld\n", query(1, n, 1, t, g) % p);

        }

    }

    return 0;

}

巴特西

洛谷P2023 [AHOI2009]维护序列（线段树区间更新，区间查询）

最新文章

热门文章