题解 P1438 【无聊的数列】

· · 题解

强烈要求加强数据

首先这很明显是一道线段树的板子题

我是为了学习zkw线段树才来的

但是后来我发现用不到zkw线段树

因为区间加法加的是等差数列

考虑到类似于树状数组的区间修改

我们可以使用一种神奇的方法

——————差分

考虑差分数组sum

在每次进行1操作时

sum[l]+=k,

sum[i]+=d,l<=i<=r,

sum[r+1]-=-(k+((r-l)*d).

每次查询P时,只要输出 s[P]+sum[1]+...+sum[P] 的值即可。

而对sum开一颗线段树

我们可以通过区间修改+区间查询来完成这个操作

但是

为什么我说要加强数据呢？？

因为下面的代码

打开O2后

它A了

#include<bits/stdc++.h> 
int p[100010];
int n,m;
int ans;
int main(){
    freopen("1.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    scanf("%d",&p[i]);
    for(int i=1;i<=m;i++){
        int ok;
        scanf("%d",&ok);
        if(ok==2){
            int a;
            scanf("%d",&a); 
            printf("%d\n",p[a]);
        }
        else{
            int l,r,k,d;
            scanf("%d%d%d%d",&l,&r,&k,&d);
            for(int t=l;t<=r;t++){
            p[t]+=k;
            k+=d;
            }
        }
    }
}