又是我

拿分块去做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