文档章节

loj 558 我们的 CPU 遭到攻击

o
 osc_n6euf5h6
发布于 2019/03/19 19:23
字数 1143
阅读 14
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

这题很明显是lct,我们只要可以维护黑色点深度和即可。

但是lct维护子树信息好难写啊。 首先边权比较难处理,所以偷懒加虚点表示边。

然后考虑维护子树距离和,需要维护splay上的边权和。 为了可以reverse,还必须维护一个反的距离和。 虚子树的答案更新在access和link连虚边的时候。 好烦啊。

千万不要把splay之前的下传标记写挂,记得只下传本splay的标记。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;

struct node{
	int blcnt;//black cnt
	int non_cnt;//xzs
	ll non_dis;
	ll sumval;//bian quan he
	int val;//bian quan
	ll disl,disr;//disl disr
	bool fl,bl;
	int fa,ch[2];
	void clear(){
		memset(this,0,sizeof(*this));
	}
	void print(){
		cout<<"blcnt: "<<blcnt<<endl;
		cout<<"non_cnt: "<<non_cnt<<endl;
		cout<<"non_dis: "<<non_dis<<endl;
		cout<<"sumval: "<<sumval<<endl;
		cout<<"val: "<<val<<endl;
		cout<<"dislr: "<<disl<<" "<<disr<<endl;
		cout<<"flip: "<<fl<<endl;
		cout<<"bl:"<<bl<<endl;
		cout<<"fa:"<<fa<<endl;
		cout<<"ch[0:1]:"<<ch[0]<<" "<<ch[1]<<endl;
	}
}T[N];

int n,m,k;
bool get(int x){
	return T[T[x].fa].ch[1]==x;
}
bool nroot(int x){
	return T[T[x].fa].ch[0]==x||T[T[x].fa].ch[1]==x;
}
bool ISBLACK(int x){
	return x<=n&&T[x].bl;
}
void pushup(int x){
	//cerr<<"pushup"<<x<<endl;
	int ls=T[x].ch[0],rs=T[x].ch[1];
	T[x].blcnt=T[x].bl+T[ls].blcnt+T[rs].blcnt+T[x].non_cnt;
	T[x].sumval=T[x].val+T[ls].sumval+T[rs].sumval;
	
	T[x].disl=T[x].disr=T[x].non_dis;

	T[x].disl+=T[ls].disl+T[rs].disl+(ISBLACK(x)+T[x].non_cnt+T[rs].blcnt)*(T[ls].sumval+T[x].val);
	T[x].disr+=T[rs].disr+T[ls].disr+(ISBLACK(x)+T[x].non_cnt+T[ls].blcnt)*(T[rs].sumval+T[x].val);
};

void puttag(int x){
	swap(T[x].disl,T[x].disr);
	swap(T[x].ch[0],T[x].ch[1]);
	T[x].fl^=1;
}

void pushdown(int x){
	if (T[x].fl){
		if (T[x].ch[0]) puttag(T[x].ch[0]);
		if (T[x].ch[1]) puttag(T[x].ch[1]);
		T[x].fl=0;
	}
}
void allpushdown(int x){
	if (nroot(x)) allpushdown(T[x].fa);
	pushdown(x);
}


void rotate(int x){
	//cerr<<"roate"<<x<<endl;
	int f=T[x].fa,gx=get(x),xs=T[x].ch[gx^1];
	T[x].fa=T[f].fa; if (nroot(f)) T[T[f].fa].ch[get(f)]=x;
	T[f].fa=x; T[x].ch[gx^1]=f;
	if (xs) T[xs].fa=f; T[f].ch[gx]=xs;
	pushup(f);
	//cerr<<"faf"<<T[1].fa<<" "<<T[2].ch[0]<<" "<<T[2].ch[1]<<endl;
}

void splay(int x){
	//cerr<<"splay"<<x<<endl;
	allpushdown(x);
	for (; nroot(x); rotate(x)){
		int f=T[x].fa;
		if (nroot(f)&&get(f)==get(x)) rotate(f);
	}
	pushup(x);
	//cerr<<"splayend"<<endl;
}

void access(int x){//????
	//cerr<<"access"<<x<<" "<<"fa"<<T[x].fa<<" "<<T[3].fa<<endl;
	int la=0;
	while (1){
		splay(x);
		T[x].non_cnt+=T[T[x].ch[1]].blcnt-T[la].blcnt;
		T[x].non_dis+=T[T[x].ch[1]].disl-T[la].disl;
		T[x].ch[1]=la;
		pushup(x);
		la=x;
		if (!(x=T[x].fa)) break;	
	}
}

void makeroot(int x){
	//cerr<<"makeroot"<<x<<" "<<T[x].fa<<" "<<T[T[x].fa].fa<<" "<<T[T[T[x].fa].fa].fa<<endl;
	access(x);
	//cerr<<"ACCEND"<<endl;
	splay(x);
	//cerr<<"ASM"<<T[1].fa<<" "<<T[2].fa<<" "<<T[3].fa<<" "<<T[3].ch[0]<<endl;
	puttag(x);
	//cerr<<":MEDN"<<endl;
}

void __link(int x,int y){
	//link virtual edge
	//cerr<<"__link"<<x<<" "<<y<<endl;
	makeroot(x);
	makeroot(y);
	//cerr<<"YYB"<<T[y].ch[0]<<endl;
	T[y].fa=x;
	T[x].non_cnt+=T[y].blcnt;
	T[x].non_dis+=T[y].disl;
	pushup(x);
	//cerr<<"ASF__link"<<T[1].fa<<" "<<T[2].fa<<" "<<T[3].fa<<endl;
}
stack<int> s;
map<int,int> mp[N>>1];
void link(int u,int v,int w){
	//cerr<<"link"<<u<<" "<<v<<" "<<w<<endl;
	int cnt=s.top(); s.pop();
	mp[u][v]=mp[v][u]=cnt;
	T[cnt].clear();
	T[cnt].val=w;
	__link(u,cnt);
	__link(v,cnt);
}

void __cut(int x,int y){
	makeroot(x);
	access(y);
	splay(y);
	assert(T[y].ch[0]==x);
	T[y].ch[0]=0;
	T[x].fa=0;
	pushup(y);
}

void cut(int u,int v){
	int cnt=mp[u][v];
	__cut(u,cnt);
	__cut(v,cnt);
	s.push(cnt);
}

void flip(int u){
	makeroot(u);
	T[u].bl^=1;
	pushup(u);
}

void Dfs(int x){
	//cerr<<"Indfs"<<x<<" "<<T[x].fl<<" "<<T[x].ch[0]<<" "<<T[x].ch[1]<<" "<<T[x].sumval<<" "<<T[x].disl<<" "<<T[x].blcnt<<endl;
	if (T[x].ch[0]) Dfs(T[x].ch[0]);
	if (T[x].ch[1]) Dfs(T[x].ch[1]);
}

ll query(int u){
	//cerr<<"query"<<u<<endl;
	makeroot(u);
	//Dfs(u);
	//cerr<<"U"<<u<<endl;
	//cerr<<"query"<<T[u].blcnt<<endl;
	//cerr<<"query"<<T[u].non_dis<<" "<<T[u].non_cnt<<" "<<T[u].ch[0]<<" "<<T[u].ch[1]<<endl;
	//cerr<<"Trifa"<<T[3].fa<<" "<<T[3].val<<endl;
	//cerr<<"query"<<T[u].sumval<<endl;
	return T[u].disl;
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	for (int i=n+n-1; i>n; --i) s.push(i);
	for (int i=1; i<=m; ++i){
		//cerr<<"DOD"<<i<<endl;
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		//cerr<<u<<" "<<v<<" "<<w<<endl;
		link(u,v,w);
	}
	/*for (int i=1; i<=n+n-1; ++i){
		cerr<<"I"<<i<<endl;
		T[i].print();
		}*/
	//return 0;
	for (int i=1; i<=k; ++i){
		//cerr<<"action:------------------"<<i<<endl;
		char s[10];
		int u,v,w;
		scanf("%s%d",s,&u);
		//cerr<<u<<endl;
		if (s[0]=='C'||s[0]=='L') scanf("%d",&v);
		if (s[0]=='L') scanf("%d",&w);
		switch (s[0]){
		case 'L':
			link(u,v,w);
			break;
		case 'C':
			cut(u,v);
			break;
		case 'F':
			flip(u);
			break;
		case 'Q':
			cout<<query(u)<<'\n';
			break;
		}

		//cerr<<"DODODODDD"<<endl;
		//cerr<<"!!!!!!!"<<endl;
		//for (int i=1; i<n+n; ++i) T[i].print();
		
		//cerr<<"afterall"<<T[1].fa<<" "<<T[2].fa<<" "<<T[3].fa<<endl;
	}
}

差点就是最长代码了,足以看出调试的艰辛。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
什么是负载均衡和分布式缓存技术?

很多的网站管理者是等到网站遭到攻击了,受到损失了,才去寻求解决的方案,在将来的互联网飞速发展的时代,一定要有安全隐患意识,不要等到损失大了,再去想办法来补救,这样为时已晚。然而当...

云漫网络Ruan
2019/06/14
6
0
彻底扼杀,美国网络应急中心建议将问题 CPU 全换掉

这两天,包括 Intel、AMD、ARM 等主要 CPU 大厂相继曝出重大处理器漏洞,且可能会造成敏感数据外泄,而引发轩然大波。除了各家 CPU 厂商发文公关,各家系统供应商和云服务厂商加紧修复外,美...

王练
2018/01/05
6K
42
现身说法:面对DDoS攻击时该如何防御?

上周,我们的网站遭到了一次DDoS攻击。虽然我对DDoS的防御还是比较了解,但是真正遇到时依然打了我个措手不及。DDoS防御是一件比较繁琐的事,面对各种不同类型的攻击,防御方式也不尽相同。对...

osc_tc6nsv9u
2018/06/11
2
0
DDoS

什么是DDoS攻击 DDoS是英文Distributed Denial of Service的缩写,中文意思是“分布式拒绝服务”。那什么又是拒绝服务呢?用户可以这样理解,凡是能导致合法用户不能进行正常的网络服务的行为...

企图穿越
2010/05/19
250
0
Linux Energy 计划承担管理和保护电网的责任

https://linux.cn/article-11874-1.html 下一场网络战争首先针对的可能是电力供应,乌克兰和美国已经遭到过这样的攻击——乌克兰基辅曾经被俄罗斯黑客的攻击造成电力中断,2019 年 3 月,犹他...

osc_b1kaj6np
03/19
2
0

没有更多内容

加载失败,请刷新页面

加载更多

VB语言基础重要知识点12

我们课程,我们做一些针对于考试的简要讲解。 一、有关考试的几个问题 首先,提问:考试最重要的是什么? 答案其实很简单:得分!!!!! 想要得分,就要做到基本的保存。 保存哪些文件呢?...

刘金玉编程
2019/10/30
5
0
全网最全JAVA、Python电子书!限时领取,过时不候!

给大家整理了最全的入门+进阶书籍!!! 免费领取,无套路! 加微信发送“电子书” 秒通过,秒发资源! 本文分享自微信公众号 - Python进击者(JAVAandPythonJun)。 如有侵权,请联系 supp...

kuls
01/16
18
0
原创356--免费还是付费

最近得有一个星期,被一个录屏软件(record it)烦到了,本来免费版可以无限制录制,只能720p,GIF不支持,高清不支持,没有剪辑功能。 之前调研了好几种,用起来还是这个方便,就一直用了。...

八音弦
04/24
14
0
数字IC技术讨论群,设计和验证、前端和后端,总有你感兴趣的话题。快满了,需要的抓紧加入。

本文分享自微信公众号 - 白山头讲IC(gray_mount)。 如有侵权,请联系 support@oschina.cn 删除。 本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。...

白山头
04/29
5
0
how to install mongodb in centos7

[root@xtwj88 ~]# cat /etc/yum.repos.d/mongodb-org-4.2.repo [mongodb-org-4.2]name=MongoDB Repositorybaseurl=https://repo.mongodb.org/yum/redhat/$releasever/mongodb-org/4.2/x86......

qwfys
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部