题解 P1438 【无聊的数列】

GUO大侠 · 2018-10-25 22:52:05 · 题解

受 @ Okkkkkkkkk 的启发,特写一篇详细的分块题解

由等差数列的数学性质可知:几段等差数列叠加起来一定也是等差数列.
那么对于区间叠加的等差数列,我们天真地想:
要是每一段都是重合的就好了,暴力加,就不会出现有的地方有等差数列a,有的地方有等差数列b的乱七八糟的情况.

But there is no such thing as a free lunch.

但我们强制实现这个想法:把序列分块,对于每一次区间加,暴力维护两端两个根号块内的序列,对于被修改区间完全包含的块块,我们记录首项和公差,就可以实现这个天真的想法了\=￣ω￣=/.

ps: 两端的"散户"要特判在一个块的情况

代码如下:

#include<bits/stdc++.h>
#define N 100001
using namespace std;
int read(){
  int data=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
  return data*w;
}
const int blk=350;
int a[N],n,m,pos[N],tag[blk],s[blk];
void add(int l,int r,int k,int d){
    for(int i=l;i<=min(r,(pos[l]+1)*blk);i++)a[i]+=k+(i-l)*d;
    if(pos[l]!=pos[r])
        for(int i=(pos[r])*blk+1;i<=r;i++)a[i]+=k+(i-l)*d;//+1
    for(int i=pos[l]+1;i<pos[r];i++)tag[i]+=d,s[i]+=k+(i*blk+1-l)*d;//**i*blk
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){a[i]=read();pos[i]=(i-1)/blk;}
    for(;m;m--)
        if(read()&1){
            int l=read(),r=read(),k=read(),d=read();
            add(l,r,k,d);
        }
        else{
            int q=read();printf("%d\n",a[q]+s[pos[q]]+tag[pos[q]]*(q-((pos[q])*blk+1)));
        }
    return 0;
}