题解 P1438 【无聊的数列】

King丨帝御威 · 2018-12-13 17:41:16 · 题解

咦，突然发现我的思路跟所有人都不太一样诶，那我也来一发！！！

首先，这道题肯定是线段树/树状数组，然而菜菜的我不太会用树状数组，所有就往线段树那考虑，其实我的思路还是比较暴力的，就是维护每个树上的k和d，然后不断更新，然后好像就完了……具体实现看代码吧QwQ~~~

下面是我香喷喷的代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100001
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
int a[maxn],n,m,id[maxn];
inline int qread()                  //快读。
{
    char c=getchar();int num=0,f=1;
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) num=num*10+c-'0';
    return num*f;
}
struct Tree
{
    bool f;
    int k,d;
}tree[maxn<<2];      //f为是为了下面的down操作用的。k和d就是题目中的那俩变量。
inline void pushdown(int rt,int len)  //更新。
{
    int k=tree[rt].k,d=tree[rt].d;
    tree[ls].k+=k,tree[ls].d+=d;
    tree[rs].k+=k+len*d,tree[rs].d+=d;
    tree[ls].f=1,tree[rs].f=1;
    tree[rt].k=tree[rt].d=tree[rt].f=0;
    return;
}
void build(int rt,int l,int r)   //建树。
{
    if(l==r)
    {
        a[l]=qread(),id[l]=rt;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void modify(int rt,int l,int r,int L,int R,int k,int d)  //区间修改。
{
    if(L<=l&&r<=R)
    {
        tree[rt].k+=k,tree[rt].d+=d;
        tree[rt].f=1;
        return;
    }
    int mid=(l+r)>>1;
    if(tree[rt].f) pushdown(rt,mid-l+1);
    if(R<=mid) modify(ls,l,mid,L,R,k,d);
    else if(L>mid) modify(rs,mid+1,r,L,R,k,d);
    else modify(ls,l,mid,L,mid,k,d),modify(rs,mid+1,r,mid+1,R,k+(mid-L+1)*d,d);
}
void down(int rt,int l,int r,int pos)    //递归更新。
{
    if(l==r) return;
    int mid=(l+r)>>1;
    if(tree[rt].f) pushdown(rt,mid-l+1);
    if(pos<=mid) down(ls,l,mid,pos);
    else down(rs,mid+1,r,pos);
}
int main()
{
    n=qread(),m=qread();
    build(1,1,n);
    for(int i=1,l,r,k,d,p;i<=m;++i)   
    {
        p=qread();
        if(p==1) 
        {
            l=qread(),r=qread(),k=qread(),d=qread();
            modify(1,1,n,l,r,k,d);
        }
        else 
        {
            l=qread();
            down(1,1,n,l);
            cout<<a[l]+tree[id[l]].k<<'\n';
        }
    }
    return 0;
}