【splay tree】 HDOJ 4441 Queue Sequence

2023-09-20 05:55:47

题目中由三种操作，第一种：在指定位置插入一个当前没用过的最小正数。。。第二种：在序列中删除一个数的正负数。。。第三种：在序列中查询一个数的正负数之间的和。。。对于第一种操作，找最小正数可以用线段树来找。判断插入的负数位置前面的负数个数必定等于插入的正数位置前面的正数个数。。然后插入的负数位置又是最右端的，由此可以找出负数的位置。。。对于后面两个操作，可以开两个数组记录正负数在序列中的位置。。。数组存的不是位置编号，位置编号会随插入和删除数而改变的。。存的是数在序列中的节点（指针写就是指针指向的位置，数组模拟存的就是数组下标）。。这样就可以快速定位数在splay中的位置。。然后就可以用splay搞了。。。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include 
#include 
#include 
#define maxn 200005
#define maxm 400005
#define eps 1e-10
#define mod 1000000007 
#define INF 99999999 
#define lowbit(x) (x&(-x))  
#define ls o<<1
#define rs o<<1 | 1
#define lson o<<1, L, mid  
#define rson o<<1 | 1, mid+1, R  
typedef long long LL;
//typedef int LL;
using namespace std;struct node
{int s, v, nos;LL sum;node *ch[2], *fa;int cmp(int x){if(x == ch[0]->s + 1) return -1;if(x > ch[0]->s + 1) return 1;else return 0;}void maintain(void){s = ch[0]->s + ch[1]->s + 1;sum = ch[0]->sum + ch[1]->sum + v;nos = ch[0]->nos + ch[1]->nos;if(v < 0) nos++;}
}*null, *root, C[maxn], *seat[maxn][2], *top;
void rotate(node* &o, int d)
{node *p = o->fa; p->ch[d^1] = o->ch[d], o->fa = p->fa;if(p->fa != null) {if(p->fa->ch[0] == p) p->fa->ch[0] = o;else p->fa->ch[1] = o;}if(p->ch[d^1] != null) p->ch[d^1]->fa = p;p->fa = o, o->ch[d] = p;p->maintain(), o->maintain();
}
void splay(node* &o)
{node *p;while(o->fa != null) {p = o->fa;if(p->ch[0] == o) {if(p != null && p->fa->ch[0] == p)rotate(p, true);rotate(o, true);}else {if(p != null && p->fa->ch[1] == p)rotate(p, false);rotate(o, false);}}
}
void kth(node* &o, int k)
{int d = o->cmp(k);while(d != -1) {if(d) {k -= o->ch[0]->s + 1;o = o->ch[1];}else o = o->ch[0];d = o->cmp(k);}splay(o);
}
node* merge(node* left, node* right)
{kth(left, left->s);left->ch[1] = right;right->fa = left;left->maintain();return left;
}
void split(node *o, int k, node* &left, node* &right)
{kth(o, k);right = o->ch[1];right->fa = null;o->ch[1] = null;left = o;left->maintain();
}
void find(node* &o, int k)
{while(!(o->ch[0]->nos + 1 == k && o->v < 0)) {if(o->ch[0]->nos + 1 > k) {o = o->ch[0];}else {k -= o->ch[0]->nos;if(o->v < 0) k -= 1;o = o->ch[1];}}splay(o);
}
int done[maxn<<2];
int get_plus(int o, int L, int R)
{if(L == R) {done[o] = 1;return L;}int mid = (L+R)>>1, ans = 0;if(done[ls]) ans = get_plus(rson);else ans = get_plus(lson);if(done[ls] && done[rs]) done[o] = 1;else done[o] = 0;return ans;
}
void updata(int o, int L, int R, int v)
{if(L == R) {done[o] = 0;return;}int mid = (L+R)>>1;if(v <= mid) updata(lson, v);else updata(rson, v);if(done[ls] && done[rs]) done[o] = 1;else done[o] = 0;
}
node* newnode(void)
{top++;top->s = 1;top->v = top->nos = 0;top->ch[0] = top->ch[1] = top->fa = null;return top;
}
void init(void)
{memset(done, 0, sizeof done);top = C;null = top++;null->v = null->s = null->nos = 0;null->ch[0] = null->ch[1] = null->fa = NULL;root = newnode();root->nos = 0;
}
void debug(node* o)
{if(o->ch[0] != null) debug(o->ch[0]);printf("AA %d  %d BB\n", o->v, o->s);if(o->ch[1] != null) debug(o->ch[1]);
}
void work(int m)
{int k, cnt = 0, n = 100000, v;node *p, *left, *right, *mid;char s[10];while(m--) {scanf("%s%d", s, &k);if(s[0] == 'i') {v = get_plus(1, 1, n);p = newnode();seat[v][0] = p;p->v = v;split(root, k+1, left, right);root = merge(merge(left, p), right);cnt++;p = newnode();p->v = -v;seat[v][1] = p;if(root->ch[0]->s - root->ch[0]->nos == cnt) {k = 2*cnt;split(root, k, left, right);}else {find(root, root->ch[0]->s - root->ch[0]->nos);split(root, root->ch[0]->s, left, right);}root = merge(merge(left, p), right);}if(s[0] == 'r') {updata(1, 1, n, k);splay(seat[k][0]);split(seat[k][0], seat[k][0]->ch[0]->s, left, p);split(p, 1, mid, right);root = merge(left, right);splay(seat[k][1]);split(seat[k][1], seat[k][1]->ch[0]->s, left, p);split(p, 1, mid, right);root = merge(left, right);cnt--;}if(s[0] == 'q') {splay(seat[k][0]);split(seat[k][0], seat[k][0]->ch[0]->s, left, p);splay(seat[k][1]);split(seat[k][1], seat[k][1]->ch[0]->s + 1, mid, right);printf("%I64d\n", mid->sum);root = merge(merge(left, mid), right);}}
}
int main(void)
{int m, _ = 0;while(scanf("%d", &m)!=EOF) {init();printf("Case #%d:\n", ++_);work(m);}return 0;
}

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

标签：技术

上一篇 > 【HDU 4441】 Queue Sequence 【Splay】
下一篇 > 【训练8】模拟员工打卡（法一、字符串数组；法二、字符串indexOf()方法）

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

【splay tree】 HDOJ 4441 Queue Sequence

相关文章