Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:我的程序能过，但还是WA

Posted by snow_my_dream at 2015-12-26 11:17:26 on Problem 3468
In Reply To:我的程序能过，但还是WA Posted by:kensin2 at 2008-10-30 11:10:55
```> #include <stdio.h>
> #define N 100000
>
> int n;
> __int64 total;
>
> struct node
> {
> 	__int64 sum;
> };
>
> struct node line_tree[4 * N + 3];
>
> void build_tree(int q, int left, int right);
>
> void update(int q, int left, int right, int li, int ri, int value);
>
> void question(int q, int left, int right, int li, int ri);
>
> int main()
> {
> 	int qn;
> 	int i;
> 	int tmp;
> 	char tc;
>
> 	scanf("%d %d", &n, &qn);
> 	build_tree(0, 1, n);
> 	for (i = 1; i <= n; i++)
> 	{
> 		scanf("%d", &tmp);
> 		update(0, 1, n, i, i, tmp);
> 	}
>
> 	for (i = 0; i < qn; i++)
> 	{
> 		getchar();
> 		scanf("%c", &tc);
> 		if (tc == 'C')
> 		{
> 			scanf("%d %d %d", &begin, &end, &add);
> 			update(0, 1, n, begin, end, add);
> 		}
> 		else
> 		{
> 			scanf("%d %d", &begin, &end);
> 			total = 0;
> 			question(0, 1, n, begin, end);
> 			printf("%I64d\n", total);
> 		}
> 	}
>
> 	return 0;
> }
>
> void build_tree(int q, int left, int right)
> {
> 	int mid = (left + right) >> 1;
>
> 	line_tree[q].sum = 0;
>
> 	if (left < right)
> 	{
> 		build_tree(q * 2 + 1, left, mid);
> 		build_tree(q * 2 + 2, mid + 1, right);
> 	}
> }
>
> void update(int q, int left, int right, int li, int ri, int value)
> {
> 	int mid = (left + right) >> 1;
>
> 	if (left == li && right == ri)
> 	{
> 		line_tree[q].sum += (ri - li + 1) * value;
>
> 		return;
> 	}
>
> 	line_tree[q].sum += (ri - li + 1) * value;
>
> 	if (li <= mid)
> 	{
> 		if (ri <= mid)
> 		{
> 			update(q * 2 + 1, left, mid, li, ri, value);
> 		}
> 		else
> 		{
> 			update(q * 2 + 1, left, mid, li, mid, value);
> 			update(q * 2 + 2, mid + 1, right, mid + 1, ri, value);
> 		}
> 	}
> 	else
> 		update(q * 2 + 2, mid + 1, right, li, ri, value);
> }
>
> void question(int q, int left, int right, int li, int ri)
> {
> 	int mid = (left + right) >> 1;
>
> 	if (left == li && right == ri)
> 	{
> 		total += line_tree[q].sum;
> 		return;
> 	}
>
> 		total += line_tree[q].addPerElmt * (ri - li + 1);
>
> 	if (li <= mid)
> 	{
> 		if (ri <= mid)
> 		{
> 			question(q * 2 + 1, left, mid, li, ri);
> 		}
> 		else
> 		{
> 			question(q * 2 + 1, left, mid, li, mid);
> 			question(q * 2 + 2, mid + 1, right, mid + 1, ri);
> 		}
> 	}
> 	else
> 		question(q * 2 + 2, mid + 1, right, li, ri);
> }
```

Followed by: