学步园

今天因为电脑被借走了，然后又因为某人要装系统，所以去了机房，参加了这次爆零掉rating的codeforce。

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

__int64 tt[100010];
__int64 t[100010];
__int64 ans[100010];
__int64 sum[100010];
__int64 cnt;

int main()
{
	int n, m, a;
	int type, l, r;
	int i;
	while(~scanf("%d",&n))
	{
		memset(tt, 0, sizeof(tt));
		memset(t, 0, sizeof(t));
		memset(ans, 0, sizeof(ans));
		memset(sum, 0, sizeof(sum));
		ans[0] = 0;
		sum[0] = 0;
		for(i = 1; i <= n; i ++)
		{
			scanf("%d",&tt[i]);
			t[i] = tt[i];
			ans[i] = ans[i - 1] + tt[i];
		}
		sort(t + 1, t + n + 1);
		for(i = 1; i <= n; i ++)
		{
			sum[i] = sum[i - 1] + t[i];
		}
		scanf("%d",&m);
		while(m --)
		{
			scanf("%d%d%d",&type, &l, &r);
			if(type == 1)
			{
				cnt = ans[r] - ans[l - 1];
			}
			else if(type == 2)
			{
				cnt = sum[r] - sum[l - 1];
			}
			printf("%I64d\n",cnt);
		}			
	}
	return 0;
}

下面是拔树的代码

#include<stdio.h>
#include<string.h>
char tt[10005];
int a[10005],ans[10005];
int main()
{
	int n,i,j,l,h,k;
	while(~scanf("%d",&n))
	{
		ans[0]=0;
		int x1=0,x2;
		getchar();
		gets(tt);
		l=strlen(tt);
		for(i=1,k=0;i<l;i++)
		{
			if(tt[i]=='|')
			{
				x2=i;
				a[k++]=x2-x1-1;
				x1=x2;
			}
		}
		ans[1]=a[0];
		for (i=2;i<=k;i++)
			ans[i]=a[i-1]+ans[i-1];
		int max=0;
		for(i=k;i-n>=1;i--)
		{
			h=ans[i]-ans[i-n-1];
			if(h>max)
				max=h;
		}
		printf("%d\n",max);
	}
	return 0;
｝