题解：P1438 无聊的数列

wjr_jok · 2024-05-21 20:07:40 · 题解

题意

给你一个长度为 n 的数列，要对它进行 m 次操作，有修改和询问两种操作。

修改：将 l \sim r 的区间加上一个首项为 k，公差为 d 的等差数列。

询问：询问序列的第 p 个数的值。

最后要你输出这个数列每个数的值。

暴力思路

分块，对于散块直接算出等差数列对应的值进行修改，对于整块则是用一个 vector 类型的 add 数组记录这个等差数列的开始位置 l，初始项 k 以及公差 d，因为每次加的是一个等差数列，无法合并，只能分开处理。

询问时就比较暴力了，直接使用循环遍历 add 数组，通过首项，当前位置以及公差算出对应的数，然后全部加上即可得到答案。

Code

#include<bits/stdc++.h>
using namespace std;
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
void write(long long n){
    if(n<0) putchar('-'),n*=-1;
    if(n>9) write(n/10);
    putchar(n % 10 + '0');
}
//快读快写防止超时
struct jgt{
    int x;//开始位置
    int y;//初始项
    int z;//公差
    int cs;//小优化，记录重复次数防止MLE
} cc;
int n,m,s,l,r,k,d;
long long cnt;
long long xl[100001];
int x[401],y[401],fk[100001];
vector<jgt> xg[401];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=(int)sqrt(n);i++){
        cnt++;
        x[cnt]=y[cnt-1]+1;
        y[cnt]=x[cnt]+(int)sqrt(n)-1;
        for(int j=x[cnt];j<=y[cnt];j++){
            fk[j]=cnt;
        }
    }
    if(y[cnt]<n){
        cnt++;
        x[cnt]=y[cnt-1]+1;
        y[cnt]=n;
        for(int i=x[cnt];i<=y[cnt];i++){
            fk[i]=cnt;
        }
    }
    for(int i=1;i<=n;i++){
        xl[i]=read();
    }
    for(int i=1;i<=m;i++){
        s=read();
        if(s==1){
            l=read(),r=read(),k=read(),d=read();
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                xl[j]+=k+(j-l)*d;
            }
            if(fk[l]!=fk[r]){
                for(int j=x[fk[r]];j<=r;j++){
                    xl[j]+=k+(j-l)*d;
                }
            }
            for(int j=fk[l]+1;j<fk[r];j++){
                if(!xg[j].empty()){
                    cc=xg[j][xg[j].size()-1];
                }
                if(l==cc.x&&k==cc.y&&d==cc.z&&!xg[j].empty()){
                    xg[j][xg[j].size()-1].cs++;
                }
              //单独处理重复情况
                else{
                    cc.x=l;
                    cc.y=k;
                    cc.z=d;
                    xg[j].push_back(cc);
                  //更新add数组
                }
            }
        }
        else{
            k=read();
            cnt=xl[k];
            for(int j=0;j<xg[fk[k]].size();j++){
                cnt+=xg[fk[k]][j].y+(k-xg[fk[k]][j].x)*xg[fk[k]][j].z*(xg[fk[k]][j].cs+1);//原始值加上add数组的值
            }
            write(cnt);
            puts("");
        }
    }
    return 0;
}