题解 P1438 无聊的数列

· · 题解

这道题似乎有许多种做法，如利用等差数列上加上一个等差数列仍然是一个等差数列的性质,或把a_{i}+k+(i-l)\times d转化成a_{i}+(k-l\times d)+i\times d

我是对原数组的差分数组再次差分。

等差数列的两项之差为d,容易想到对原数组差分。

设原数组a的差分数组为b

对a_{i}+k+(i-l)\times d的修改其中i\in[l,r]转化为对b_{l}+k和

b_{l}+d(i\in(l,r])$以及$b_{r+1}-k-(r-l+1)\times d

询问序列的第P个数a_{p}的值相当于求\sum_{i=1}^p b_{i}

仔细一想,这不就是对b数组进行区间加和区间求和操作。

设b的差分数组为c对b_{i}+d(i\in(l,r])及对c_{l+1}+d 和c_{r+1}-d

用数组c0维护数组c前缀和,用数组c1维护数组c_{i}\times i前缀和。

\sum_{i=1}^p\sum_{j=1}^ic_{i}=\sum_{i=1}^p(p-i+1)\times c_{i}=(p+1)\times \sum_{i=1}^pc_{i}-i\sum_{i=1}^pi\times c_{i}

用树状数组维护c0,c1即可。

时间复杂度为O(nlogn)

不知为何跑起来飞快

截止2019.6.29日，这份代码在你谷排第四

Code: 
#include<iostream>
#include<cctype>
#include<cstdio>
const int MAXN=100001;int n;
#define LL long long
LL as[MAXN+10],_c0[MAXN+10],_c1[MAXN+10],_c2[MAXN+10];
LL read(){
  LL sum=0;int f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')sum=sum*10+ch-'0',ch=getchar();
  return f*sum;
}
inline void add0(const int &x,const LL &k){
  int i;for (i=x;i<=n;i+=i&(-i)) _c0[i]+=k;
}
inline LL ask0(const int &x){
  LL ans=0;int i;
  for (i=x;i;i-=i&(-i)) ans+=_c0[i];return ans;
}
inline void add1(const int &x,const LL &k){
  int i;for (i=x;i<=n;i+=i&(-i)) _c1[i]+=k;
}
inline LL ask1(const int &x){
  LL ans=0;int i;
  for (i=x;i;i-=i&(-i)) ans+=_c1[i];return ans;
}
int main(){
    int m,i;
    n=read();m=read();
    for (i=1;i<=n;++i) as[i]=as[i-1]+read();
    int op,l,r;
    LL k,d,c0,c1,c2,ad1,ad2;
    for (i=1;i<=m;++i){
        op=read();
        if (op==1){
            l=read(),r=read(),k=read(),d=read();
            ad1=-k-(r-l+1)*d,ad2=k+(r-l)*d;
            add0(l,k),add0(r+1,ad1),add0(l+1,d-k),add0(r+2,ad2);
            add1(l,l*k),add1(r+1,(r+1)*ad1);
            add1(l+1,(l+1)*(d-k)),add1(r+2,(r+2)*ad2);
        } 
        else {
            l=read();
            c1=ask1(l),c0=ask0(l);
            printf("%d\n",as[l]-as[l-1]+(l+1)*c0-c1);
        }
    }
}