背景 Background
AndyBear 生日模拟赛 第一题描述 Description
BIBO是个贪吃的小熊，她有很多喜欢的食物，但是为了控制体重，她每天不能吃的太多，因此小熊BIBO给每一种食物都赋了一个喜欢程度K，BIBO每天 从她所有喜欢的食物中挑出一件喜欢程度最大的来吃，可能是蜂蜜，也可能是面包，同时小熊BIBO还会更改某一种食物的喜欢程度，或者说自己不喜欢某件食物 了。你，作为小熊BIBO的首席大管家，要告诉她今天该吃的是什么。输入格式 InputFormat
输入文件的第一行，给出两个数字N和M，分别表示小熊bibo拥有的食物种类以及操作数量。操作有三种：
Yummy 对于每一个Yummy操作，输出一个数字，表示所有食物中喜欢程度的最大值。
Like 对于每一个Like操作，后面会跟着一个数对x y，表示小熊bibo把第x种食物的喜欢程度改为了y。
Unlike 对于每一个Unlike操作，后面会跟着一个数x，表示小熊bibo不再喜欢第x种食物了，你可以认为这种食物的喜欢程度变成了负无穷。但是请注意，bibo是个善变的小熊，她有可能在之后的某次操作中又喜欢上了这种食物。
输入数据保证，不会出现所有食物都不喜欢的情况。
输出格式 OutputFormat
若干行数字，每一行对应一个Yummy操作的输出。样例输入 SampleInput [复制数据]
10 6
Yummy
Like 5 100
Yummy
Like 6 99
Unlike 5
Yummy
样例输出 SampleOutput [复制数据]
0
100
99
数据范围和注释 Hint
在一开始，所有的食物的喜欢程度都为0。
在数据中，0<=喜欢程度K<=1000000.
对于80%的数据 0<n,m<=1000
对于100%的数据 0<n,m<=100000
思路：两年前做的比赛题了，当时只会暴力，不会线段树
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int maxn=111210;
const int INF=100000000;
int a[maxn<<2],n,m,x,y;
char s[20];
void close()
{
exit(0);
}
void pushup(int rt)
{
a[rt]=max(a[rt<<1],a[rt<<1|1]);
}
void upd(int l,int r,int rt,int x,int y)
{
if (l==x && r==x)
{
a[rt]=y;
return;
}
int mid=(l+r)>>1;
if (l<=x && x<=mid)
upd(lson,x,y);
else
upd(rson,x,y);
pushup(rt);
}
void init()
{
scanf("%d %d",&n,&m);
memset(a,0,sizeof(a));
for (int i=1;i<=m;i++)
{
scanf("%s",s);
if (s[0]=='Y')
printf("%d
",a[1]);
if (s[0]=='L')
{
scanf("%d %d",&x,&y);
upd(1,n,1,x,y);
}
if (s[0]=='U')
{
scanf("%d",&x);
upd(1,n,1,x,-INF);
}
}
}
int main ()
{
init();
close();
return 0;
}