Just a Hook
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16232 Accepted Submission(s): 8075
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.
题意:
给出 T 组 case,后给出 N(1 ~ 100000) ,代表有 N 个为 1 的数,后给出 M,代表有 M 个操作,每个操作有 l,r,ans,代表将 l 到 r 区间的数变为 ans,在处理完所有操作之后,输出整个序列和的结果。
思路:
线段树 + 区间更新。延迟标记记录每段变为 ans 时候的值,理解了新的写法。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 100000 * 5; int tree[MAX], mark[MAX]; void pushup (int node) { tree[node] = tree[node << 1] + tree[node << 1 | 1]; } void pushdown (int node, int l, int r) { if (mark[node]) { int mid = (r + l) >> 1; mark[node << 1] = mark[node]; mark[node << 1 | 1] = mark[node]; tree[node << 1] = (mid - l + 1) * mark[node]; tree[node << 1 | 1] = (r - mid) * mark[node]; mark[node] = 0; } } void build (int node, int l, int r) { int mid = (l + r) >> 1; if (l == r) { tree[node] = 1; mark[node] = 0; } else { build(node << 1, l, mid); build(node << 1 | 1, mid + 1, r); pushup(node); mark[node] = 0; } } void update (int node, int l, int r, int cl, int cr, int num) { if (cl > r || cr < l) return; if (cl <= l && cr >= r) { mark[node] = num; tree[node] = (r - l + 1) * num; return; } pushdown(node, l, r); int mid = (r + l) >> 1; update(node << 1, l, mid, cl, cr, num); update(node << 1 | 1, mid + 1, r, cl, cr, num); pushup(node); } int main() { int t; scanf("%d", &t); for (int tt = 1; tt <= t; ++tt) { int n; scanf("%d", &n); build(1, 1, n); int m; scanf("%d", &m); while (m--) { int al, ar, ans; scanf("%d%d%d", &al, &ar, &ans); update(1, 1, n, al, ar, ans); } printf("Case %d: The total value of the hook is %d.\n", tt, tree[1]); } return 0; }
相关推荐
Hook+-+进程防杀 进程 HOOK c++ 源代码
易语言x64_hook模块源码+实列 带实用hook 实列 方便操作
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
DELPHI HOOK 钩子 通过调用API 通过MessageBoxA,MessageBoxW,MessageBoxW,OpenProcess 函数的截取。
using (var hook = new MessageBoxHook()) { //绕过Hook直接调用源函数 hook.Origin(IntPtr.Zero, "111", "222", 0); //调用Api 被Hook MessageBox.Show("Hello world", "666", MessageBoxButtons.YesNoCancel...
API Hook 源代码 vc ++ API Hook 源代码 vc ++
用来将自定义的 Dll 注入进程空间,并钩住指定 API 函数
Hook经典分析 关于QQ Hook的应用 钩子
C#使用Hook监听获取LWIN+F20、LWIN+F19、LWin+F18用来覆盖ink工作区的设置
拼西西商城后台管理系统源码(react(hook) + antd + ts) 拼西西商城后台管理系统源码(react(hook) + antd + ts) 拼西西商城后台管理系统源码(react(hook) + antd + ts) 拼西西...
用于过滤d2gs在没有源码的情况把本身的4000端口hook到其他端口,然后通过hpsocket转发数据并过滤其中不好的东西。 主要用于针对暗黑2私服中用封包攻击端口用,类似于端口防火墙的原理.
Delphi的9个钩子实例源码:CopyHook+利用Hook在Explorer进程插入一个线程+全局快捷键HOOK+消息HOOK+鼠标HOOK+IO HOOK+鼠标键盘记录HOOK
源码采用inlinehook来监听实时消息,并且回调到易语言,可监听的消息为:收到的聊天内容/发送出去的聊天内容/入店路径/改地址信息/退款信息/小卡片信息/订单信息等等自动监视目标进程创建,自动hook/自动还原hook。...
3.易语言的信息框就是messageboxA,反而模块中的MessageBoxA却hook不到...没有看模块的源码,也不知道是哪个模块里面的.这里请教高手解答一下.. 4.界面很丑 讲一下这个hook的过程吧,比较有意思的,而且还有很大的拓展...
dxgkrnl_hook 这将钩住图形内核子系统以允许操纵屏幕缓冲区,有关更多信息,请参见本文 用法示例 在播放器盒视频是通过使用钩绘制。
Native+Hook+技术分析,分别讲解 GOT/PLT Hook、Trap Hook 以及 Inline Hook这些 Hook 技术的实现原理和优劣比较
加壳器 包括技术:Hook IAT, stolen codes,动态加载 编程语言:汇编。
屏蔽WIN、ALT+TAB、CTRL+ESC键的低级键盘钩子.zip
API hook API hook API hook
hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程hook 教程...