分块TLE50pts求调

Z_X_D_ @ 2023-09-27 09:18:22

#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define M 10010
#define otto auto
using namespace std;
int a[N],st[M],e[M],det[M],bl[M],t[N];
template <typename Tp>
void read(Tp &x)
{
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
void fr(char &x)
{
    x=0;while(x!='M'&&x!='A') x=getchar();
}
void Sort(int k)
{
    for(int i=st[k];i<=e[k];i++)
        t[i]=a[i];
    sort(t+st[k],t+e[k]+1);
}
void mdf(int l,int r,int c)
{
    int i,x=bl[l],y=bl[r];
    if(x==y)
    {
        for(i=l;i<=r;i++)
            a[i]+=c;
        Sort(x);
        return;
    }
    for(i=l;i<=e[x];i++)a[i]+=c;
    for(i=st[y];i<=r;i++)a[i]+=c;
    for(i=x+1;i<y;i++)det[i]+=c;
    Sort(x);
    Sort(y); 
}
int asw(int l,int r,int c)
{
    int i,ans=0,x=bl[l],y=bl[r];
    if(x==y)
    {
        for(i=l;i<=r;i++)
            if(a[i]+det[x]>=c)ans++;
        return ans;
    }
    for(i=l;i<=e[x];i++)
        if(a[i]+det[x]>=c)ans++;
    for(i=st[y];i<=r;i++)
        if(a[i]+det[y]>=c)ans++;
    for(i=x+1;i<y;i++)
        ans+=e[i]-(lower_bound(t+st[i],t+e[i]+1,c-det[i])-t)+1;
    return ans;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","r",stdin);
    int i,j,n,q,num,x,y,z;
    char op;
    read(n),read(q);
    num=sqrt(n)+1;
    for(i=1;i<=n;i++)read(a[i]),t[i]=a[i];
    for(i=1;i<=num;i++)
    {
        st[i]=n/num*(i-1)+1;
        e[i]=n/num*i;
    }
    e[num]=n;
    for(i=1;i<=num;i++)
    {
        for(j=st[i];j<=e[i];j++)
            bl[j]=i;
//      sz[i]=e[i]-st[i]+1;
        sort(t+st[i],t+e[i]+1);
    }
    while(q--)
    {
        fr(op);
        read(x),read(y),read(z);
        if(op=='M')
            mdf(x,y,z);
        if(op=='A')
            printf("%d\n",asw(x,y,z));
    }
    return 0;
}

by _Regenbogen_ @ 2023-09-27 10:09:02

@Z_XD 宁.....数组开小了

by _Regenbogen_ @ 2023-09-27 10:09:46

过了

#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define M 10010
#define otto auto
using namespace std;
int a[N],st[N],e[N],det[N],bl[N],t[N];
template <typename Tp>
void read(Tp &x)
{
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')){
        ch=getchar();
    }
    if(ch=='-'){
        fh=-1;ch=getchar();
    }else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    x*=fh;
}
void fr(char &x)
{
    x=0;while(x!='M'&&x!='A') x=getchar();
}
void Sort(int k)
{
    for(int i=st[k];i<=e[k];i++)
        t[i]=a[i];
    sort(t+st[k],t+e[k]+1);
}
void mdf(int l,int r,int c)
{
    int i,x=bl[l],y=bl[r];
    if(x==y)
    {
        for(i=l;i<=r;i++)
            a[i]+=c;
        Sort(x);
        return;
    }
    for(i=l;i<=e[x];i++)a[i]+=c;
    for(i=st[y];i<=r;i++)a[i]+=c;
    for(i=x+1;i<y;i++)det[i]+=c;
    Sort(x);
    Sort(y); 
}
int asw(int l,int r,int c)
{
    int i,ans=0,x=bl[l],y=bl[r];
    if(x==y)
    {
        for(i=l;i<=r;i++)
            if(a[i]+det[x]>=c)ans++;
        return ans;
    }
    for(i=l;i<=e[x];i++)
        if(a[i]+det[x]>=c)ans++;
    for(i=st[y];i<=r;i++)
        if(a[i]+det[y]>=c)ans++;
    for(i=x+1;i<y;i++)
        ans+=e[i]-(lower_bound(t+st[i],t+e[i]+1,c-det[i])-t)+1;
    return ans;
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","r",stdin);
    int i,j,n,q,num,x,y,z;
    char op;
    read(n),read(q);
    num=sqrt(n)+1;
    for(i=1;i<=n;i++)read(a[i]),t[i]=a[i];
    for(i=1;i<=num;i++)
    {
        st[i]=n/num*(i-1)+1;
        e[i]=n/num*i;
    }
    e[num]=n;
    for(i=1;i<=num;i++)
    {
        for(j=st[i];j<=e[i];j++)
            bl[j]=i;
//      sz[i]=e[i]-st[i]+1;
        sort(t+st[i],t+e[i]+1);
    }
    while(q--)
    {
        fr(op);
        read(x),read(y),read(z);
        if(op=='M')
            mdf(x,y,z);
        if(op=='A')
            printf("%d\n",asw(x,y,z));
    }
    return 0;
}

by _Regenbogen_ @ 2023-09-27 10:10:34

@Z_XD 确实不会T

by Z_X_D_ @ 2023-09-27 10:14:57

@Regenbogen az，才看到bl要开1e6蚌不住了，谢谢您（