PASCAL:

const
	nmax = 100000;
type
	keytype = int64;
	rangetree = record
		l,r : longint;
		key,delta : keytype;
	end;

var
	cmd : char;
	tree : array[1..nmax+nmax] of rangetree;
	n,q : longint;
	i,a,b,c : longint;
	key : array[1..nmax] of keytype;

procedure maketree(k : longint);
begin
	if tree[k].l < tree[k].r then begin
		tree[k+k].l := tree[k].l; tree[k+k+1].r := tree[k].r;
		tree[k+k].r := (tree[k].l+tree[k].r) shr 1; tree[k+k+1].l := tree[k+k].r+1;
		maketree(k+k); maketree(k+k+1);
		tree[k].key := tree[k+k].key+tree[k+k+1].key;
	end
	else tree[k].key := key[tree[k].l];
end;

procedure settle(k : longint; x : keytype);
begin
	inc(tree[k].key,(tree[k].r-tree[k].l+1)*x); inc(tree[k].delta,x);
end;

procedure refresh(k : longint);
begin
	if tree[k].l <> tree[k].r then begin
		settle(k+k,tree[k].delta); settle(k+k+1,tree[k].delta);
	end;
	tree[k].delta := 0;
end;

procedure modify(k,a,b : longint; c : keytype);
begin
	if (a <= tree[k].r) and (b >= tree[k].l) then begin
		if (a <= tree[k].l) and (b >= tree[k].r) then begin
			settle(k,c);
		end
		else begin
			refresh(k);
			modify(k+k,a,b,c); modify(k+k+1,a,b,c);
			tree[k].key := tree[k+k].key+tree[k+k+1].key;
		end;
	end;
end;

function ask(k,a,b : longint) : keytype;
begin
	if (a > tree[k].r) or (b < tree[k].l) then ask := 0
	else if (a <= tree[k].l) and (b >= tree[k].r) then begin
		ask := tree[k].key;
	end
	else begin
		refresh(k);
		ask := ask(k+k,a,b)+ask(k+k+1,a,b);
	end;
end;

begin
	readln(n,q);
	for i := 1 to n do read(key[i]); readln;
	tree[1].l := 1; tree[1].r := n;
	maketree(1);
	for i := 1 to q do begin
		read(cmd);
		if cmd = 'C' then begin
			readln(a,b,c); modify(1,a,b,c);
		end
		else begin
			readln(a,b); writeln(ask(1,a,b));
		end;
	end;
	close(input); close(output);
end.

GCC:

#include <stdio.h>
#define nmax 150000

typedef long long keytype;
typedef struct sRangeTree
{
	int l,r;
	keytype key,delta;
}rangetree;

int key[nmax],n,q;
rangetree tree[nmax+nmax];
char buffer[255];

void maketree(int k)
{
	if(tree[k].l==tree[k].r)
		tree[k].key=key[tree[k].l];
	else
	{
		tree[k+k].l=tree[k].l; tree[k+k+1].r=tree[k].r;
		tree[k+k].r=(tree[k].l+tree[k].r)>>1; tree[k+k+1].l=tree[k+k].r+1;
		maketree(k+k); maketree(k+k+1);
		tree[k].key=tree[k+k].key+tree[k+k+1].key;
	}
}

void settle(int k,keytype delta)
{
	tree[k].delta+=delta;
	tree[k].key+=delta*(tree[k].r-tree[k].l+1);
}

void refresh(int k)
{
	if(tree[k].l<tree[k].r)
	{
		settle(k+k,tree[k].delta);
		settle(k+k+1,tree[k].delta);
	}
	tree[k].delta=0;
}

void modify(k,a,b,c)
int k,a,b; keytype c;
{
	if(a<=tree[k].r && b>=tree[k].l)
	{
		if(a<=tree[k].l && b>=tree[k].r)
			settle(k,c);
		else
		{
			refresh(k);
			modify(k+k,a,b,c); modify(k+k+1,a,b,c);
			tree[k].key=tree[k+k].key+tree[k+k+1].key;
		}
	}
}

keytype ask(k,a,b)
int k,a,b;
{
	if(a>tree[k].r || b<tree[k].l) return 0;
	if(a<=tree[k].l && b>=tree[k].r) return tree[k].key;
	refresh(k);
	return ask(k+k,a,b)+ask(k+k+1,a,b);
}

int main(int argc, char *argv[])
{
	scanf("%d%d",&n,&q);
	register int i;
	for(i=1; i<=n; scanf("%d",&key[i++]))
		;
	gets(&buffer);
	tree[1].l = 1; tree[1].r = n; maketree(1);
	char cmd; int a,b; keytype c;
	for(i=1; i<=q; i++)
	{
		scanf("%c",&cmd);
		if(cmd=='Q')
		{
			scanf("%d%d",&a,&b); gets(&buffer);
			printf("%lld\n",ask(1,a,b));
		}
		else
		{
			scanf("%d%d%lld",&a,&b,&c); gets(&buffer);
			modify(1,a,b,c);
		}
	}
	fclose(stdin); fclose(stdout);
}

• Re:为什么gcc跑的比Pascal还慢！ (90) indeed 2011-08-02 15:22:21
• Re:为什么gcc跑的比Pascal还慢！ (10) zxd123314 2012-01-29 01:54:29