当然不需要啊。。才$10^{17}$
by SSerxhs @ 2019-04-13 23:38:04
@[kai586123](/space/show?uid=52068)
%DKY
by Sirius_Judson @ 2019-05-07 16:24:22
为什么我swap了还是wa50啊？
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int c[maxn],sum[maxn],n,k,ks[maxn],f[maxn],L[maxn],R[maxn];
int read()
{
int x=0;char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x;
}
void update(int a,int b)
{
int l,r,i,j;
if(ks[a]==ks[b])
{
if(f[ks[a]])return;
for(i=a;i<=b;i++)
{
sum[ks[a]]-=c[i];
c[i]=sqrt(c[i]);
sum[ks[a]]+=c[i];
}
if(sum[ks[a]]==R[ks[a]]-L[ks[a]]+1)f[ks[a]]=1;
return;
}
l=a;r=R[ks[a]];
for(i=l;i<=r;i++)
{
sum[ks[a]]-=c[i];
c[i]=sqrt(c[i]);
sum[ks[a]]+=c[i];
}
if(sum[ks[a]]<=R[ks[a]]-L[ks[a]]+1)f[ks[a]]=1;
l=L[ks[b]];r=b;
for(i=l;i<=r;i++)
{
sum[ks[b]]-=c[i];
c[i]=sqrt(c[i]);
sum[ks[b]]+=c[i];
}
if(sum[ks[b]]<=R[ks[b]]-L[ks[b]]+1)f[ks[b]]=1;
l=ks[a]+1;r=ks[b]-1;
for(i=l;i<=r;i++)
{
if(f[i]==1)continue;
for(j=L[i];j<=R[i];j++)
{
sum[i]-=c[j];
c[j]=sqrt(c[j]);
sum[i]+=c[j];
}
if(sum[i]<=R[i]-L[i]+1)f[i]=1;
}
}
int query(int a,int b)
{
int ans=0,i,l,r;
if(ks[a]==ks[b])
{
for(i=a;i<=b;i++)
ans+=c[i];
}
else
{
l=a;r=R[ks[a]];
for(i=l;i<=r;i++)
ans+=c[i];
// cout<<ans<<endl;
l=L[ks[b]];r=b;
for(i=l;i<=r;i++)
ans+=c[i];
// cout<<ans<<endl;
for(i=ks[a]+1;i<=ks[b]-1;i++)
ans+=sum[i];
}
return ans;
}
int main()
{
int i,j,m,x,y,z;
n=read();k=qsqrt(n);
for(i=1;i<=n;i++)
c[i]=read();
for(i=1;i<=n;i++)
{
ks[i]=(i-1)/k+1;
if(L[ks[i]]==0)L[ks[i]]=i;
R[ks[i]]=i;
sum[ks[i]]+=c[i];
}
m=read();
while(m--)
{
x=read();y=read();z=read();
if(y>z)swap(y,z);
if(x==0)
{
update(y,z);
}
if(x==1)
{
cout<<query(y,z)<<endl;
}
// for(i=1;i<=n;i++)
// cout<<c[i]<<" ";
// cout<<endl;
// for(i=1;i<=n;i++)
// cout<<i<<" "<<ks[i]<<" "<<f[ks[i]]<<" "<<sum[ks[i]]<<endl;
// cout<<endl;
}
}
求各位神佬帮忙看看
by Masky @ 2019-05-17 09:34:10
把swap注释掉了调试没改回来...
by lsy263 @ 2019-07-04 00:20:48
加完全WA才发现写了``if(y>x)swap();``...
by lsy263 @ 2019-07-04 00:23:47
好吧还是50，**要加longlong**
by lsy263 @ 2019-07-04 00:25:37
$orz!!!$
$窝加了swap真过了qwq$
by formkiller @ 2019-10-30 20:35:52