洛谷P1438 无聊的数列

题目

线段树。一开始以为是考查lazy数组的变化。然而并不是。

等差数列的性质是相邻的数的差相等，给一段数加上一段相邻的差相等的数列，会发现他们之间的差也会增加，而且相邻的数差增加的是一致的，又因为是单点查询一个数，相当于区间查询差分数组，因此可以用线段树区间修改差分数组，区间查询差分数组。

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 100003
using namespace std;
int l, r, k, d, n, m, judge, p, tree[N*4], a[N],lazy[N*4];
inline void push_down(int root, int len)//len代表着等差数列的长度 
{
    if (lazy[root])
    {
        lazy[root << 1] += lazy[root];
        lazy[root << 1 | 1] += lazy[root];
        tree[root << 1] += (len - (len >> 1)) * lazy[root];
        tree[root << 1 | 1] += (len >> 1) * lazy[root];//len>>1等于 (int) (len/2)，左子树的个数
        lazy[root] = 0;
    }
}   
inline void pushup(int root)
{   
    tree[root] = tree[root << 1] + tree[root << 1 | 1];//lazy tag 的用途就是免除不必要的信息在每个区间向它的子区间传导。 
}   
int query(int now, int l, int r, int ql, int qr)
{   
    if(ql <= l && r <= qr)
        return tree[now]; 
    push_down(now, r - l + 1);
    lazy[now] = 0;
    int res = 0, mid = (l + r) >> 1;
    if (mid >= ql) res += query(now << 1, l, mid, ql, qr);
    if (mid < qr) res += query(now << 1 | 1, mid + 1, r, ql, qr);
    return res;
}

void update(int ql, int qr, int l, int r, int now, int s)
{
    if (l >= ql && r <= qr)
    {
        tree[now] += (r - l + 1) * s;
        lazy[now] += s;//s相当于add 
        return;   
    }             
    push_down(now, r - l + 1);
    int mid = (l + r) >> 1;
    if(mid >= ql) update(ql, qr, l, mid, now << 1, s);
    if(mid < qr)  update(ql, qr, mid + 1, r, now << 1 | 1, s);
    pushup(root);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &judge);
        if (judge == 1)
        {
            scanf("%d%d%d%d", &l, &r, &k, &d);
            update(l, l, 1, n, 1, k);
            if (r > l)
                update(l + 1, r, 1, n, 1, d);//区间修改差分数组。 
            if (r < n)
                update(r + 1, r + 1, 1, n, 1, - (k + (r - l) * d));//分两段传递修改，分别修改, 其实就是差分数组。
        }
        else
        {
            scanf("%d", &p);
            printf("%d\n", a[p] + query(1, 1, n, 1, p));//区间(1, p)内的所有等差数列的权值和。 
        }
    }
    return 0;
}

洛谷P1438 无聊的数列

原文：https://www.cnblogs.com/liuwenyao/p/11788748.html