题解 P1438 【无聊的数列】

Canony · 2017-08-09 20:23:16 · 题解

用普通线段树实现，记录并维护区间首项和公差的lazy值lk和ld

维护sum时要用等差数列求和公式Sn=n*an+（n-1）*n*d/2。

下面给出代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define il id<<1
#define ir id<<1|1
const int MAXN=100005;
struct Node
{
    int l,r;
    int lk,ld;
    int sum;
}t[MAXN*5];
int a[MAXN];
void build(int id,int left,int right)
{
    t[id].l=left;
    t[id].r=right;
    t[id].lk=0;
    t[id].ld=0;
    if(left==right)
    {
        t[id].sum=a[left];
        return;
    }
    int m=(left+right)/2;
    build(il,left,m);
    build(ir,m+1,right);
    t[id].sum=t[il].sum+t[ir].sum;
}
void pushdown(int id)
{
    t[il].lk+=t[id].lk;//对于左区间可以直接加
    t[il].ld+=t[id].ld;
    t[ir].lk+=t[id].lk+t[id].ld*(t[il].r-t[il].l+1);//而右区间则要求出等差数列在右区间的第一项作为首项
    t[ir].ld+=t[id].ld;
    t[id].ld=0;
    t[id].lk=0;
}
void change(int id,int left,int right,int k,int d)
{
    if(t[id].l==left && t[id].r==right)
    {
        t[id].lk+=k;
        t[id].ld+=d;
        return;
    }
    if(t[id].lk || t[id].ld)
        pushdown(id);
    if(right<=t[il].r)
        change(il,left,right,k,d);
    else if(left>=t[ir].l)
        change(ir,left,right,k,d);
    else
    {
        change(il,left,t[il].r,k,d);
        change(ir,t[ir].l,right,k+d*(t[il].r-left+1),d);//查询时右区间同上也需改变首项
    }
    int lenl=t[il].r-t[il].l+1;
    int lenr=t[ir].r-t[ir].l+1;
    t[id].sum=t[il].sum+t[ir].sum
             +t[il].lk*lenl+lenl*(lenl-1)*t[il].ld/2
             +t[ir].lk*lenr+lenr*(lenr-1)*t[ir].ld/2;
}
int query(int id,int x)
{
    if(t[id].l==t[id].r)
        return t[id].sum+t[id].lk;
    if(t[id].lk || t[id].ld)
    {
        int len=t[id].r-t[id].l+1;
        t[id].sum+=t[id].lk*len+len*(len-1)*t[id].ld/2;
        pushdown(id);
    }
    if(x<=t[il].r)
        return query(il,x);
    else
        return query(ir,x);
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    int c，x,l,r,k,d;
    while(m--)
    {
        cin>>c;
        if(c==1)
        {
            cin>>l>>r>>k>>d;
            change(1,l,r,k,d);
        }
        else
        {
            cin>>x;
            cout<<query(1,x)<<endl;
        }
    }
    return 0;
}