結果

問題 No.1099 Range Square Sum
コンテスト
ユーザー snrnsidy
提出日時 2021-05-11 05:52:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,863 bytes
コンパイル時間 2,000 ms
コンパイル使用メモリ 197,704 KB
最終ジャッジ日時 2025-01-21 10:00:50
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector <long long int> v;

long long int init(int node, int start, int end, vector<long long>& tree)
{
	if (start == end)
	{
		return tree[node] = v[start];
	}
	else
	{
		int mid = (start + end) / 2;
		return tree[node] = init(node * 2, start, mid, tree) + init(node * 2 + 1, mid + 1, end, tree);
	}
}

long long int init2(int node, int start, int end, vector<long long>& tree)
{
	if (start == end)
	{
		return tree[node] = v[start]*v[start];
	}
	else
	{
		int mid = (start + end) / 2;
		return tree[node] = init2(node * 2, start, mid, tree) + init2(node * 2 + 1, mid + 1, end, tree);
	}
}

void lazy(int node, int start, int end, vector<long long>& tree, vector<long long>& l)
{
	if (l[node] != 0)
	{
		tree[node] += (end - start + 1) * l[node];
		if (start != end)
		{
			l[node * 2] += l[node];
			l[node * 2 + 1] += l[node];
		}
		l[node] = 0;
	}
}

void update(int node, int start, int end, int left, int right, long long int diff, vector<long long>& tree, vector<long long>& l)
{
	lazy(node, start, end, tree, l);
	if (left > end || right < start)
	{
		return;
	}

	if (left <= start && end <= right)
	{
		tree[node] += (end - start + 1) * diff;
		if (start != end)
		{
			l[node * 2] += diff;
			l[node * 2 + 1] += diff;
		}
		return;
	}
	int mid = (start + end) / 2;
	update(node * 2, start, mid, left, right, diff, tree, l);
	update(node * 2 + 1, mid + 1, end, left, right, diff, tree, l);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

long long int sum(int node, int start, int end, int left, int right, vector<long long>& tree, vector<long long>& l)
{
	lazy(node, start, end,tree,l);
	if (left > end || right < start)
	{
		return 0;
	}

	if (left <= start && end <= right)
	{
		return tree[node];
	}

	int mid = (start + end) / 2;
	return sum(node * 2, start, mid, left, right,tree,l) + sum(node * 2 + 1, mid + 1, end, left, right,tree,l);
}

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, q;
	int h, size;
	cin >> n;
	h = (int)ceil(log2(n + 100));
	size = (1 << (h + 1)) - 1;
	vector <long long int> tree,tree2;
	vector <long long int> l,l2;
	v.resize(n);
	tree.resize(size);
	l.resize(size);
	tree2.resize(size);
	l2.resize(size);
	
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}
	init(1, 0, n - 1,tree);
	init2(1, 0, n - 1, tree2);
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		int mode, a, b;
		long long int d;
		cin >> mode;
		if (mode == 1)
		{
			cin >> a >> b >> d;
			a -= 1;
			b -= 1;
			long long int len = b - a + 1;
			for (int j = a; j <= b; j++)
			{
				long long int add = 2 * d * sum(1, 0, n - 1, j, j, tree, l);
				add += (d * d);
				update(1, 0, n - 1, j, j, add, tree2, l2);
			}
			update(1, 0, n - 1, a, b, d,tree,l);
		}
		else
		{
			cin >> a >> b;
			a -= 1;
			b -= 1;
			cout << sum(1, 0, n - 1, a, b,tree2,l2) << '\n';
		}
	}

	return 0;
}
0