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