比赛 |
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;
}