| ||||||||||
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 |
有没有大佬帮忙看一下怎么WA了#include <stdio.h> #include <stdio.h> #include <stdio.h> #include <iostream> #include <algorithm> #include <string> #define ll long long using namespace std; const int MAXN=100000; struct Node{ int l; int r; ll sum; }; int M,N; Node Tree[MAXN*4]; long long add[MAXN*4]; void build(int l,int r,int k){ Tree[k].l=l; Tree[k].r=r; if (l==r) { cin>>Tree[k].sum; return; } build(l,(l+r)/2, k*2); build((l+r)/2+1,r,k*2+1); Tree[k].sum=Tree[k*2].sum+Tree[k*2+1].sum; } void update(int l,int r,int k,long long v){ if(l<=Tree[k].l&&Tree[k].r>=r){ Tree[k].sum+=(Tree[k].r-Tree[k].l+1)*v; add[k]+=v; return ; } if(add[k]){ int m=Tree[k].r-Tree[k].l+1; //所有子节点要加上add[k]; add[k*2]+=add[k]; add[k*2+1]+=add[k]; Tree[k*2].sum+=(m-m/2)*add[k]; Tree[k*2+1].sum+=(m/2)*add[k]; add[k]=0; } int mid=(Tree[k].r+Tree[k].l)/2; if (r<=mid) { update(l, r, k*2, v); }else if(l>mid){ update(l, r, k*2+1, v); }else{ update(l, mid, k*2, v); update(mid+1, r, k*2+1, v); } Tree[k].sum=Tree[k*2].sum+Tree[k*2+1].sum; } long long query(int l,int r,int k){ if (l<=Tree[k].l&&r>=Tree[k].r) { return Tree[k].sum; } if(add[k]){ int m=Tree[k].r-Tree[k].l+1; //所有子节点要加上add[k]; add[k*2]+=add[k]; add[k*2+1]+=add[k]; Tree[k*2].sum+=(m-m/2)*add[k]; Tree[k*2+1].sum+=(m/2)*add[k]; add[k]=0; } int mid=(Tree[k].l+Tree[k].r)/2; if (r<=mid) { return query(l, r, k*2); }else if(l>mid){ return query(l, r, k*2+1); } return query(l, mid, k*2)+query(mid+1, r, k*2+1); } int main(){ cin>>N>>M; build(1, N, 1); while (M--) { char op; int a,b; ll c; cin>>op>>a>>b; if (op=='Q') { cout<<query(a, b, 1)<<endl; }else if(op=='C'){ cin>>c; update(a, b, 1, c); } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator