1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
|
#include<iostream> using namespace std; struct CNode { int L,R; CNode *pLeft,*pRight; long long nSum; long long Inc; }; CNode Tree[200010]; int nCount=0; int Mid(CNode *pRoot) { return (pRoot->L+pRoot->R)/2; } void BuildTree(CNode *pRoot,int L,int R) { pRoot->L=L; pRoot->R=R; pRoot->nSum=0; pRoot->Inc=0; if(L==R) return ; nCount++; pRoot->pLeft=Tree+nCount; nCount++; pRoot->pRight=Tree+nCount; BuildTree(pRoot->pLeft,L,(L+R)/2); BuildTree(pRoot->pRight,(L+R)/2+1,R); } void Insert(CNode *pRoot,int i,int v) { if(pRoot->L==i&&pRoot->R==i) { pRoot->nSum=v; return ; } pRoot->nSum+=v; if(i<=Mid(pRoot)) Insert(pRoot->pLeft,i,v); else Insert(pRoot->pRight,i,v); } void Add(CNode *pRoot,int a,int b,long long c) { if(pRoot->L==a&&pRoot->R==b) { pRoot->Inc+=c; return ; } pRoot->nSum+=c*(b-a+1); if(b<=(pRoot->L+pRoot->R)/2) Add(pRoot->pLeft,a,b,c); else if(a>=(pRoot->L+pRoot->R)/2+1) Add(pRoot->pRight,a,b,c); else { Add(pRoot->pLeft,a,(pRoot->L+pRoot->R)/2,c); Add(pRoot->pRight,(pRoot->L+pRoot->R)/2+1,b,c); } } long long QuerySum(CNode *pRoot,int a,int b) { if(pRoot->L==a&&pRoot->R==b) return pRoot->nSum+(pRoot->R-pRoot->L+1)*pRoot->Inc; pRoot->nSum+=(pRoot->R-pRoot->L+1)*pRoot->Inc; Add(pRoot->pLeft,pRoot->L,Mid(pRoot),pRoot->Inc); Add(pRoot->pRight,Mid(pRoot)+1,pRoot->R,pRoot->Inc); pRoot->Inc=0; if(b<=Mid(pRoot)) return QuerySum(pRoot->pLeft,a,b); else if(a>=Mid(pRoot)+1) return QuerySum(pRoot->pRight,a,b); else { return QuerySum(pRoot->pLeft,a,Mid(pRoot))+QuerySum(pRoot->pRight,Mid(pRoot)+1,b); } } int main() { int n,q,a,b,c; char cmd[10]; scanf("%d %d",&n,&q); int i,j,k; nCount=0; BuildTree(Tree,1,n); for(i=1;i<=n;++i) { scanf("%d",&a); Insert(Tree,i,a); } for(i=0;i<q;++i) { scanf("%s",cmd); if(cmd[0]=='C') { scanf("%d %d %d",&a,&b,&c); Add(Tree,a,b,c); }else{ scanf("%d %d",&a,&b); printf("%I64dn",QuerySum(Tree,a,b)); } } return 0; }
|
近期评论