题解 P1438 【无聊的数列】

清远学会 · 2019-09-23 07:30:19 · 题解

遇事不决先分块

分块——一种优雅的暴力，既可以感受到暴力的美感，也可以享受AC的快感

这道题其实没啥，只要学过数列就行；发现数列的首项与公差是可以相加的

  例如 1 2 3 4  5  6 首项是1，公差为1
       1 3 5 7  9  11 首项是1，公差为2
       2 5 8 11 14 17 上下相加即为首项为2，公差为3的新数列

重点维护：

数列最要的首项和公差；对于每个块都维护这样两个值，查询时O(1)推一下就行

最后奉上代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 300500
using namespace std;

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

int n,m;
int a[N];
int tag[N],L[N],R[N];
int lzk[N],lzd[N];

inline void Change(int l,int r,int k,int d) {
    if(tag[l] == tag[r]) {
        for(int i = l;i <= r;i ++)
            a[i] += k + d * (i - l);
        return ;
    }
    int res = k + d * (R[tag[l]] - l + 1);
    for(int i = l;i <= R[tag[l]];i ++) 
        a[i] += k + d * (i - l);
    for(int i = tag[l] + 1;i < tag[r];i ++)
        lzk[i] += res,lzd[i] += d,res += d * (R[i] - L[i] + 1);
    for(int i = L[tag[r]];i <= r;i ++)
        a[i] += res + d * (i - L[tag[r]]);
}

inline int Ask(int p) {
    int k = lzk[tag[p]],d = lzd[tag[p]];
    int res = a[p] + k + d * (p - L[tag[p]]);
    return res;
}

int main() {
    n = read(),m = read(); int len = sqrt(n);
    for(int i = 1;i <= n;i ++) a[i] = read();
    for(int i = 1;i <= n;i ++) tag[i] = (i - 1) / len + 1;
    for(int i = 1;i <= tag[n];i ++) 
        L[i] = R[i - 1] + 1,R[i] = min(n,L[i] + len - 1);
    for(int i = 1;i <= m;i ++) {
        int opt = read();
        if(opt == 1) {
            int l = read(),r = read(),k = read(),d = read();
            Change(l,r,k,d);
        }
        else {
            int p = read();
            printf("%d\n",Ask(p));
        }
    }
}