Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
ACM ICPC 2018 World Finals

挑战上线段树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;
     add(a,b,x,k*2+1,l,(l+r)/2);
     add(a,b,x,k*2+2,(l+r)/2,r);
  }
}

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);
            add(i,i+1,x,0,0,n);
        }
        //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);
                add(l-1,r,x,0,0,n);
            }
            else {
                int l,r;scanf("%d%d",&l,&r);
                printf("%lld\n",sum(l-1,r,0,0,n));
            }
        }
     }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator