[题解] [JSOI2011] 任务调度
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了[题解] [JSOI2011] 任务调度,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2105字,纯文字阅读大概需要4分钟。
内容图文
![[题解] [JSOI2011] 任务调度](/upload/InfoBanner/zyjiaocheng/1142/6243077415774e019dc02224c325f9b1.jpg)
题解
题面
左偏树练习题吧
改权值的操作就是把这个点扯出来, 左右儿子合并后接到这个点的父亲上去, 然后再把这个点重新塞进左偏树里就行了
至于这部操作为什么不要更新 dis , 可能是因为 dis 最多只会变 1 , 左偏的性质还是存在吧
Code
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 300005;
using namespace std;
int n, m, T, rt[505];
char s[105];
struct node
{
int val, dis, fa, ch[2];
} t[N];
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
int merge(int x, int y)
{
if(!x || !y) return x + y;
if(t[x].val > t[y].val) swap(x, y);
t[x].ch[1] = merge(t[x].ch[1], y);
if(t[t[x].ch[1]].dis > t[t[x].ch[0]].dis) swap(t[x].ch[0], t[x].ch[1]);
t[x].dis = t[t[x].ch[1]].dis + 1;
t[t[x].ch[0]].fa = t[t[x].ch[1]].fa = x;
return x;
}
void modify(int x, int y, int z)
{
int f = t[y].fa, tmp = merge(t[y].ch[0], t[y].ch[1]);
if(rt[x] == y) rt[x] = tmp;
else t[f].ch[t[f].ch[1] == y] = tmp;
t[tmp].fa = f; t[y].val = z, t[y].fa = 0;
t[y].ch[0] = t[y].ch[1] = 0;
rt[x] = merge(rt[x], y);
}
int main()
{
n = read <int> (), m = read <int> (), T = read <int> ();
int x, y, z;
while(T--)
{
scanf("%s", s + 1);
if(s[1] == 'A')
{
x = read <int> (), y = read <int> (), z = read <int> ();
modify(x, y, z);
// t[y].val = z, rt[x] = merge(rt[x], y);
}
else if(s[1] == 'D')
{
x = read <int> (), y = read <int> (), z = read <int> ();
modify(x, y, t[y].val - z);
}
else if(s[1] == 'T')
{
x = read <int> (), y = read <int> ();
rt[y] = merge(rt[y], rt[x]), rt[x] = 0;
}
else if(s[1] == 'M')
x = read <int> (), printf("%d\n", t[rt[x]].val);
else if(s[1] == 'W')
{
x = read <int> (), y = read <int> ();
if((t[rt[x]].ch[0] && t[rt[x]].val == t[t[rt[x]].ch[0]].val) || (t[rt[x]].ch[1] && t[rt[x]].val == t[t[rt[x]].ch[1]].val))
puts("ERROR");
else modify(x, rt[x], t[rt[x]].val + y);
}
}
return 0;
}
原文:https://www.cnblogs.com/ztlztl/p/12258734.html
内容总结
以上是互联网集市为您收集整理的[题解] [JSOI2011] 任务调度全部内容,希望文章能够帮你解决[题解] [JSOI2011] 任务调度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。