SuperMemo 【POJ - 3580】【Splay】

2023-11-23 00:58:09

题目链接

一份完整的解题代码

  这是第二次来做这道题，关于Splay与其他数据结构又更好的联系起来了，更加的注意那些在细节上的处理，在pushdown()与pushup()上的处理尤其重要。

  这次写的更加清晰了。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, M, root, tot;
struct node
{int ff, val, ch[2], lazy, add, size, minn;node() { ff = val = ch[0] = ch[1] = lazy = add = size = 0; minn = INF; }void init(int fa, int _val) { ff = fa; val = minn = _val;  ch[0] = ch[1] = lazy = add = 0; size = 1; }
}t[maxN<<1];
void pushup(int rt)
{if(!rt) return;t[rt].size = t[t[rt].ch[0]].size + t[t[rt].ch[1]].size + 1;t[rt].minn = t[rt].val;if(t[rt].ch[0]) t[rt].minn = min(t[rt].minn, t[t[rt].ch[0]].minn);if(t[rt].ch[1]) t[rt].minn = min(t[rt].minn, t[t[rt].ch[1]].minn);
}
void pushdown(int rt)
{if(!rt) return;if(t[rt].add){if(t[rt].ch[0]){t[t[rt].ch[0]].add += t[rt].add;t[t[rt].ch[0]].val += t[rt].add;t[t[rt].ch[0]].minn += t[rt].add;}if(t[rt].ch[1]){t[t[rt].ch[1]].add += t[rt].add;t[t[rt].ch[1]].val += t[rt].add;t[t[rt].ch[1]].minn += t[rt].add;}t[rt].add = 0;}if(t[rt].lazy){t[rt].lazy ^= 1;swap(t[rt].ch[0], t[rt].ch[1]);if(t[rt].ch[0]) t[t[rt].ch[0]].lazy ^= 1;if(t[rt].ch[1]) t[t[rt].ch[1]].lazy ^= 1;}
}
void Rotate(int x)
{int y = t[x].ff, z = t[y].ff;pushdown(y);    pushdown(x);int k = t[y].ch[1] == x;t[z].ch[t[z].ch[1] == y] = x;t[x].ff = z;t[y].ch[k] = t[x].ch[k^1];t[t[x].ch[k^1]].ff = y;t[x].ch[k^1] = y;t[y].ff = x;pushup(y);  pushup(x);
}
void Splay(int x, int goal)
{while(t[x].ff != goal){int y = t[x].ff, z = t[y].ff;pushdown(z);    pushdown(y);    pushdown(x);if(z != goal) (t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? Rotate(x) : Rotate(y);Rotate(x);}if(!goal) root = x;
}
void insert(int x)
{int u = ++tot;t[root].ch[1] = u;t[u].init(root, x);Splay(u, 0);
}
int Kth(int x)
{int u = root;while(true){pushdown(u);int y = t[u].ch[0];if(t[y].size + 1 < x){x -= t[y].size + 1;u = t[u].ch[1];}else{if(t[y].size >= x) u = y;else return u;}}
}
inline void ADD(int l, int r, int val)
{l = Kth(l - 1);   r = Kth(r + 1);Splay(l, 0);    Splay(r, l);int tmp = t[r].ch[0];t[tmp].add += val;t[tmp].val += val;t[tmp].minn += val;
}
inline void INSERT(int x, int P)
{int l = Kth(x), r = Kth(x + 1);Splay(l, 0);    Splay(r, l);t[r].ch[0] = ++tot;t[tot].init(r, P);pushup(r);  pushup(l);
}
inline void DELETE(int x)
{int l = Kth(x - 1), r = Kth(x + 1);Splay(l, 0);    Splay(r, l);t[r].ch[0] = 0;pushup(r);  pushup(l);
}
inline int MIN(int l, int r)
{l = Kth(l - 1); r = Kth(r + 1);Splay(l, 0);    Splay(r, l);int tmp = t[r].ch[0];return t[tmp].minn;
}
inline void REVERSE(int l, int r)
{l = Kth(l - 1); r = Kth(r + 1);Splay(l, 0);    Splay(r, l);int tmp = t[r].ch[0];t[tmp].lazy ^= 1;
}
inline void REVOLVE(int l1, int r1, int l2, int r2)
{int x = Kth(l2 - 1), y = Kth(r2 + 1);Splay(x, 0);    Splay(y, x);int tmp = t[y].ch[0];t[y].ch[0] = 0;x = Kth(l1 - 1);    y = Kth(l1);Splay(x, 0);    Splay(y, x);t[y].ch[0] = tmp;t[tmp].ff = y;pushup(y);  pushup(x);
}
inline void init()
{root = tot = 0;memset(t, 0, sizeof(t));insert(INF);
}
char op[10];
int main()
{while(scanf("%d", &N)!=EOF){init();for(int i=1, val; i<=N; i++){scanf("%d", &val);insert(val);}   insert(INF);scanf("%d", &M);int l, r, T;while(M--){scanf("%s", op);if(op[0] == 'A')    //ADD x y D{scanf("%d%d%d", &l, &r, &T);ADD(l + 1, r + 1, T);}else if(op[0] == 'I')   //INSERT x P{scanf("%d%d", &l, &r);INSERT(l + 1, r);}else if(op[0] == 'D')   //DELETE x{scanf("%d", &l);DELETE(l + 1);}else if(op[0] == 'M')   //MIN x y{scanf("%d%d", &l, &r);printf("%d\n", MIN(l + 1, r + 1));}else if(op[3] == 'E')   //REVERSE x y{scanf("%d%d", &l, &r);REVERSE(l + 1, r + 1);}else    //REVOLVE x y T{scanf("%d%d%d", &l, &r, &T);T = T % (r - l + 1);if(T) REVOLVE(l + 1, r- T + 1, r - T + 2, r + 1);}}}return 0;
}

 


本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

相关文章

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统 微软输入法 于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销 是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题 跑道 汽车 绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

立即
投稿

微信公众账号

微信扫一扫加关注

 返回
顶部