首页 > 代码库 > 1355 巧克力 （线段树点+区间）
1355 巧克力 （线段树点+区间）
继续最水的线段树 简单粗暴
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc p<<1,s,mid
#define rc p<<1|1,mid+1,e
#define mid ((s+e)>>1)
using namespace std;
const int N = 100005;
int add[4 * N], maxv[4 * N];
void pushup(int p)
{
maxv[p] = max(maxv[p << 1], maxv[p << 1 | 1]);
}
void pushdown(int p)
{
add[p << 1] += add[p];
add[p << 1 | 1] += add[p];
maxv[p << 1] += add[p];
maxv[p << 1 | 1] += add[p];
add[p] = 0;
}
void build(int p, int s, int e)
{
add[p] = 0;
if(s == e) scanf("%d", &maxv[p]);
else
{
build(lc);
build(rc);
pushup(p);
}
}
void update(int p, int s, int e, int l, int r, int v, int op)
{
if(s == l && e == r)
{
if(op)
{
add[p] += v;
maxv[p] += v;
}
else maxv[p] = v;
return;
}
pushdown(p);
if(r <= mid) update(lc, l, r, v, op);
else if(l > mid) update(rc, l, r, v, op);
else update(lc, l, mid, v, op), update(rc, mid + 1, r, v, op);
pushup(p);
}
int query(int p, int s, int e, int l, int r)
{
if(s == l && e == r) return maxv[p];
pushdown(p);
if(r <= mid) return query(lc, l, r);
if(l > mid) return query(rc, l, r);
return max(query(lc, l, mid), query(rc, mid + 1, r));
}
int main()
{
int n, m, x, y;
char cmd[10];
while(~scanf("%d%d", &n, &m))
{
build(1, 1, n);
while(m--)
{
scanf("%s", cmd);
if(!strcmp(cmd, "Ask"))
{
scanf("%d", &x);
printf("%d\n", query(1, 1, n, x + 1, x + 1));
continue;
}
scanf("%d%d", &x, &y);
if(cmd[0] == 'Q')
printf("%d\n", query(1, 1, n, x + 1, y + 1));
else if(cmd[0] == 'C')
update(1, 1, n, x + 1, x + 1, y, 0);
else
update(1, 1, n, x + 1, y + 1, 1, 1);
}
}
return 0;
}
1355: 巧克力
Problem Description
TY最喜欢做的事情就是吃巧克力，经常幻想拥有吃不完的巧克力，作为一个acmer(菜机），IcY出了个问题准备考考她，如果回答出来，那巧克力自然是源源不断的啦。
IcY给出了一列排好的的巧克力，有的是德芙，有的是费列罗，它们都拥有不同的美味值……现在IcY通过魔法更改了这些巧克力，TY必须能指出排列中第K个是巧克力的美味值是多少和某一段巧克力中最美味的值是多少，才能吃到巧克力，否则，哼哼，就去乖乖的做题吧。现在，TY来寻求你的帮助，你能让poor TY吃上巧克力吗？
Input
输入数据有很多组，以EOF结尾。
每组数据第一行是2个整数N，M。N代表初始的巧克力数目，M代表操作数。
第二行含有n个正整数，代表每块巧克力的美味值wi。每块巧克力的下标从0--n-1。
接下来的M行，表示M个操作。
操作分4种：
Query x y 代表查询某一个区间内的美味最大值。
Ask x 代表查询某一块巧克力的美味值。
Change x y 代表将第x块的美味值变成y
Add x y 代表讲从第x块到第y块巧克力的美味值分别增加1.
（1 <= N<= 100000 1<= M <= 100000 Wi <= 5000 ）
Output
对于每一个Query输出一个整数，代表区间内的美味最大值。
对于每一个Ask 输出一个整数，代表这块巧克力的美味值。
Sample Input
10 4 1 2 3 4 5 6 7 8 9 10 Ask 0 Change 0 1 Add 0 2 Query 0 2
Sample Output
1 4
1355 巧克力 （线段树点+区间）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。