比赛 20110723 评测结果 AAWWWWWW
题目名称 儿童节快乐 最终得分 25
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-23 09:51:33
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=111111;

struct xds
{
	int l,r,c,pos,he;
	xds *cl,*cr;
	xds()
	{
		c=he=0;
	}
	inline void gei()
	{
		c+=he;
		he=0;
	}
	inline void breed()
	{
		if (l==r)
		{
			gei();
			return;
		}
		cl->he+=he;
		cr->he+=he;
		he=0;
	}
	inline void update()
	{
		if (l==r)
		{
			gei();
			return;
		}
		if (cl->c+cl->he>=cr->c+cr->he)
		{
			c=cl->c+cl->he;
			pos=cl->pos;
		}
		else
		{
			c=cr->c+cr->he;
			pos=cr->pos;
		}
	}
}T[MAXN*2],*root=T;

int ps=0,n,m,i,j,k,x,y,ans,ansp;

void mkt(xds *p,int l,int r)
{
	p->l=l;
	p->r=r;
	p->pos=l;
	if (r>l)
	{
		int mid=(l+r)>>1;
		++ps;
		p->cl=T+ps;
		mkt(p->cl,l,mid);
		++ps;
		p->cr=T+ps;
		mkt(p->cr,mid+1,r);
	}
}

void ins(xds *p)
{
	if (p->l>y || p->r<x) return;
	if (p->l>=x && p->r<=y)
	{
		p->he+=k;
		return;
	}
	p->breed();
	ins(p->cl);
	ins(p->cr);
	p->update();
}

void find(xds *p)
{
	if (p->l>y || p->r<x) return;
	if (p->l>=x && p->r<=y)
	{
		if (p->c+p->he>ans)
		{
			ans=p->c+p->he;
			ansp=p->pos;
		}
		return;
	}
	p->breed();
	find(p->cl);
	find(p->cr);
	p->update();
}

void ch(xds *p)
{
	if (p->l>ansp || p->r<ansp) return;
	if (p->l==p->r)
	{
		p->he=p->c=0;
		return;
	}
	p->breed();
	ch(p->cl);
	ch(p->cr);
	p->update();
}

int main()
{
	freopen("happya.in","r",stdin);
	freopen("happya.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	mkt(root,1,n);
	while (m--)
	{
		char op;
		scanf("%c",&op);
		if (op=='I')
		{
			scanf("%d%d%d\n",&x,&y,&k);
			ins(root);
		}
		else
		{
			scanf("%d%d\n",&x,&y);
			ans=0;
			find(root);
			ch(root);
			printf("%d\n",ans);
		}
	}
	return 0;
}