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

AC代码

Posted by ACINE at 2018-02-27 19:45:20 on Problem 3468
#include<cstdio>
#include<iostream>

#define N 100000
#define ll long long

using namespace std;

char ord;
int n,q;
ll A[N+10];

struct node
{
	int l,r;
	ll sum;
	ll val;
}date[6*N];

void init(int root,int l,int r)
{
	date[root].l=l;
	date[root].r=r;
	
	if(l==r) {
		
		date[root].sum=A[l];
		
		return;
	}
	
	int mid=(l+r)>>1;
	
	init(root*2,l,mid);
	init(root*2+1,mid+1,r);
	
	date[root].sum=date[root*2].sum+date[root*2+1].sum;
}

void update(int root,int a,int b,ll c)
{
	if(date[root].val!=0) {
		
		date[root*2].val+=date[root].val;
		date[root*2+1].val+=date[root].val;
		date[root*2].sum+=date[root].val*(date[root*2].r-date[root*2].l+1);
		date[root*2+1].sum+=date[root].val*(date[root*2+1].r-date[root*2+1].l+1);
		date[root].val=0;
	}
	
	if(date[root].l==a&&date[root].r==b) {
		
		date[root].val=c;
		date[root].sum+=c*(date[root].r-date[root].l+1);
		
		return;
	}
	
	int mid=(date[root].l+date[root].r)>>1;
	
	if(a<=mid&&b<=mid) update(root*2,a,b,c);
	else if(a>mid&&b>mid) update(root*2+1,a,b,c);
	else {
		
		update(root*2,a,mid,c);
		update(root*2+1,mid+1,b,c);
	}
	
	date[root].sum=date[root*2].sum+date[root*2+1].sum;
}

ll query(int root,int a,int b)
{
	if(date[root].val) {
		
		date[root*2].val+=date[root].val;
		date[root*2+1].val+=date[root].val;
		date[root*2].sum+=date[root].val*(date[root*2].r-date[root*2].l+1);
		date[root*2+1].sum+=date[root].val*(date[root*2+1].r-date[root*2+1].l+1);
		date[root].val=0;
	}

	if(date[root].l==a&&date[root].r==b) return date[root].sum;

	int mid=(date[root].l+date[root].r)>>1;
	
	if(a<=mid&&b<=mid) return query(root*2,a,b);
	else if(a>mid&&b>mid) return query(root*2+1,a,b);
	return query(root*2,a,mid)+query(root*2+1,mid+1,b);
}

int main()
{
	scanf("%d%d",&n,&q);
	
	for(int i=1;i<=n;i++)	scanf("%lld",&A[i]);
	
	init(1,1,n);
	
	for(int i=1;i<=q;i++) {
		
		scanf("%s",&ord);
		
		if(ord=='C') {
			
			int a,b;
			ll c;
			
			scanf("%d%d%lld",&a,&b,&c);
			
			update(1,a,b,c);
		}
		else {
			
			int a,b;
			
			scanf("%d%d",&a,&b);
			
			printf("%lld\n",query(1,a,b));
		}
	}
	
	return 0;
}

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