Logo 铜龟的博客

博客

哪错了???

2023-07-12 12:49:36 By 铜龟
#include<cstdio>
#include<cmath>
int f[50005];
int n;
int text[50005];//每一个点属于哪一个班
int text2[224];//每一个班的开头
int text3[224];
int num[224];//sqrt(50000)+1
void add(int a/*区间开始*/,int b/*区间结束*/,int c/*修改值*/){
    int l,r;//第一个完整修改的班级和最后一个完整修改的班级
    if(a!=text2[text[a]]){//如果区间开始不是那个班级的开头
        l=text2[text[a]+1];
    }
    if(b!=text2[text[b]+1]-1){//如果区间结束不是那个班级的结束
        r=text2[text[b]-1];
    }
    for(int i = l;i <= r;i++){
        num[i]+=c;//大段维护
    }
    if(a!=text2[text[a]])
        for(int i = text2[l]-1;i>=a;i--){
            f[i]+=c;//小段暴力(开头)
        }
    if(b!=text2[text[b]]-1)
        for(int j = text2[r];j <= b;j++){
            f[j]+=c;//小段暴力(结尾)
        }

}
int main(){
    scanf("%d",&n);
    int k = 0;
    for(int i = 0;i <= n;i+=sqrt(n)){
        text2[k]=i;
        if(i!=0){
            text3[k]=i-1;
        }
        for(int j = i;j < i+sqrt(n);j++){
            text[j]=k;
        }
        k++;
    }
    for(int i = 0;i < n;i++){
        scanf("%d",&f[i]);
    }
    int a,b,c,d;
    for(int i= 0 ;i < n;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a==0){
            add(b-1,c-1,d);
        }else{
            printf("%d\n",num[text[c-1]]+f[c-1]);//集体+个人=总共
        }
    }
    return 0;
}

loj6277

评论

阿兹卡班的小天狼星
分块
阿兹卡班的小天狼星
大段维护,小段暴力

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。