| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:这道题有什么Tricks么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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator