玄学,何故无输出

P2801 教主的魔法

出言不逊王子 @ 2021-05-05 09:39:15

#include<bits/stdc++.h>
#define HCL_AK_IOI 114514
#define fs(i,x,y,z) for(register int i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(register int i=x;i>=y;i+=z)
#define int long long
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int N=1000003,inf=0x3f3f3f3f;
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
int o,n,org[N],k,trs[N],add[N],q,s,l[N],r[N],bl[N];
inline void upd(int lll,int rrr,int w){
    fs(i,(l[bl[lll]]==lll?bl[lll]:bl[lll]+1),(r[bl[rrr]]==rrr?bl[rrr]:bl[rrr]-1),1) add[i]+=w;//是不是整块,如果是的话只要加整的
    /*o--- xxxx xxxx -ooo
    那么我们只能对x所在的块进行修改*/
    if(l[bl[lll]]!=lll){//左边的在org单独修改 
        int b=bl[lll];
        fs(i,lll,r[b],1) org[i]+=w,trs[i]=org[i];
        sort(trs+l[b]+1,trs+r[b]+1);
    }
    if(r[bl[rrr]]!=rrr){
        int b=bl[rrr];
        fs(i,l[b],rrr,1) org[i]+=w,trs[i]=org[i];
        sort(trs+l[b]+1,trs+r[b]+1);
    }
}
inline int query(int lll,int rrr,int c){
    int ans=0;
    if(l[bl[lll]]!=lll){//左边的在org单独查询
        int b=bl[lll];
        fs(i,lll,r[b],1) if(org[i]>=c) ans++;
    }
    //printf("!1!%d\n",ans); 
    if(r[bl[rrr]]!=rrr){
        int b=bl[rrr];
        fs(i,l[b],rrr,1) if(org[i]>=c) ans++;
    }
    //printf("!2!%d\n",ans); 
    fs(i,(l[bl[lll]]==lll?bl[lll]:bl[lll]+1),(r[bl[rrr]]==rrr?bl[rrr]:bl[rrr]-1),1){
        int pp=lower_bound(trs+l[i],trs+r[i]+1,c-add[i])-trs;
        if(pp>r[i]) continue;//一个没有啊 
        ans+=r[i]-pp+1;
        //printf("!!%d!!%d %d\n",i,ans,pp);
    }
    printf("%lld\n",ans);
}
signed main(){
    n=read(),q=read();
    k=sqrt(n);
    o=n-k*k;
    fs(i,1,n,1) trs[i]=org[i]=read();
    s=n/k;
    if(o) s++;
    fs(i,1,k,1) sort(trs+(i-1)*k+1,trs+i*k+1);
    fs(i,1,s,1) l[i]=(i-1)*k+1,r[i]=i*k;
//  printf("sample thing:\nk=%d\ns=%d\neach l&r:\n",k,s);
//  fs(i,1,s,1) printf("%d %d\n",l[i],r[i]);
    r[s]=n;
    fs(i,1,n,1) bl[i]=(i-1)/k+1;//,printf("%d ",bl[i]);
    while(q--){
        char op='\0';
        /*do{*/op=getchar();/*}while(op!='A'||op!='M');*/
        int a=read(),b=read(),c=read();
        if(op=='A') query(a,b,c);
        else upd(a,b,c); 
    }
    return 0;
}

by 出言不逊王子 @ 2021-05-05 09:39:48

校内OJ原题是WA,70分


|