题解 P1438 【无聊的数列】

cxy004 · 2015-07-22 18:03:10 · 题解

标记永久化，随用随查的ZKW线段树 【百度PPT《统计的力量》

一个区间维护2个值，首项和公差

再存一个区间左端点【其实可以直接算

具体维护时用等差数列通项公式算就行了

#include<cstdio>
using namespace std;

const int M=131071;
int n,m,d[262144],s[262144],g[262144];
//d为区间左端点，s为首项【即区间左端点的值】，g为公差

void D(const int &m,const int &l,const int &r) //计算区间m的左端点【其实可以试着直接计算通项公式
{
    d[m]=l;
    if(l==r) return;
    const int M=(l+r)>>1,t=m<<1;
    D(t,l,M);D(t|1,M+1,r);
}

void Updata(const int &L,const int &R,const int &K,const int &D) 【操作1
{
    for(int l=L+M-1,r=R+M+1;l^r^1;l>>=1,r>>=1)
    {
      if(!(l&1)) {s[l^1]+=K+(d[l^1]-L)*D;g[l^1]+=D;}
      if(r&1) {s[r^1]+=K+(d[r^1]-L)*D;g[r^1]+=D;;}
    }
}

int Search(const int &m) 【操作2
{
    int Ans=0;
    for(int i=m+M;i>=1;i>>=1) Ans+=s[i]+(m-d[i])*g[i];
    return Ans;
}

int main()
{
    D(1,1,131072);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&s[M+i]);
    for(;m--;)
    {
      int c;scanf("%d",&c);
      if(c==1) {int L,R,K,D;scanf("%d%d%d%d",&L,&R,&K,&D);Updata(L,R,K,D);}
      else {int m;scanf("%d",&m);printf("%d\n",Search(m));}
    }
    return 0;
}