题解 P1438 【无聊的数列】

上进的z君 · 2016-08-03 10:32:42 · 题解

楼下的大神用的ZKW线段树比较高级，蒟蒻表示不太会用……╮(╯_╰)╭

所以就写了一个弱弱的线段树。

下面贴代码+注释

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=100010;
int sum[maxn*4],add[maxn*4],n,m,a[maxn];//线段树的4倍数组不要忘了，不然会WA或者RE的
void Update(int rt,int l,int r,int x,int y,int p,int q){
    if(x>r||y<l)return;
    if(x<=l&&y>=r){
        sum[rt]+=p+q*(l-x);
//这里计算出当前区间的左端点相对于L的位置，并且累加值。然后后面在查询点的时候，只要知道那个点相对于左端点的位置即可
        add[rt]+=q;//记录公差
        return;
    }
    int mid=(l+r)/2;
    Update(rt*2,l,mid,x,y,p,q);
    Update(rt*2+1,mid+1,r,x,y,p,q);
    return;
}
int Query(int rt,int l,int r,int x){
    if(x<l||x>r)return 0;
    if(l==r)return sum[rt];
    int mid=(l+r)/2;
    int p1=Query(rt*2,l,mid,x);
    int p2=Query(rt*2+1,mid+1,r,x);
    return p1+p2+sum[rt]+add[rt]*(x-l);//其实用非递归写可能会更好，不过递归更加优美……
//这里就是在向下查询，每遇到一个父节点，就计算P跟父节点的相对位置，然后累加
}
int main()
{
    //freopen("c.in","r",stdin);
    //freopen("c.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        int p,l,r,k,d;
        scanf("%d",&p);
        if(p&1){
            scanf("%d%d%d%d",&l,&r,&k,&d);
            Update(1,1,n,l,r,k,d);
        }
        else{
            scanf("%d",&d);
            int ans=Query(1,1,n,d);
            printf("%d\n",a[d]+ans);
        }
    }
    return 0;
}