結果

問題 No.1099 Range Square Sum
ユーザー snrnsidysnrnsidy
提出日時 2021-05-11 05:52:47
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,863 bytes
コンパイル時間 3,403 ms
コンパイル使用メモリ 205,608 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-21 10:29:09
合計ジャッジ時間 8,609 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge10
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 54 ms
4,348 KB
testcase_12 AC 55 ms
4,348 KB
testcase_13 AC 54 ms
4,348 KB
testcase_14 AC 58 ms
4,348 KB
testcase_15 AC 52 ms
4,348 KB
testcase_16 AC 55 ms
4,348 KB
testcase_17 AC 56 ms
4,348 KB
testcase_18 AC 56 ms
4,348 KB
testcase_19 AC 59 ms
4,348 KB
testcase_20 AC 56 ms
4,348 KB
testcase_21 TLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます

ソースコード

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