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

## 挑战上线段树AC

Posted by MrYX at 2017-03-14 19:28:38 on Problem 3468
```#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=(1<<18)-1;
ll data[N],datb[N];

void add(int a,int b,int x,int k,int l,int r){
if(a<=l&&r<=b) data[k]+=x;
else if(l<b&&a<r){
datb[k]+=(min(b,r)-max(a,l))*x;
}
}

ll sum(int a,int b,int k,int l,int r){
if(b<=l||r<=a) return 0;
else if(a<=l&&r<=b){
return data[k]*(r-l)+datb[k];
}
else{
ll res=data[k]*(min(b,r)-max(a,l));
res+=sum(a,b,k*2+1,l,(l+r)/2);
res+=sum(a,b,k*2+2,(l+r)/2,r);
return res;
}
}

int main(){
int q,n;
while(~scanf("%d %d",&n,&q)){
memset(data,0,sizeof(data));
memset(datb,0,sizeof(datb));
for(int i=0;i<n;i++){
int x;scanf("%d",&x);
}
//cout<<sum(3,4,0,0,n)<<endl;
for(int i=0;i<q;i++){
//getchar();
char c[2];scanf("%s",c);
if(c[0]=='C'){
int l,r,x;scanf("%d%d%d",&l,&r,&x);
}
else {
int l,r;scanf("%d%d",&l,&r);
printf("%lld\n",sum(l-1,r,0,0,n));
}
}
}
}
```

Followed by: