HDU1698(KB7-E 线段树)
Just a Hook
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34362 Accepted Submission(s): 16774
Problem Description
Now Pudge wants to do some operations on the hook.
Let us number the consecutive metallic sticks of the hook from 1 to N. For each operation, Pudge can change the consecutive metallic sticks, numbered from X to Y, into cupreous sticks, silver sticks or golden sticks.
The total value of the hook is calculated as the sum of values of N metallic sticks. More precisely, the value for each kind of stick is calculated as follows:
For each cupreous stick, the value is 1.
For each silver stick, the value is 2.
For each golden stick, the value is 3.
Pudge wants to know the total value of the hook after performing the operations.
You may consider the original hook is made up of cupreous sticks.
Input
For each case, the first line contains an integer N, 1<=N<=100,000, which is the number of the sticks of Pudge’s meat hook and the second line contains an integer Q, 0<=Q<=100,000, which is the number of the operations.
Next Q lines, each line contains three integers X, Y, 1<=X<=Y<=N, Z, 1<=Z<=3, which defines an operation: change the sticks numbered from X to Y into the metal kind Z, where Z=1 represents the cupreous kind, Z=2 represents the silver kind and Z=3 represents the golden kind.
Output
Sample Input
10
2
1 5 2
5 9 3
Sample Output
Source
//2017-08-11
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson (id<<1)
#define rson ((id<<1)|1)
#define mid ((tree[id].l+tree[id].r)>>1) using namespace std; const int N = ;
struct Node{
int l, r, sum, lazy;
}tree[N<<]; void build(int id, int l, int r){
tree[id].l = l;
tree[id].r = r;
tree[id].lazy = ;
if(l == r){
tree[id].sum = ;
return;
}
build(lson, l, mid);
build(rson, mid+, r);
tree[id].sum = tree[lson].sum + tree[rson].sum;
} void push_down(int id){
tree[id].sum = (tree[id].r-tree[id].l+)*tree[id].lazy;
tree[lson].lazy = tree[id].lazy;
tree[rson].lazy = tree[id].lazy;
tree[id].lazy = ;
} void update(int id, int l, int r, int val){
if(tree[id].lazy)push_down(id);
if(tree[id].l == l && tree[id].r == r){
tree[id].sum = (r-l+)*val;
tree[id].lazy = ;
tree[lson].lazy = val;
tree[rson].lazy = val;
return;
}
if(l > mid)update(rson, l, r, val);
else if(r <= mid)update(lson, l, r, val);
else{
update(lson, l, mid, val);
update(rson, mid+, r, val);
}
if(tree[lson].lazy)push_down(lson);
if(tree[rson].lazy)push_down(rson);
tree[id].sum = tree[lson].sum + tree[rson].sum;
} int query(int id, int l, int r){
if(tree[id].l == l && tree[id].r == r){
return tree[id].sum;
}
if(l > mid)return query(rson, l, r);
else if(r <= mid)return query(lson, l, r);
else return query(lson, l, mid)+query(rson, mid+, r);
} int main()
{
int T, n, kase = ;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
build(, , n);
int m, l, r, z;
scanf("%d", &m);
while(m--){
scanf("%d%d%d", &l, &r, &z);
update(, l, r, z);
}
printf("Case %d: The total value of the hook is %d.\n", ++kase, query(, , n));
} return ;
}
最新文章
- css知识点整理
- SAP Query工具(一 Overview)
- 深入分析MVC中通过IOC实现Controller依赖注入的原理
- js注入
- Java框架篇---Mybatis 构建SqlSessionFactory
- 转载总结 C# 多态(虚方法,抽象,接口实现)
- EventBus3 简单使用及注意点
- UVA 10375 Choose and divide
- [学习笔记]js动画实现方法,作用域,闭包
- Apache+Tomcat部署负载均衡(或集群)
- 命令行利用KVM创建虚拟机
- Linux 网络管理、软件包安装
- windows端ndk 编译.c/cpp文件生成so库示例
- vue2.0中使用sass
- WinCHM 制作开发知识库,So easy!!!
- 70. Climbing Stairs爬楼梯
- JQuery选择器和DOM的操作-入门学习
- 数学图形(2.17)pappus螺线
- python数据类型二
- robot framework连接Oracle错误:ORA-12504: TNS:listener was not given the SERVICE_NAME in CONNECT_DATA