P1438 无聊的数列

梦里梦外; 2022-01-12 09:47 265阅读 0赞

## 题目背景 ##

无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）

## 题目描述 ##

维护一个数列\{a\[i\]\}，支持两种操作：

1、1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a\[L\]~a\[R\]的每一个数上。即：令a\[L\]=a\[L\]+K，a\[L+1\]=a\[L+1\]+K+D，

a\[L+2\]=a\[L+2\]+K+2D……a\[R\]=a\[R\]+K+(R-L)D。

2、2 P：询问序列的第P个数的值a\[P\]。

## 输入输出格式 ##

输入格式：

第一行两个整数数n，m，表示数列长度和操作个数。

第二行n个整数，第i个数表示a\[i\]（i=1,2,3…,n）。

接下来的m行，表示m个操作，有两种形式：

1 L R K D

2 P 字母意义见描述（L≤R）。

输出格式：

对于每个询问，输出答案，每个答案占一行。

## 输入输出样例 ##

输入样例\#1： 复制

5 2
    1 2 3 4 5
    1 2 4 1 2
    2 3

输出样例\#1： 复制

## 说明 ##

数据规模：

0≤n，m≤100000

|a\[i\]|，|K|，|D|≤200

Hint：

有没有巧妙的做法？

**题解**

用zkw线段树直接暴力就好了

在每个节点打个标记

然后用等差数列通项公式搞一搞

1 //minamoto
     2 #include<iostream>
     3 #include<cstdio>
     4 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
     5 char buf[1<<21],*p1=buf,*p2=buf;
     6 inline int read(){
     7     #define num ch-'0'
     8     char ch;bool flag=0;int res;
     9     while(!isdigit(ch=getc()))
    10     (ch=='-')&&(flag=true);
    11     for(res=num;isdigit(ch=getc());res=res*10+num);
    12     (flag)&&(res=-res);
    13     #undef num
    14     return res;
    15 }
    16 char sr[1<<21],z[20];int C=-1,Z;
    17 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
    18 inline void print(int x){
    19     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    20     while(z[++Z]=x%10+48,x/=10);
    21     while(sr[++C]=z[Z],--Z);sr[++C]='\n';
    22 }
    23 const int N=262144;
    24 int L[N],tag[N],sum[N];
    25 int n,m,q;
    26 inline void build(){
    27     for(m=1;m<n+2;m<<=1);
    28     for(int i=m+1;i<=m+n;++i) L[i]=i-m,sum[i]=read();
    29     for(int i=m-1;i;--i) L[i]=L[i<<1];
    30 }
    31 inline void update(int l,int r,int k,int d){
    32     int x=l;
    33     for(l=l+m-1,r=r+m+1;l^r^1;l>>=1,r>>=1){
    34         if(~l&1) sum[l^1]+=k+(L[l^1]-x)*d,tag[l^1]+=d;
    35         if(r&1) sum[r^1]+=k+(L[r^1]-x)*d,tag[r^1]+=d;
    36     }
    37 }
    38 inline int query(int x){
    39     int ans=0;
    40     for(int i=m+x;i;i>>=1) ans+=sum[i]+(x-L[i])*tag[i];
    41     return ans;
    42 }
    43 int main(){
    44     //freopen("testdata.in","r",stdin);
    45     n=read(),q=read();
    46     build();
    47     while(q--){
    48         int opt=read();
    49         if(opt==1){
    50             int l=read(),r=read(),k=read(),d=read();
    51             update(l,r,k,d);
    52         }
    53         else{
    54             int x=read();
    55             print(query(x));
    56         }
    57     }
    58     Ot();
    59     return 0;
    60 }

转载于:https://www.cnblogs.com/bztMinamoto/p/9441984.html