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
我也是 应该是lowerbound
和vector
的问题