为什么我不开O2第八个点过不去

P2801 教主的魔法

OYBDOOO @ 2019-07-11 00:56:25

蒟弱写的第二个分块题,求助!!!

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
long long aa[1000100];
vector<long long>yu[10005];
int bb[1000100];
long long jia[10005];
int ll[10005];
int rr[10005];
char ss[55];
int n,q;
long long read()
{
    char c=0;
    long long x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        x*=10;
        x+=c-'0';
        c=getchar();
    }
    return x;
}
int main()
{
    int i,j;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++)aa[i]=read();
    int kuan=sqrt(n);
    int ks;
    for(i=1;i<=n;i++)
    {
        bb[i]=(i-1)/kuan+1;
    }
    ks=bb[n];
    for(i=1;i<=n;i++)
    {
        if(bb[i]!=bb[i-1])
        {
            ll[bb[i]]=i;
        }
    }

    for(i=1;i<ks;i++)rr[i]=ll[i+1]-1;
    rr[ks]=n;
//  for(i=1;i<=ks;i++)
//  {
//      cout<<ll[i]<<" "<<rr[i]<<endl;
//  }
    for(i=1;i<=ks;i++)
    {
        for(j=ll[i];j<=rr[i];j++)
            yu[i].push_back(aa[j]);
        sort(yu[i].begin(),yu[i].end());
    }
    int L,R,C;
    for(i=1;i<=q;i++)
    {
        scanf("%s",ss);
        if(ss[0]=='A')
        {
            scanf("%d%d%d",&L,&R,&C);
            int cnt=0;
            int kpp=upper_bound(rr+1,rr+ks+1,L)-rr;
            kpp--;
            for(j=L;j<=rr[kpp];j++)
            {
                if(aa[j]+jia[kpp]>=C)
                    cnt++;
            }
            int kpq=upper_bound(ll+1,ll+ks+1,R)-ll;
            kpq--;
            for(j=ll[kpq];j<=R;j++)
            {
                if(aa[j]+jia[kpq]>=C)
                    cnt++;
            }
            for(j=kpp+1;j<kpq;j++)
            {
                int ksd=lower_bound(yu[j].begin(),yu[j].end(),C-jia[j])-yu[j].begin();
//              int eee=*lower_bound(aa+ll[j]+1,aa+rr[j]+1,C-jia[j]);
//              cout<<"****"<<ksd<<endl;
                cnt+=(yu[j].size()-ksd);
            }
            printf("%d\n",cnt);
        }
        if(ss[0]=='M')
        {
            scanf("%d%d%d",&L,&R,&C);
            int kpp=upper_bound(rr+1,rr+ks+1,L)-rr;
            kpp--;
            for(j=L;j<=rr[kpp];j++)aa[j]+=C;
//          sort(aa+ll[kpp],aa+rr[kpp]+1);
            yu[kpp].clear();
            for(j=ll[kpp];j<=rr[kpp];j++)
                yu[kpp].push_back(aa[j]);
            sort(yu[kpp].begin(),yu[kpp].end());
            int kpq=upper_bound(ll+1,ll+ks+1,R)-ll;
            kpq--;
            for(j=ll[kpq];j<=R;j++)aa[j]+=C;
            yu[kpq].clear();
            for(j=ll[kpq];j<=rr[kpq];j++)
                yu[kpq].push_back(aa[j]);
            sort(yu[kpq].begin(),yu[kpq].end());
            for(j=kpp+1;j<kpq;j++)jia[j]+=C;
        }
    }
    return 0;
}

by wwlw @ 2019-07-11 08:11:22

头像好评


by Explorelore @ 2019-10-07 23:41:47

我也是的,直接交的话第八个点会T,吸口氧就过了。。


by MifuneShioriko @ 2019-11-08 17:53:26

我也是 应该是lowerboundvector的问题


|