支持区间加法，查区间最大值，单点修改的线段树。

#include<cstdio>
#include<cstring>
const int N=100005;
int n,m;
struct qq
{
	int l,r;
	int s1,s2;
	int z,z1;
	int lazy; 
}s[N*2];
int num;
void bt (int l,int r)
{
	num++;
	int a=num;
	s[a].l=l;s[a].r=r;
	s[a].s1=s[a].s2=-1;
	s[a].z=0;
	s[a].z1=l;
	s[a].lazy=0;
	if (l==r) return ;
	int mid=(l+r)/2;
	s[a].s1=num+1;bt(l,mid);
	s[a].s2=num+1;bt(mid+1,r);
	return ;
}
void add (int now,int l,int r,int c)
{
	if (s[now].l==s[now].r)
	{
		s[now].z+=c;
		return ;
	}
	if (s[now].l==l&&s[now].r==r)
	{
		s[now].lazy+=c;
		s[now].z+=c;
		return ;
	}
	int s1=s[now].s1,s2=s[now].s2;
	s[s1].lazy+=s[now].lazy;
	s[s1].z+=s[now].lazy;
	s[s2].lazy+=s[now].lazy;
	s[s2].z+=s[now].lazy;
	s[now].lazy=0;
	int mid=(s[now].l+s[now].r)/2;
	if (r<=mid) add(s1,l,r,c);
	else if (l>mid) add(s2,l,r,c);
	else
	{
		add(s1,l,mid,c);
		add(s2,mid+1,r,c);
	}
	if (s[s1].z>=s[s2].z)
	{
		s[now].z=s[s1].z;
		s[now].z1=s[s1].z1;
	}
	else
	{
		s[now].z=s[s2].z;
		s[now].z1=s[s2].z1;
	}
	return ;
}
int z,z1;
void find (int now,int l,int r)
{
	if (s[now].l==l&&s[now].r==r)
	{
		z=s[now].z;
		z1=s[now].z1;
		return ;
	}
	int s1=s[now].s1,s2=s[now].s2;
	s[s1].lazy+=s[now].lazy;
	s[s1].z+=s[now].lazy;
	s[s2].lazy+=s[now].lazy;
	s[s2].z+=s[now].lazy;
	s[now].lazy=0;
	int mid=(s[now].l+s[now].r)/2;
	if (r<=mid) find (s1,l,r);
	else if (l>mid) find (s2,l,r);
	else
	{
		find(s1,l,mid);
		int a=z,a1=z1;
		find(s2,mid+1,r);
		if (a>=z)
		{
			z=a;
			z1=a1;
		}
	}
	return ;
}
int main()
{
	while (scanf("%d%d",&n,&m))
	{
	if (n==0&&m==0) break;
	num=0;bt(1,n);
	for (int u=1;u<=m;u++)
	{
		char ss[5];
		scanf("%s",ss);
		if (ss[0]=='I')	
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			add(1,a,b,c);
		}
		else 
		{
			int a,b;
			scanf("%d%d",&a,&b);
			find (1,a,b);
			printf("%d\n",z);
			add(1,z1,z1,-z);
		}
	}
	}
	return 0;
}