题解 P1438 【无聊的数列】

ping_fan · 2018-07-30 22:01:21 · 题解

翻了翻楼下各位神犇们的代码，蒟蒻表示看不懂啊......╮(╯▽╰)╭

于是蒟蒻发布了自己的第一篇题解......

下面奉上代码和注释

#include<cstdio>
using namespace std;
int n,st, a[100010],tag[400010],tagd[400010], c,cl,cr,ck,cd,fp, x;//n：数列长度,st：操作个数, a：数列,tag：懒标记, tagd：标记公差, c：操作种类, cl：等差数列的左端点, cr：等差数列的右端点, ck：首项, cd：公差, fp：查找的点, x：循环 
void pd(int p,int l,int r)//下传 
{//p：当前节点,l，当前区间左端点,r：当前区间右端点
    tag[p*2]+=tag[p];//懒标记下传左节点
    tagd[p*2]+=tagd[p];//公差下传左节点
    tag[p*2+1]+=tag[p]+((l+r)/2+1-l)*tagd[p];//懒标记下传右节点
    tagd[p*2+1]+=tagd[p];//公差下传右节点
    tag[p]=0;//清空当前节点懒标记
    tagd[p]=0;//清空当前节点公差
    return;
}
void gx(int p,int l,int r)//区间修改
{//p：当前节点,l，当前区间左端点,r：当前区间右端点
    if(cl<=l&&cr>=r)//当前区间在要修改的区间范围内 
    {
        tag[p]+=ck+(l-cl)*cd;
        tagd[p]+=cd;
        return;
    }
    pd(p,l,r);//下传懒标记
    if(cl<=(l+r)/2)
        gx(p*2,l,(l+r)/2);//继续修改左节点
    if(cr>=(l+r)/2+1)
        gx(p*2+1,(l+r)/2+1,r);//继续修改右节点
    return;
}
int cz(int p,int l,int r)//单点查询
{//p：当前节点,l，当前区间左端点,r：当前区间右端点
    if(fp==l&&fp==r)//找到了 
        return tag[p];//直接返回区间的懒标记值 
    pd(p,l,r);//下传懒标记
    if(fp<=(l+r)/2)
        return cz(p*2,l,(l+r)/2);//继续查询左节点
    else
        return cz(p*2+1,(l+r)/2+1,r);//继续查询右节点
}
int main()
{ 
    scanf("%d%d",&n,&st);
    for(x=1;x<=n;++x)
        scanf("%d",&a[x]);
    for(x=1;x<=st;++x)
    {
        scanf("%d",&c);
        if(c==1)
        {
            scanf("%d%d%d%d",&cl,&cr,&ck,&cd);
            gx(1,1,n);
        }
        else
        {
            scanf("%d",&fp);
            printf("%d\n",a[fp]+cz(1,1,n));
        }
    }:)
    return 0;
}