splay tree成段更新，成段查询poj3466
2024-10-15 20:04:55
线段树入门题，换成splay tree 来搞搞。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std; #define MAXN 200100 long long Add[MAXN];//延迟标记 struct Splay_Tree
{
int cnt, rt;//cnt为节点数，rt == root struct Tree{
long long K;
long long sumk;
int key;//关键字
int num, size;//num是这个节点有多少重复，size是以这个节点为根的子树大小。
int fa, son[];
}T[MAXN]; inline void init()
{
cnt = ;//初始化超级根节点（标记为0的节点）
T[].size = ;
T[].sumk = ;
T[].K = ;
rt = ;
memset(Add,,sizeof(Add));
}
inline void PushUp(int x)
{
T[x].size=T[T[x].son[]].size+T[T[x].son[]].size+T[x].num;
T[x].sumk=T[T[x].son[]].sumk+T[T[x].son[]].sumk+T[x].K;
} inline void PushDown(int x)
{
if(Add[x])
{
if(T[x].son[])//
{
T[T[x].son[]].K += Add[x];
T[T[x].son[]].sumk += T[T[x].son[]].size*Add[x];
Add[T[x].son[]]+=Add[x];
}
if(T[x].son[])
{
T[T[x].son[]].K+=Add[x];
T[T[x].son[]].sumk += T[T[x].son[]].size*Add[x];
Add[T[x].son[]]+=Add[x];
}
Add[x]=;//不管子节点有没有，这层一定往下推,没有子节点相当于标记无效。
}
} inline int Newnode(int key, int fa,int K) //新建一个节点并返回
{
++cnt;
T[cnt].K = T[cnt].sumk = K;
T[cnt].key=key;
T[cnt].num=T[cnt].size=;
T[cnt].fa=fa;
T[cnt].son[]=T[cnt].son[]=;
return cnt;
} inline void Rotate(int x, int p) //0左旋 1右旋
{
int y=T[x].fa;
PushDown(y);//这里是不是必须的，我感觉从小往上不需要往上推
PushDown(x);
T[y].son[!p]=T[x].son[p];
T[T[x].son[p]].fa=y;
T[x].fa=T[y].fa;
if(T[x].fa)
T[T[x].fa].son[T[T[x].fa].son[] == y]=x;
T[x].son[p]=y;
T[y].fa=x;
PushUp(y);
PushUp(x);
} void Splay(int x, int To) //将x节点移动到To的子节点中
{
while(T[x].fa != To)
{
if(T[T[x].fa].fa == To)
Rotate(x, T[T[x].fa].son[] == x);
else
{
int y=T[x].fa, z=T[y].fa;
int p=(T[z].son[] == y);
if(T[y].son[p] == x)
Rotate(x, !p), Rotate(x, p); //之字旋
else
Rotate(y, p), Rotate(x, p); //一字旋
}
}
if(To == ) rt=x;
} int GetPth(int p, int To) //返回第p小的节点 并移动到To的子节点中
{
if(!rt || p > T[rt].size) return ;
int x=rt;
while(x)
{
PushDown(x);
if(p >= T[T[x].son[]].size+ && p <= T[T[x].son[]].size+T[x].num)
break;
if(p > T[T[x].son[]].size+T[x].num)
{
p-=T[T[x].son[]].size+T[x].num;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(x, );
return x;
} int Find(int key) //返回值为key的节点 若无返回0 若有将其转移到根处
{
if(!rt) return ;
int x=rt;
while(x)
{
PushDown(x);
if(T[x].key == key) break;
x=T[x].son[key > T[x].key];
}
if(x) Splay(x, );
return x;
} int Prev() //返回根节点的前驱 非重点
{
if(!rt || !T[rt].son[]) return ;
int x=T[rt].son[];
while(T[x].son[])
{
PushDown(x);
x=T[x].son[];
}
Splay(x, );
return x;
} int next() //返回根结点的后继 非重点
{
if(!rt || !T[rt].son[]) return ;
int x=T[rt].son[];
while(T[x].son[])
{
PushDown(x);
x=T[x].son[];
}
Splay(x, );
return x;
} void Insert(int key,int K) //插入key值
{
if(!rt)
rt=Newnode(key, , K);
else
{
int x=rt, y=;
while(x)
{
PushDown(x);
y=x;
if(T[x].key == key)
{
T[x].num++;
T[x].size++;
break;
}
T[x].size++;//既然一定调整
x=T[x].son[key > T[x].key];
}
if(!x)
x = T[y].son[key > T[y].key] = Newnode(key, y, K);
Splay(x, );
}
} void Delete(int key) //删除值为key的节点1个
{
int x=Find(key);
if(!x) return;
if(T[x].num>)
{
T[x].num--;
PushUp(x);
return;
}
int y=T[x].son[];
while(T[y].son[])
y=T[y].son[];
int z=T[x].son[];
while(T[z].son[])
z=T[z].son[];
if(!y && !z)
{
rt=;
return;
}
if(!y)
{
Splay(z, );
T[z].son[]=;
PushUp(z);
return;
}
if(!z)
{
Splay(y, );
T[y].son[]=;
PushUp(y);
return;
}
Splay(y, );
Splay(z, y);
T[z].son[]=;
PushUp(z);
PushUp(y);
} int GetRank(int key) //获得值<=key的节点个数 并将其转移到根处 若<key只需将<=换为<
{
if(!rt) return ;
int x=rt, ret=, y=;
while(x)
{
y=x;
if(T[x].key <= key)
{
ret += T[T[x].son[]].size + T[x].num;
x=T[x].son[];
}
else
x=T[x].son[];
}
Splay(y, );
return ret;
} // 这个删除太丑了
// void Delete(int l, int r) //删除值在[l, r]中的所有节点 l!=r
// {
// if(!Find(l)) Insert(l);// 你这样写真的好吗？ 泥煤
// int p=Prev();
// if(!Find(r)) Insert(r);
// int q=next();
// if(!p && !q)
// {
// rt=0;
// return;
// }
// if(!p)
// {
// T[rt].son[0]=0;
// PushUp(rt);
// return;
// }
// if(!q)
// {
// Splay(p, 0);
// T[rt].son[1]=0;
// PushUp(rt);
// return;
// }
// Splay(p, q);
// T[p].son[1]=0;
// PushUp(p);
// PushUp(q);
// }
}spt; int main() {
int n,q;
scanf("%d%d",&n,&q);
spt.init();
for(int i=;i<=n;i++)
{
int tmp;
scanf("%d",&tmp);
spt.Insert(i, tmp);
}
for(int i=;i<q;i++)
{
getchar();
char sign;
scanf("%c",&sign);
long long ans=;
if(sign == 'Q')
{
int a,b;
scanf("%d%d",&a,&b);
if(a==b)
{
int id = spt.Find(a);
// mark
ans = spt.T[id].K;
//cout<<spt.T[id].K<<endl;
}
else
{
int ida,idb;
idb = spt.Find(b);//在这题，因为点没有删除,所以点的标号和splaytree中标号一致。
ida = spt.Find(a);//但是有lazy标记，所以还是得找一遍，可以把标记往下推。
spt.Splay(idb, ida);
int idson = spt.T[idb].son[];
//spt.PushDown(idb);
ans = spt.T[idb].K + spt.T[ida].K + spt.T[idson].sumk;
}
printf("%I64d\n",ans);
//cout<<ans<<endl;
}
else
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c); if(a==b)
{
int id = spt.Find(a);
spt.T[id].K += c;
spt.T[id].sumk += c;
// 这个节点的值改变了,还是得往上推
spt.Splay(id, );
}
else
{
int ida,idb;
idb = spt.Find(b);
ida = spt.Find(a); spt.T[ida].K += c;
//spt.T[ida].sumk += c;
spt.T[idb].K += c;
//spt.T[idb].sumk += c; spt.Splay(idb, ida); int idson = spt.T[idb].son[]; if(idson != )
{
spt.T[ idson ].sumk += spt.T[ idson ].size*c;
spt.T[ idson ].K += c;
Add[idson] += c;// 当全局变量来用
spt.Splay(idson, );//还得往上推一下吧
} } }
}
return ;
}
最新文章
- WPF路径动画(动态逆向动画)
- HA（High available）-Keepalived高可用性集群(双机热备)单点实验-菜鸟入门级
- 快速反射DataTable
- C# 动态链接库的创建
- Gulp的安装
- 【redis】04set类型和zset类型
- JavaScript 输入自动完成插件
- OD: Kernel Vulnerabilities Analyze
- MySQL_数据分页查询（limit用法）
- If We Were a Child Again
- echarts学习总结（一）：图表溢出窗口，图表数据窗口显示不全
- 命令行的目录栈(pushd指令与popd指令)
- linux下安装vld
- 整理c盘文件
- OO第二单元多线程电梯总结分析
- python multiprocessing深度解析
- vue从入门到进阶：Class 与 Style 绑定（四）
- zend studio mac
- C语言基础总结 分类： iOS学习 c语言基础 2015-06-11 10:08 23人阅读 评论(0) 收藏
- java8 - 4
热门文章
- Codeforces Round #307 (Div. 2) D. GukiZ and Binary Operations （矩阵高速幂）
- 进程资源和进程状态 TASK_RUNNING TASK_INTERRUPTIBLE TASK_UNINTERRUPTIBLE
- JSON——Java中的使用
- Pycharm 安装scrapy
- 学习使用master.dbo.spt_values表
- asp.net core mvc视频A：笔记6-1.应用发布与部署
- Jquery的promise对象
- Redis之ziplist数据结构
- 在CTreeCtrl控件点击事件中获取点击的项
- STL 源代码剖析 算法 stl_algo.h -- rotate