hdu 1698 (延迟标记+区间修改+区间求和)
In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.
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
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
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
For each case, print a number in a line representing the total value of the hook after the operations. Use the format in the example.
Sample Input
1
10
2
1 5 2
5 9 3
Sample Output
Case 1: The total value of the hook is 24.
Source
2008 “Sunline Cup” National Invitational Contest
思路:第一个想法是对不同区间的不通材料的分别做判断求和,后来根据lazy标记可以发现,在标记下压的过程中其实已经给区间分类了,膜法
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100000+100;
int sum[maxn<<2],add[maxn<<2];//lazy
void pushup(int rt) {//sum
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int rt,int m) {
if(add[rt]) {
add[rt<<1]=add[rt<<1|1]=add[rt];
sum[rt<<1]=(m-(m>>1))*add[rt];
sum[rt<<1|1]=(m>>1)*add[rt];
add[rt]=0;
}
}
void build(int l,int r,int rt) {
add[rt]=0;
if(l==r) {
sum[rt]=1;
return;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void update(int c,int L,int R,int l,int r,int rt) {
if(L<=l&&r<=R) {
add[rt]=c;
sum[rt]=c*(r-l+1);
return;
}
pushdown(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m) update(c,L,R,l,m,rt<<1);
if(R>m) update(c,L,R,m+1,r,rt<<1|1);
pushup(rt);
}
int main() {
// freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++) {
int n;
scanf("%d",&n);
build(1,n,1);
int m;
scanf("%d",&m);
while(m--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(c,a,b,1,n,1);
}
printf("Case %d: The total value of the hook is %d.\n",i,sum[1]);
}
return 0;
}
最新文章
- Azure机器学习入门(二)创建Azure机器学习工作区
- python之面向对象
- 一步一步开发Game服务器(二)完成登陆,聊天
- Spring MVC 指导文档解读(一)
- 14.quartus联合modelsim仿真
- QString::toWCharArray可以拷贝到宽字符串里
- 部署在IIS服务器的asp.net 网站,禁止访问指定类型文件
- js打印Iframe中的内容,并且不需要预览。
- Bull And Cows
- 福建省队集训被虐记——DAY3
- 使用智能移动设备访问Ossim制
- Java计算字符串中字母出现的次数
- am335x在ubuntu下使用StarterWare编写裸机程序并在CCS中用Jlink调试
- CUDA编程模型之内存管理
- nginx-1-初识nginx
- (转) Let’s make an A3C: Theory
- UVA 10870 Recurrences(矩阵乘法)
- 利用SMB jcifs实现对windows中的共享文件夹的操作
- C程序模拟实现银行家算法
- test examples/test scripts
热门文章
- JS a标签默认鼠标事件,导致无法修改input选中状态
- 一个简单的Quartz定时任务
- .net正则匹配
- Python之字符串方法
- ASP.NET 性能监控工具和优化技巧
- Java中Json字符串转换为对象的方法(多层List集合)
- ubuntu Error fetching https://gems.ruby-china.org/: 	Errno::ECONNREFUSED: Connection refused
- mongo-2ds索引对超过半球范围的适用性测试
- svn初涉及使用
- nginx——优化 Nginx 连接超时时间