Splay 全 TLE 求助
查看原帖
Splay 全 TLE 求助
363036
chlchl楼主2022/3/19 21:51

rt,还是说这道题卡 Splay?大概是代码有点问题,请大佬瞧瞧!

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100010;
int rt, num;
int n, q, a[N], s[N], cntemp;
struct Splay_tree{
	int val, sum, tag, sz, fa, son[2];
} spy[N];

void newnode(int &u, int p, int k){
	if(cntemp)	u = cntemp--;
	else	u = ++num;
	spy[u].fa = p;
	spy[u].sz = 1;
	spy[u].tag = spy[u].son[0] = spy[u].son[1] = 0;
	spy[u].val = spy[u].sum = k;
}

bool direction(int u, int fa){return spy[fa].son[1] == u;}

//给r为根的子树增加值,把当前结点更新掉,加延迟标记
void update_val(int u, int v){
	if(u == 0)	return;
	spy[u].tag += v, spy[u].val += v, spy[u].sum += v * spy[u].sz;//更新区间值 
}

void pushup(int u){//更新当前节点的区间和、子树大小 
	spy[u].sz = spy[spy[u].son[0]].sz + spy[spy[u].son[1]].sz + 1;
	spy[u].sum = spy[spy[u].son[0]].sum + spy[spy[u].son[1]].sum + spy[u].val;
}

void pushdown(int u){
	if(spy[u].tag){//与线段树相似 
		update_val(spy[u].son[0], spy[u].tag);
		update_val(spy[u].son[1], spy[u].tag);
		spy[u].tag = 0;
	}
}

void build(int &o, int l, int r, int p){
	if(l > r)	return;
	int mid = (l + r) >> 1;
	newnode(o, p, a[mid]);//建树,新建当前节点 
	build(spy[o].son[0], l, mid - 1, o);//往左子树递归
	build(spy[o].son[1], mid + 1, r, o);//往右子树递归 
	pushup(o);//更新 o 节点的 val 和 sum 
}

void Rotate(int x, int d){//旋转 
	int f = spy[x].fa;
	pushdown(f);
	pushdown(x);//任何操作前下放节点,不然就连父亲儿子都找不到了 
	spy[f].son[!d] = spy[x].son[d];//处理大于等于x,小于等于y的数 
	spy[spy[x].son[d]].fa = f;//更换父子关系 
	if(spy[f].fa)	spy[spy[f].fa].son[direction(f, spy[f].fa)] = x;//更新祖父的儿子 
	spy[x].fa = spy[f].fa;//x 原来的父亲是现在 f 的父亲 
	spy[x].son[d] = f;//x 的儿子变成了 f 
	spy[f].fa = x;//f 的父亲变成了 x 
	pushup(f);//更新 f 
}

void Splay(int u, int goal){
	pushdown(u);
	while(spy[u].fa != goal){
		if(spy[spy[u].fa].fa == goal)	Rotate(u, !direction(u, spy[u].fa));//祖先的祖先就是目标了!旋一次就行了 
		else{
			int y = spy[u].fa;//否则开始双旋 
			int d = !direction(y, spy[y].fa);
			if(spy[y].son[d] == u)	Rotate(u, !d), Rotate(u, d);
			else	Rotate(y, d), Rotate(u, d);
		}
	}
	pushup(u);
	if(goal == 0)	rt = u;
}

int rnk(int u, int k){//查询排名为 k 的数 
	pushdown(u);//先下放,与线段树一样 
	int t = spy[spy[u].son[0]].sz + 1;//左子树sz+自身 
	if(t == k)	return u; 
	if(t > k)	return rnk(spy[u].son[0], k);//在左子树中,往下递归
	else	return rnk(spy[u].son[1], k - t);//在右子树中,往右子树递归,查询排名为 k - t 的数 
}

void update(int l, int r, int d){//区间增加一个值
	Splay(rnk(rt, l), 0);//将第l个点旋转到根结点
	Splay(rnk(rt, r + 2), rt);//因为加了个空结点,第 r + 2 个点旋转到根结点的右孩子
	update_val(spy[spy[rt].son[1]].son[0], d);//将区间更新 
	pushup(spy[rt].son[1]);//更新右子树(val更新之后右子树也会改变) 
	pushup(rt);//更新节点 (根节点就更不用说了) 
}

int query(int l, int r){//查询区间的和
	Splay(rnk(rt, l), 0);//同 update 
	Splay(rnk(rt, r + 2), rt);//同 update 
	return spy[spy[spy[rt].son[1]].son[0]].sum;//那么 spy[spy[rt].son[1]].son[0] 就是需要修改的区间[l, r]
}
 
main(){
	scanf("%lld%lld", &n, &q);
	rt = num = cntemp = 0;//cntemp 方便动态开点 
	spy[rt].son[0] = spy[rt].son[1] = spy[rt].fa = spy[rt].sz = spy[rt].tag = spy[rt].sum = spy[rt].val = 0;//初始化 
	newnode(rt, 0, -1);//新建两个空节点 
	newnode(spy[rt].son[1], rt, -1);//新建两个空节点,防止区间操作时旋了个寂寞 
	for(int i=1;i<=n;i++)	scanf("%lld", &a[i]);
	build(spy[spy[rt].son[1]].son[0], 1, n, spy[rt].son[1]);//建树(区间建树,所以这么传参) 
	pushup(spy[rt].son[1]);//更新右子树 
	pushup(rt);//更新根节点 
	int op, x, y, z;
	while(q--){
		scanf("%d", &op);
		if(op == 2){
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", query(x, y));
		}else{
			scanf("%lld%lld%lld", &x, &y, &z);
			update(x, y, z);
		}
	}
	return 0;
}
2022/3/19 21:51
加载中...