脚本宝典收集整理的这篇文章主要介绍了P1438 无聊的数列 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Description

洛谷传送门

Solution

很明显的一道线段树维护区间题目。

查看一下标签不难发现，可以用差分来维护。

具体来说，对于操作 1。

• 我们给 (l) 加上 (K)。

• (l) + 1 ~ (r) 加上 (D)（两个数之间的差）。

• (r + 1) 减去 (K * (r - l) * D)（除去自己的一个 (D)）。

然后对于查询操作。

直接输出 (1) ~ (p) 的区间和再加上原数组上的数即可。

总结：其实就是差分在线段树上的一个应用。

具体看代码吧（我是不会告诉你我快读写挂了，调了半天）。

Code

#include <iostream>
#include <cstdio>
#include <algorIThm>
#include <cstring>
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

const int N = 1e5 + 10;
int n, m;
int sum[N << 2], lazy[N << 2], a[N];

inline void pushup(int rt){
    sum[rt] = sum[ls] + sum[rs];
}

inline void pushdown(int l, int r, int rt){
    if(lazy[rt]){
        int mid = (l + r) >> 1;
        sum[ls] += lazy[rt] * (mid - l + 1);
        sum[rs] += lazy[rt] * (r - mid);
        lazy[ls] += lazy[rt];
        lazy[rs] += lazy[rt];
        lazy[rt] = 0;
    }
}

inline void update(int L, int R, int k, int l, int r, int rt){
    if(L <= l &amp;& r <= R){
        sum[rt] += k * (r - l + 1);
        lazy[rt] += k;
        return;
    }
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    if(L <= mid) update(L, R, k, l, mid, ls);
    if(R > mid) update(L, R, k, mid + 1, r, rs);
    pushup(rt);
}

inline int query(int L, int R, int l, int r, int rt){
    if(L <= l && r <= R)
        return sum[rt];
    pushdown(l, r, rt);
    int mid = (l + r) >> 1;
    int res = 0;
    if(L <= mid) res += query(L, R, l, mid, ls);
    if(R > mid) res += query(L, R, mid + 1, r, rs);
    return res;
}

int main(){
    freoPEn("P1438.in", "r", stdin);
    freopen("P1438.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        a[i] = read();
    for(int i = 1; i <= m; ++i){
        int op = read();
        if(op == 1){
            int l = read(), r = read(), k = read(), d = read();
            update(l, l, k, 1, n, 1);
            if(r > l) update(l + 1, r, d, 1, n, 1);
            if(r != n) update(r + 1, r + 1, -(k + (r - l) * d), 1, n, 1);
        }else{
            int x = read();
            PRintf("%dn", a[x] + query(1, x, 1, n, 1));
        }
    }
    return 0;
}

End

脚本宝典总结

以上是脚本宝典为你收集整理的P1438 无聊的数列 题解全部内容，希望文章能够帮你解决P1438 无聊的数列 题解所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。