分块100pts但t了Subtask #1第2个点玄关求调

wuhuhuhuhuhuhu @ 2024-10-23 20:32:34

#include<bits/stdc++.h>
using namespace std;
struct kuai{
    long long zhi=0;
    long long l=0;
    long long r=0;
};
long long meikuai,a,b;
kuai block[1000005];
long long c[1000005],pai[1000005],lan[1000005]={0}; 
long long getkuai(long long x){
    return (x-1)/meikuai+1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(long long i=1;i<=a;i++){
        cin>>c[i];
        pai[i]=c[i];
    }
    meikuai=(long long)sqrt(a);
    long long sum=0,cnt=1;
    for(long long i=1;i<=a;i++){
        sum+=c[i];
        if(i%meikuai==0){
            block[cnt].zhi=sum;
            block[cnt].l=block[cnt-1].r+1;
            block[cnt].r=i;
            sum=0;
            cnt++;
        }
    }
    if(a%(long long)sqrt(a)!=0){
        block[cnt].zhi=sum;
        block[cnt].l=block[cnt-1].r+1;
        block[cnt].r=a;
    }
    char ji;
    long long quel,quer,lid,rid,d;
    for(long long i=0;i<b;i++){
        cin>>ji;
        cin>>quel>>quer;
        cin>>d;
        lid=getkuai(quel);
        rid=getkuai(quer);
        if(ji=='M'){
            if(lid==rid){
                for(long long n=quel;n<=quer;n++){
                    c[n]+=d;
                    pai[n]=c[n];
                    block[lid].zhi+=d;
                }
                if(!is_sorted(pai+block[lid].l,pai+block[lid].r+1)) sort(pai+block[lid].l,pai+block[lid].r+1);
            }
            else{
                for(long long n=quel;n<=block[lid].r;n++){
                    c[n]+=d;
                    block[lid].zhi+=d;
                }
                for(long long n=block[lid].l;n<=block[lid].r;n++){
                    pai[n]=c[n];
                }
                if(!is_sorted(pai+block[lid].l,pai+block[lid].r+1)) sort(pai+block[lid].l,pai+block[lid].r+1);
                for(long long n=lid+1;n<rid;n++){
                    block[n].zhi+=meikuai*d;
                    lan[n]+=d;
                }
                for(long long n=block[rid].l;n<=quer;n++){
                    c[n]+=d;
                }
                for(long long n=block[rid].l;n<=block[rid].r;n++){
                    pai[n]=c[n];
                }
                if(!is_sorted(pai+block[rid].l,pai+block[rid].r+1)) sort(pai+block[rid].l,pai+block[rid].r+1);
            }
        }
        else{       
            if(lid==rid){
                sum=0;
                for(long long n=quel;n<=quer;n++){
                    if(c[n]+lan[lid]>=d) sum++; 
                }   
            }
            else{
                sum=0;
                for(long long n=quel;n<=block[lid].r;n++){
                    if(c[n]+lan[lid]>=d) sum++;
                }
                for(long long n=lid+1;n<rid;n++){
                    if(!is_sorted(pai+block[n].l,pai+block[n].r+1)) sort(pai+block[n].l,pai+block[n].r+1);
                    sum+=block[n].r-(lower_bound(pai+block[n].l,pai+block[n].r+1,d-lan[n])-pai-1);
                } 
                for(long long n=block[rid].l;n<=quer;n++){
                    if(c[n]+lan[rid]>=d) sum++;
                }   
            }
            cout<<sum<<'\n';
        }
    }
    return 0;
}

by Andy2035 @ 2024-10-23 20:33:18

关注我，就不给你调

by firefly13163 @ 2024-10-23 21:08:57

把块长加1提高容错，然后提前排了一遍就过了

（改了22，35，92）

#include<bits/stdc++.h>
using namespace std;
struct kuai{
    long long zhi=0;
    long long l=0;
    long long r=0;
};
long long meikuai,a,b;
kuai block[1000005];
long long c[1000005],pai[1000005],lan[1000005]={0}; 
long long getkuai(long long x){
    return (x-1)/meikuai+1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>a>>b;
    for(long long i=1;i<=a;i++){
        cin>>c[i];
        pai[i]=c[i];
    }
    meikuai=(long long)sqrt(a)+1;
    long long sum=0,cnt=1;
    for(long long i=1;i<=a;i++){
        sum+=c[i];
        if(i%meikuai==0){
            block[cnt].zhi=sum;
            block[cnt].l=block[cnt-1].r+1;
            block[cnt].r=i;
            sort(pai+block[cnt].l,pai+block[cnt].r+1);
            sum=0;
            cnt++;
        }
    }
    if(a%((long long)sqrt(a)+1)!=0){
        block[cnt].zhi=sum;
        block[cnt].l=block[cnt-1].r+1;
        block[cnt].r=a;
    }
    char ji;
    long long quel,quer,lid,rid,d;
    for(long long i=0;i<b;i++){
        cin>>ji;
        cin>>quel>>quer;
        cin>>d;
        lid=getkuai(quel);
        rid=getkuai(quer);
        if(ji=='M'){
            if(lid==rid){
                for(long long n=quel;n<=quer;n++){
                    c[n]+=d;
                    pai[n]=c[n];
                    block[lid].zhi+=d;
                }
                if(!is_sorted(pai+block[lid].l,pai+block[lid].r+1)) sort(pai+block[lid].l,pai+block[lid].r+1);
            }
            else{
                for(long long n=quel;n<=block[lid].r;n++){
                    c[n]+=d;
                    block[lid].zhi+=d;
                }
                for(long long n=block[lid].l;n<=block[lid].r;n++){
                    pai[n]=c[n];
                }
                if(!is_sorted(pai+block[lid].l,pai+block[lid].r+1)) sort(pai+block[lid].l,pai+block[lid].r+1);
                for(long long n=lid+1;n<rid;n++){
                    block[n].zhi+=meikuai*d;
                    lan[n]+=d;
                }
                for(long long n=block[rid].l;n<=quer;n++){
                    c[n]+=d;
                }
                for(long long n=block[rid].l;n<=block[rid].r;n++){
                    pai[n]=c[n];
                }
                if(!is_sorted(pai+block[rid].l,pai+block[rid].r+1)) sort(pai+block[rid].l,pai+block[rid].r+1);
            }
        }
        else{       
            if(lid==rid){
                sum=0;
                for(long long n=quel;n<=quer;n++){
                    if(c[n]+lan[lid]>=d) sum++; 
                }   
            }
            else{
                sum=0;
                for(long long n=quel;n<=block[lid].r;n++){
                    if(c[n]+lan[lid]>=d) sum++;
                }
                for(long long n=lid+1;n<rid;n++){
                //  if(!is_sorted(pai+block[n].l,pai+block[n].r+1)) sort(pai+block[n].l,pai+block[n].r+1);
                    sum+=block[n].r-(lower_bound(pai+block[n].l,pai+block[n].r+1,d-lan[n])-pai-1);
                } 
                for(long long n=block[rid].l;n<=quer;n++){
                    if(c[n]+lan[rid]>=d) sum++;
                }   
            }
            cout<<sum<<'\n';
        }
    }
    return 0;
}

其实第一个hack调完之后wa了，可能是pai数组的问题，但是懒得一个个看变量，就挑了块长，可以自己照着题解看看写法

by wuhuhuhuhuhuhu @ 2024-10-23 21:48:26

@firefly13163 交上去之后直接a了第一个hack没wa orzorz%%%%%%%%%%%%%

by wuhuhuhuhuhuhu @ 2024-10-24 07:49:43

@firefly13163 忘关注了今早才想起来，我是彩笔orzorz