题目链接:hdu 1698 Just a Hook
题目大意:给定N,表示钩子的长度,铜色的位置增加伤害1,银色的位置增加伤害2,金色伤害3,初始均为铜色,现在给出Q次修改,每次将区间l,r的钩子变成v。输出最后钩子的总伤害。
解题思路:线段树,区间修改,对每个节点开一个v和s,v表示修改值,s表示区间的伤害加成。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100005;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
struct Node {
int l, r, v, s;
void set (int l, int r, int v, int s) {
this->l = l;
this->r = r;
this->v = v;
this->s = s;
}
void maintain (int x) {
v = x;
s = (r - l + 1) * x;
}
}nd[maxn * 4];
int N, Q;
void pushup (int u) {
nd[u].s = nd[lson(u)].s + nd[rson(u)].s;
if (nd[lson(u)].v == nd[rson(u)].v)
nd[u].v = nd[lson(u)].v;
else
nd[u].v = 0;
}
void pushdown(int u) {
if (nd[u].v) {
nd[lson(u)].maintain(nd[u].v);
nd[rson(u)].maintain(nd[u].v);
nd[u].v = 0;
}
}
void build (int u, int l, int r) {
nd[u].set(l, r, 1, r - l + 1);
if (l == r)
return;
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
}
void modify (int u, int l, int r, int x) {
if (l <= nd[u].l && nd[u].r <= r) {
nd[u].maintain(x);
return;
}
pushdown(u);
int mid = (nd[u].l + nd[u].r) / 2;
if (l <= mid)
modify(lson(u), l, r, x);
if (r > mid)
modify(rson(u), l, r, x);
pushup(u);
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
scanf("%d", &N);
build(1, 1, N);
int l, r, v;
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
scanf("%d%d%d", &l, &r, &v);
modify(1, l, r, v);
}
printf("Case %d: The total value of the hook is %d.\n", kcas, nd[1].s);
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
NULL 博文链接:https://128kj.iteye.com/blog/1738772
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门