首页 > 其他 > 详细

P1438 无聊的数列

时间:2019-03-29 18:07:50      阅读:123      评论:0      收藏:0      [点我收藏+]

P1438 无聊的数列

链接

分析:

  等差数列可加,首项相加,公差相加。

代码:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==-)f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-0;return x*f;
}

const int N = 1e5 + 10;
int A[N << 2], D[N << 2], ori[N];

void pushdown(int rt,int l,int r) {
    int mid = (l + r) >> 1;
    A[rt << 1] += A[rt];
    A[rt << 1 | 1] += A[rt] + (mid - l + 1) * D[rt]; 
    D[rt << 1] += D[rt];
    D[rt << 1 | 1] += D[rt];
    A[rt] = D[rt] = 0;
}
void update(int l,int r,int rt,int L,int R,int a,int d) {
    if (L <= l && r <= R) {
        A[rt] += a + (l - L) * d; D[rt] += d; return ;
    }
    if (A[rt] || D[rt]) pushdown(rt, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) update(l, mid, rt << 1, L, R, a, d);
    if (R > mid) update(mid + 1, r, rt << 1 | 1, L, R, a, d);
}
int query(int l,int r,int rt,int p) {
    if (l == r) return ori[l] + A[rt];
    if (A[rt] || D[rt]) pushdown(rt, l, r);
    int mid = (l + r) >> 1;
    if (p <= mid) return query(l, mid, rt << 1, p);
    else return query(mid + 1, r, rt << 1 | 1, p);
}
int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) ori[i] = read();
    while (m --) {
        if (read() == 1) {
            int l = read(), r = read(), a = read(), d = read();
            update(1, n, 1, l, r, a, d);
        }
        else {
            int x = read();
            cout << query(1, n, 1, x) << "\n";
        }
    }
    return 0;
}

 

P1438 无聊的数列

原文:https://www.cnblogs.com/mjtcn/p/10622772.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!