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

Re:这道题有什么Tricks么

Posted by Exile_oi at 2008-05-08 14:34:59 on Problem 3468
In Reply To:这道题有什么Tricks么 Posted by:Exile_oi at 2008-04-28 19:43:48
用"%I64d"做输入输出啊……很奇怪……一直WA

#include <iostream>
using namespace std;

#define MID(_A, _B) (((_A)+(_B))>>1)

const int MN(100005);

struct Node
{
	int low, high;
	long long sum, delta;
	Node *left, *right;
};

int N, Q, a, b;
long long A[MN], c;
char buf[128];
Node *root;

void BuildTree(Node*& u, int l, int h)
{
	u = new Node((Node){l, h, 0, 0, 0, 0});
	if(l+1 < h)
	{
		BuildTree(u->left, l, MID(l, h));
		BuildTree(u->right, MID(l, h), h);
		u->sum = u->left->sum + u->right->sum;
	}
	else u->sum = A[l];
}

void Divide(Node*& u)
{
	if(u->left) u->left->delta += u->delta;
	if(u->right) u->right->delta += u->delta;
	u->sum += u->delta;
	u->delta = 0;
}

void Maintain(Node*& u)
{
	Divide(u->left);
	Divide(u->right);
	u->sum = u->left->sum + u->right->sum;
}

void Add(Node*& u, int& l, int& h, long long& d)
{
	Divide(u);
	if(l <= u->low && u->high <= h) u->delta += d;
	else
	{
		if(l < MID(u->low, u->high)) Add(u->left, l, h, d);
		if(MID(u->low, u->high) < h) Add(u->right, l, h, d);
		Maintain(u);
	}
}

long long Sum(Node*& u, int& l, int& h)
{
	long long ret(0LL);

	Divide(u);
	if(l <= u->low && u->high <= h) ret = u->sum;
	else
	{
		if(l < MID(u->low, u->high)) ret += Sum(u->left, l, h);
		if(MID(u->low, u->high) < h) ret += Sum(u->right, l, h);
		Maintain(u);
	}

	return ret;
}

int main()
{
	int i;

	scanf("%d %d", &N, &Q);
	for(i = 0; i < N; ++ i) scanf("%I64d", A+i);

	BuildTree(root, 0, N);
	for(gets(buf); Q --;)
	{
		gets(buf);
		if(buf[0] == 'C')
		{
			sscanf(buf+1, "%d %d %I64d", &a, &b, &c);
			Add(root, -- a, b, c);
		}
		else
		{
			sscanf(buf+1, "%d %d", &a, &b);
			printf("%I64d\n", Sum(root, -- a, b));
		}
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator