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

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

Posted by kensin2 at 2008-10-30 11:10:55 on Problem 3468
In Reply To:给一个线段树容易出错的测试用例 Posted by:fanlonglong8500 at 2008-08-25 10:54:41
```#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;
int begin, end, add;

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: