又是我
拿分块去做P3372,虽然没有被卡常,但是开了O2的运行速度是原来的 6倍左右,为什么这么神奇呢?
代码:
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
long long int data[1000],tag[1000];
int st[1000],ed[1000],belong[500010],size[1000];
int num;
int a[500010];
void init (int n)
{
num = sqrt(n);
for (int i = 1; i <= num; i++)
{
st[i] = n / num * (i - 1) + 1;
ed[i] = n / num * i;
}
ed[num] = n;
for (int i = 1; i <= num; i++)
{
for (int j = st[i]; j <= ed[i]; j++)
{
belong[j] = i;
data[i]+=a[j];
}
size[i] = ed[i] - st[i] + 1;
}
}
void pushdown (int x)
{
for (int i = st[x]; i <= ed[x]; i++)
{
a[i]+=tag[x];
}
tag[x]=0;
}
long long int query (int l,int r)
{
long long int ans=0;
int b=belong[l];
if (l!=st[belong[l]])
{
pushdown(belong[l]);
for (int i=l;i<=min(ed[belong[l]],r);i++)
{
ans+=a[i];
//cerr<<i<<endl;
}
b++;
}
//cerr<<ans<<endl;
int e=belong[r];
if (r!=ed[belong[r]])
{
pushdown(belong[r]);
for (int i=max(st[belong[r]],l);i<=r;i++)
{
ans+=a[i];
//cerr<<i<<endl;
}
e--;
}
//cerr<<ans<<endl;
for (int i=b;i<=e;i++)
{
ans+=data[i];
}
return ans;
}
void add (int l,int r,int x)
{
int b=belong[l];
if (l!=st[belong[l]])
{
for (int i=l;i<=min(ed[belong[l]],r);i++)
{
a[i]+=x;
data[b]+=x;
//cerr<<i<<endl;
}
b++;
}
//cerr<<ans<<endl;
int e=belong[r];
if (r!=ed[belong[r]])
{
for (int i=max(st[belong[r]],l);i<=r;i++)
{
a[i]+=x;
data[e]+=x;
//cerr<<i<<endl;
}
e--;
}
//cerr<<ans<<endl;
for (int i=b;i<=e;i++)
{
data[i]+=size[i]*x;
tag[i]+=x;
}
}
inline int read()
{
char c = getchar();
int x = 0, f = 1;
while (c < '0' || c > '9')
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int main ()
{
int n,m;
cin>>n>>m;
for (int i=1;i<=n;i++)
{
a[i]=read();
}
init(n);
while (m--)
{
int opt=read();
if (opt==1)
{
int x=read(),y=read();
long long int k=read();
add(x,y,k);
}
else
{
int x=read(),y=read();
printf ("%lld\n",query(x,y));
}
/*for (int i=1;i<=num;i++)
cerr<<data[i]<<" ";
cerr<<endl;
for (int i=1;i<=num;i++)
cerr<<tag[i]<<" ";
cerr<<endl;
for (int i=1;i<=n;i++)
cerr<<a[i]<<" ";
cerr<<endl;*/
}
}
我就比较担心联赛上不可O2尝试会不会爆炸啊?
比如CSP-J 2019 我的T4就因为vector
,80->75