50pts WA求调

TempestJueMu @ 2022-09-06 16:38:23

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=1000010,B=1010;
int n,q;
int a[N],b[N];
int bl,st[B],ed[B],bel[N],siz[B],tag[B];
void build()
{
    bl=sqrt(n);
    fo(i,1,bl)
        st[i]=n/bl*(i-1)+1,
        ed[i]=n/bl*i,
        siz[i]=ed[i]-st[i]+1;
    ed[bl]=n;
    siz[bl]=ed[bl]-st[bl]+1;
    fo(i,1,bl)
    {
        fo(j,st[i],ed[i])
            bel[j]=i,b[j]=a[j];
        sort(b+st[i],b+ed[i]+1);
    }
}
void add(int l,int r,int k)
{
    if(bel[r]-bel[l]<=1)
    {
        fo(i,l,r)
            a[i]+=k;
        fo(i,st[l],ed[r])
            b[i]=a[i];
        sort(b+st[l],b+st[l]+1);
        sort(b+st[r],b+st[r]+1);
        return;
    }
    fo(i,bel[l]+1,bel[r]-1)tag[i]+=k;
    fo(i,l,ed[bel[l]])a[i]+=k;
    fo(i,st[bel[r]],r)a[i]+=k;
    fo(i,st[l],ed[l])b[i]=a[i];
    fo(i,st[r],ed[r])b[i]=a[i];
    sort(b+st[l],b+ed[l]+1);
    sort(b+st[r],b+ed[r]+1);
}
int query(int l,int r,int c)
{
    int ans=0;
    if(bel[r]-bel[l]<=1)
    {
        fo(i,l,r)ans+=(a[i]+tag[bel[i]]>=c);
        return ans;
    }
    fo(i,bel[l]+1,bel[r]-1)
    {
        int f=lower_bound(b+st[bel[i]],b+1+ed[bel[i]],c-tag[i])-b;
        ans+=ed[bel[i]]-(f-st[bel[i]]+1)+1;
    }
    fo(i,l,ed[bel[l]])ans+=(a[i]+tag[bel[i]]>=c);
    fo(i,st[bel[r]],r)ans+=(a[i]+tag[bel[i]]>=c);
    return ans;
}
int main()
{
    cin>>n>>q;
    fo(i,1,n)cin>>a[i];
    build();
    char op;int l,r,x;
    fo(i,1,q)
    {
        cin>>op>>l>>r>>x;
        if(op=='M')add(l,r,x);
        if(op=='A')cout<<query(l,r,x)<<'\n';
    }
    return 0;
}

by TempestJueMu @ 2022-09-06 16:45:45

一下午都没调出来/kel

by NATURAL6 @ 2022-09-07 17:47:06

话说这为什么没RE

by NATURAL6 @ 2022-09-07 18:33:54

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=1000010,B=1010;
int n,q;
int a[N],b[N];
int bl,st[B],ed[B],bel[N],siz[B],tag[B];
void build()
{
    bl=sqrt(n);
    fo(i,1,bl)//这个括号没加 
        st[i]=n/bl*(i-1)+1,
        ed[i]=n/bl*i,
        siz[i]=ed[i]-st[i]+1;
    ed[bl]=n;
    siz[bl]=ed[bl]-st[bl]+1;
    fo(i,1,bl)
    {
        fo(j,st[i],ed[i])
            bel[j]=i,b[j]=a[j];
        sort(b+st[i],b+ed[i]+1);
    }
}
void add(int l,int r,int k)
{
    if(bel[r]-bel[l]<=1)
    {
        fo(i,l,r)
            a[i]+=k;
        fo(i,st[l],ed[r])//这里写法有大问题吧 ，没加bel[] 
            b[i]=a[i];
        sort(b+st[l],b+st[l]+1);
        sort(b+st[r],b+st[r]+1);
        return;
    }
    fo(i,bel[l]+1,bel[r]-1)tag[i]+=k;
    fo(i,l,ed[bel[l]])a[i]+=k;
    fo(i,st[bel[r]],r)a[i]+=k;
    fo(i,st[l],ed[l])b[i]=a[i];
    fo(i,st[r],ed[r])b[i]=a[i];
    sort(b+st[l],b+ed[l]+1);//没加bel[] 
    sort(b+st[r],b+ed[r]+1);
}
int query(int l,int r,int c)
{
    int ans=0;
    if(bel[r]-bel[l]<=1)
    {
        fo(i,l,r)ans+=(a[i]+tag[bel[i]]>=c);
        return ans;
    }
    fo(i,bel[l]+1,bel[r]-1)
    {
        int f=lower_bound(b+st[bel[i]],b+1+ed[bel[i]],c-tag[i])-b;
        ans+=ed[bel[i]]-(f-st[bel[i]]+1)+1;//这个ed应该是siz吧 
    }
    fo(i,l,ed[bel[l]])ans+=(a[i]+tag[bel[i]]>=c);
    fo(i,st[bel[r]],r)ans+=(a[i]+tag[bel[i]]>=c);
    return ans;
}
int main()
{
    cin>>n>>q;
    fo(i,1,n)cin>>a[i];
    build();
    char op;int l,r,x;
    fo(i,1,q)
    {
        cin>>op>>l>>r>>x;
        if(op=='M')add(l,r,x);
        if(op=='A')cout<<query(l,r,x)<<'\n';
    }
    return 0;
}

by TempestJueMu @ 2022-09-07 23:23:02

@NATURAL6 thx,已经打废了