原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1698
Just a Hook
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 17134 Accepted Submission(s): 8555
Problem Description
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.
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.
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
Recommend
分析:用线段树,区间更新。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define MAXN 100010 int sum[4*MAXN],lazy[4*MAXN]; int t,n,op,x,y,z,total; void build(int r,int L,int R){ if(L==R) sum[r] = 1; else{ int M = (L+R)/2; build(r*2,L,M); build(r*2+1,M+1,R); sum[r] = sum[r*2] + sum[r*2+1]; } } void push_up(int r,int L,int R) { if(lazy[r]>0) sum[r] = lazy[r]*(R-L+1); else sum[r] = sum[r*2] + sum[r*2+1]; } void push_down(int r) { if(lazy[r]>0) { lazy[r*2] = lazy[r*2+1] = lazy[r]; lazy[r] = 0; } } void update(int r,int L,int R,int x,int y,int z) { if(x<=L&&R<=y) { lazy[r] = z; sum[r] = z*(R-L+1); } else { push_down(r); int M = (L+R)/2; if(x<=M) update(r*2,L,M,x,y,z); else push_up(r*2,L,M); if(y>M) update(r*2+1,M+1,R,x,y,z); else push_up(r*2+1,M+1,R); push_up(r,L,R); } } void query(int r, int L,int R,int ql,int qr) { if(lazy[r]>0) total+=lazy[r]*(min(qr,R)-max(ql,L)+1); else if(ql<=L&&R<=qr) total += sum[r]; else { int M = (L+R)/2; if(ql<=M) query(r*2,L,M,ql,qr); if(qr>M) query(r*2+1,M+1,R,ql,qr); } } int main() { scanf("%d",&t); int k = 1; while(t--) { memset(lazy,0,sizeof(lazy)); lazy[1] = 1; total = 0; scanf("%d%d",&n,&op); build(1,1,n); while(op--) { scanf("%d%d%d",&x,&y,&z); update(1,1,n,x,y,z); } query(1,1,n,1,n); printf("Case %d: The total value of the hook is %d.\n",k++,total); } return 0; }
相关推荐
Hdu 1698 Just a Hook 是另一个典型的线段树题目,题目要求我们实现一个数据结构来维护一个数组的区间信息。 Hdu 3584 Cube Hdu 3584 Cube 是一个三维线段树题目,题目要求我们实现一个三维线段树来维护一个三维...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
- 这个函数接收两个字符串参数`a`和`b`,代表两个待相加的大整数,以及一个整数`fn`作为结果存放的位置索引。 - 函数内部首先计算两个数的长度,然后进行逐位相加,同时考虑进位的情况。 - 结果存储在一个临时的`...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
hdu2101AC代码
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...
hdu_2102_passed_sorce
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...