题解 P1438 【无聊的数列】

kkxhh · 2019-03-09 11:45:14 · 题解

其他题解都是用差分做的（然而我太菜了不知道怎么转成差分）

提供一个我自己的维护的思路

对于每个点维护两个标记，第一个标记表示这个区间里的每个数加上标记，第二个标记表示这个区间里的每个数加上这个数在原数组里的下标乘上标记

也就是说

当我们对区间 [l,r] 加上一个首项为 k 公差为 d 的等差数列时，我们给这个区间加上 k - d \times l，再给每个位置加上 下标\times d，正确性显然。每次区间修改的复杂度是 O(logn) ，单点查询复杂度也是 O(logn)。于是这题我们就做完了。

另外这题可以用标记永久化优化一下常数

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
#define lt (o<<1)
#define rt (o<<1|1)

typedef long long ll;
typedef struct node{
    ll tag,tag2;
}node;

node t[400010];
ll n,m,a[100010];

inline ll read(){
    ll num=0,k=1; char c=getchar();
    while(c>'9' || c<'0') k=(c=='-')?0:k,c=getchar();
    while(c>='0' && c<='9') num=num*10+c-'0',c=getchar();
    return k?num:-num;
}

void modify(ll o,ll l,ll r,ll ql,ll qr,ll t1,ll t2){
    if(ql<=l && qr>=r) {t[o].tag+=t1,t[o].tag2+=t2; return;}
    ll mid=(l+r)>>1;
    if(ql<=mid) modify(lt,l,mid,ql,qr,t1,t2);
    if(qr>=mid+1) modify(rt,mid+1,r,ql,qr,t1,t2);
}

ll query(ll o,ll l,ll r,ll q,ll t1,ll t2){
    if(l==r) {return t1+t[o].tag+l*(t2+t[o].tag2);}
    ll mid=(l+r)>>1;
    if(q<=mid) return query(lt,l,mid,q,t1+t[o].tag,t2+t[o].tag2);
    else return query(rt,mid+1,r,q,t1+t[o].tag,t2+t[o].tag2);
}

int main(){
    n=read(); m=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    while(m--){
        ll opt=read();
        if(opt==1){
            ll l=read(),r=read(),k=read(),d=read();
            modify(1,1,n,l,r,k-d*l,d);
        }
        else{
            ll q=read();
            printf("%lld\n",query(1,1,n,q,0,0)+a[q]);
        }
    }
    return 0;
}