CodeVS 1082 线段树练习3 【Splay模板】

tonyfang posted @ 2016年2月14日 16:55 in codevs with tags C++ OI , 655 阅读

学习了下Splay,发现原来学的都是错的(迷

学了下正确的姿势:http://wenku.baidu.com/link?url=scHbokjqF7nK8kca00Pxrm8uaUmm7HNkgXLGaq0tNU-9T2zOrc08oZ7YJkXagD-Q2FVpZ89uxjStXco_8zK5T83Bwx2XXhBjbtAK6dxGMoW

(发完链接就贴代码系列)

 

#include <stdio.h>
#include <iostream>
using namespace std;

#define Max 200010 
#define B ch[ch[root][1]][0] 
int ch[Max][2],fa[Max],root,o[Max],sz[Max],n;
long long sum[Max],tag[Max],val[Max],an;
void pushdown(int x) {
	if (!x || !tag[x]) return;
	val[x]+=tag[x];
	if(ch[x][0]) tag[ch[x][0]]+=tag[x],sum[ch[x][0]]+=tag[x]*sz[ch[x][0]];
	if(ch[x][1]) tag[ch[x][1]]+=tag[x],sum[ch[x][1]]+=tag[x]*sz[ch[x][1]];
	tag[x]=0;
}
void update(int x) {
    if(!x) return ;
	sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
	sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
void rotate(int x) {
	if(!fa[x]) return;
	int y=fa[x],p=ch[y][0]==x;
	pushdown(y);
	pushdown(x);
	int b=ch[x][p];ch[y][p^1]=b;
	if(b) fa[b]=y;
	fa[x]=fa[y];
	if(fa[y]) ch[fa[y]][ch[fa[y]][1]==y]=x;
	ch[x][p]=y;fa[y]=x;
	update(y);
	if(y==root) root=x;
}

void splayy(int x,int f) {
	pushdown(x);
	while(fa[x]!=f) {
		if(fa[fa[x]]!=f) {
			int y=fa[x];
			if((ch[y][0]==x)^(ch[fa[y]][0]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	update(x);
	if(!f) root=x;
}
void splayk(int k,int f) {
	int x=root;pushdown(x);
	while(sz[ch[x][0]]!=k-1) {
		if(sz[ch[x][0]]<k) {
			k-=sz[ch[x][0]]+1;
			x=ch[x][1];
		} else x=ch[x][0];
		pushdown(x);
	}
	splayy(x,f);
}
void addnode(int &ad,int f,int x) {
	ad=++an;sz[ad]=1,fa[ad]=f,val[ad]=sum[ad]=x;
}
void build(int &ad,int f,int l,int r) {
	if(l>r) {ad=0;return;}
	int mid=l+r>>1;
	addnode(ad,f,o[mid]);
	build(ch[ad][0],ad,l,mid-1);
	build(ch[ad][1],ad,mid+1,r);
	update(ad);
}
void init() {
	an=0;
	addnode(root,0,0);
	addnode(ch[root][1],root,0);
	update(root);
	build(B,ch[root][1],1,n);
	update(ch[root][1]);
	update(root);
}
void getlr(int l,int r) {
	splayk(l,0);
	splayk(r+2,root);
}
int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&o[i]);
	init();
	int Q;char buf[123];int a,b,c;scanf("%d",&Q);
	while(Q--) {
		scanf("%s",buf);
		if(buf[0]=='2') {
			scanf("%d%d",&a,&b);
			getlr(a,b);
			printf("%lld\n",sum[B]);
		} else {
			scanf("%d%d%d",&a,&b,&c);
			getlr(a,b);
			tag[B]+=c;
			sum[B]+=(long long)sz[B]*c;
		}
	}	
} 
https://recruit-noti 说:
2023年4月15日 22:37

Recruit-notify.in is an initiative of professional writers who have come together for dedicated news coverage of the latest happenings around the country. https://recruit-notify.in/ Our team comprises professional writers & citizens with a diverse range of interests in Journalism who are passionate about publishing Education Updates with transparency in general public interest.Our reporting team intends to publish the Education & Recruitment Update for all age groups and present the true picture of the recent events with the inside coverage.

my today activity 说:
2023年7月10日 22:46

My Activity today is a piece tracking or recording user activity that collects information whenever users with a Google account use Google services daily such as today, yesterday, weekly, monthly, and yearly for entire activities from the account generation. my today activity These My Activity recording or collection services include YouTube, Google Maps, and other Google apps, as well as your search history when using the Google Chrome browser or doing a Google search.

CBSE 4th Class Spli 说:
2023年8月21日 19:20

CBSE Curriculum is based on the National Curriculum Framework and Provides Opportunities for Students to Achieve Excellence in Learning, CBSE Provides the Syllabus for 4th Class, This new Syllabus CBSE 4th Class Split up Syllabus 2024 are Designed Strategically by a Team of Subject Experts and are Prescribed by the Ministry of Human Resource Development, formerly Ministry of Education, is Responsible for the Development of Human Resources in India, Primary Level Syllabus for the Children of has been developed with the Supervision of the Central Board of Secondary Education.

pavzi.com 说:
2024年1月03日 20:54

Pavzi website is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. pavzi.com We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter