WA求助,清零了,样例过了
查看原帖
WA求助,清零了,样例过了
125018
ztx__楼主2020/8/15 10:19

rt,双倍经验AC了,这道题WA了。。。请大佬们帮忙审一下代码吧,写的分块

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXSQRTN 320
typedef long long ll;
int n,m,sqrtn;
ll a[MAXN];
int belong[MAXN],l[MAXSQRTN],r[MAXSQRTN],block_cnt;
bitset<MAXN> vis;
ll block[MAXSQRTN];
void init(){
    vis=0;
    memset(belong,0,sizeof(belong));
    memset(block,0,sizeof(block));
    memset(l,0,sizeof(l));
    //memset(a,0,sizeof(a));
    memset(r,0,sizeof(r));
    block_cnt=0;
}
void build(){
    block_cnt=sqrtn;
    for(int i=1;i<=sqrtn;i++){
        l[i]=r[i-1]+1;
        r[i]=l[i]+sqrtn-1;
        for(int j=l[i];j<=r[i];j++){
            block[i]+=a[j];
            belong[j]=i;
        }
    }
    if(r[block_cnt]!=n){
        block_cnt+=1;
        l[block_cnt]=r[block_cnt-1]+1;
        r[block_cnt]=n;
        for(int i=l[block_cnt];i<=r[block_cnt];i++){
            block[block_cnt]+=a[i];
            belong[i]=block_cnt;
        }
    }
}
ll query(int L,int R){
    ll ret=0;
    if(belong[L]==belong[R]){
        for(int i=L;i<=R;i++){
            ret+=a[i];
        }
        return ret;
    }
    if(L!=l[belong[L]]){
        for(int i=L;i<=r[belong[L]];i++){
            ret+=a[i];
        }
        L=l[belong[L]+1];
    }
    if(R!=r[belong[R]]){
        for(int i=R;i>=l[belong[R]];i--){
            ret+=a[i];
        }
        R=r[belong[R]-1];
    }
    for(int i=belong[L];i<=belong[R];i++){
        ret+=block[i];
    }
    return ret;
}
void modify(int L,int R){
    if(belong[L]==belong[R]){
        if(!vis[belong[L]]){
            for(int i=L;i<=R;i++){
                ll tmp=a[i];
                a[i]=sqrt(a[i]);
                block[belong[L]]-=tmp-a[i];
            }
        }
    }else{
        if(L!=l[belong[L]]){
            if(!vis[belong[L]]){
                for(int i=L;i<=r[belong[L]];i++){
                    ll tmp=a[i];
                    a[i]=sqrt(a[i]);
                    block[belong[L]]-=tmp-a[i];
                }
            }
            L=l[belong[L]+1];
        }
        if(R!=r[belong[R]]){
            if(!vis[belong[L]]){
                for(int i=R;i>=l[belong[R]];i--){
                    ll tmp=a[i];
                    a[i]=sqrt(a[i]);
                    block[belong[R]]-=tmp-a[i];
                }
            }
            R=r[belong[R]-1];
        }
        for(int i=belong[L];i<=belong[R];i++){
            if(!vis[i]){
                vis[i]=true;
                for(int j=l[i];j<=r[i];j++){
                    ll tmp=a[j];
                    a[j]=sqrt(a[j]);
                    if(a[j]>1){
                        vis[i]=false;
                    }
                    block[i]-=tmp-a[j];
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    int fuck=0;
    while(cin.good()){
        cin>>n;
        sqrtn=sqrt(n);
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        if(!cin.good()){
            exit(0);
        }
        init();
        build();
        cin>>m;
        cout<<"Case #"<<++fuck<<":"<<endl;
        for(int i=1;i<=m;i++){
            int op,l,r;
            cin>>op>>l>>r;
            if(l>r)swap(l,r);
            if(op==0){
                modify(l,r);
            }else if(op==1){
                cout<<query(l,r)<<endl;
            }
        }
    }
    return 0;
}
2020/8/15 10:19
加载中...