正解:$splay$
解题报告:
$splay$板子,,,?
先考虑这题要实现些什么东西嘛$QwQ$
其实只要实现一个东西?就查询数列中与给定数字相差最小的数,显然用$splay$查询前驱后继,然后就没辣,,,?(哦还一个$insert$,,,$QwQ$
记得分类讨论下是人有剩还是宠物有剩就好,$over$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char const int N=1e5,mod=,inf=1e9;
int rt,n,cnt=,nod_cnt,as,a,b;
struct nod{int ch[],val,sz,fa;il void pre(ri x,ri fat){ch[]=ch[]=;val=x;sz=;fa=fat;}}tr[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void pushup(ri x){tr[x].sz=tr[tr[x].ch[]].sz+tr[tr[x].ch[]].sz+;}
il void rotate(ri x)
{
ri fa=tr[x].fa,grdfa=tr[fa].fa;rb op1=tr[fa].ch[]==x,op2=tr[grdfa].ch[]==fa;
tr[grdfa].ch[op2]=x;tr[x].fa=grdfa;
tr[fa].ch[op1]=tr[x].ch[op1^];tr[tr[x].ch[op1^]].fa=fa;
tr[fa].fa=x;tr[x].ch[op1^]=fa;
pushup(fa);pushup(x);
}
il void splay(ri x,ri goal)
{
if(!x)return;
while(tr[x].fa!=goal)
{
ri fa=tr[x].fa,grdfa=tr[fa].fa;
if(grdfa!=goal)(tr[fa].ch[]==x)^(tr[grdfa].ch[]==fa)?rotate(x):rotate(fa);
rotate(x);
}
if(!goal)rt=x;
}
il void insert(ri x)
{
ri nw=rt,fa=;
while(nw)fa=nw,nw=tr[nw].ch[tr[nw].val<x];
nw=++nod_cnt;if(fa)tr[fa].ch[tr[fa].val<x]=nw;tr[nw].pre(x,fa);
splay(nw,);
}
il void fd(ri x)
{
ri nw=rt;if(!rt)return;
while(tr[nw].ch[x>tr[nw].val] && x!=tr[nw].val)nw=tr[nw].ch[x>tr[nw].val];
splay(nw,);
}
il int ask_pr(ri x)
{
fd(x);ri nw=rt;
if(tr[nw].val<=x)return nw;
nw=tr[nw].ch[];
while(tr[nw].ch[])nw=tr[nw].ch[];
return nw;
}
il int ask_lst(ri x)
{
fd(x);ri nw=rt;
if(tr[nw].val>=x)return nw;
nw=tr[nw].ch[];
while(tr[nw].ch[])nw=tr[nw].ch[];
return nw;
}
il int ask_pr_yg(ri x)
{
fd(x);ri nw=rt;
if(tr[nw].val<x)return nw;
nw=tr[nw].ch[];
while(tr[nw].ch[])nw=tr[nw].ch[];
return nw;
}
il int ask_lst_yg(ri x)
{
fd(x);ri nw=rt;
if(tr[nw].val>x)return nw;
nw=tr[nw].ch[];
while(tr[nw].ch[])nw=tr[nw].ch[];
return nw;
}
il void delet(ri x)
{
ri pr=ask_pr_yg(x),lst=ask_lst_yg(x);
splay(pr,);splay(lst,pr);
tr[tr[rt].ch[]].ch[]=;
} int main()
{
// freopen("2286.in","r",stdin);freopen("2286.out","w",stdout);
n=read();insert(inf);insert(-inf);
while(n--)
{
cnt+=a?:-;a=read(),b=read();
if(!cnt){insert(b);continue;}
if(cnt>)
{
if(a){insert(b);continue;}
ri pr=ask_pr(b),lst=ask_lst(b);
if(abs(tr[lst].val-b)<abs(b-tr[pr].val))
{
as+=abs(tr[lst].val-b);as%=mod;
delet(tr[lst].val);
}
else
{
as+=abs(b-tr[pr].val);as%=mod;
delet(tr[pr].val);
}
}
else
{
if(!a){insert(b);continue;}
ri pr=ask_pr(b),lst=ask_lst(b);
if(abs(tr[lst].val-b)<abs(b-tr[pr].val))
{
as+=abs(tr[lst].val-b);as%=mod;
delet(tr[lst].val);
}
else
{
as+=abs(b-tr[pr].val);as%=mod;
delet(tr[pr].val);
}
}
}
printf("%d\n",as);
return ;
}
随机推荐
-
DISCUZ 自定义模板
DISCUZ 自定义模板 模板安装和维护 安装新模板 将模板template打包放在对应目录:template/ 后台 -> 界面 -> 风格管理 , 安装模板 后台 -> 界面 - ...
-
统计知识选讲（一）——主成分分析（PCA）的思想
主成分分析的主要目的是希望用较少的变量去解释原来资料中的大部分变异,将我们手中许多相关性很高的变量转化成彼此相互独立或不相关的变量,从而达到降维的目的.在原始数据“预处理”阶段通常要先对它们采用PCA ...
-
常见的CSS
/***** Selector Hacks ******/ /* IE6 and below */ * html #uno { color: red } /* IE7 */ *:first-child ...
-
[转] 那些在使用webpack时踩过的坑
用webpack的过程,就是一个不断入坑和出坑的过程.回望来时路,一路都是坑啊!现把曾经趟过的那些坑整理出来,各位看官有福了~ 文章末尾有我用到的依赖的版本信息,若你发现某个问题与我在本文中的描述不一 ...
-
【JS单元测试】Qunit 和 jsCoverage使用方法
近日在网上浏览过很多有关js单元测试相关的文档,工具,但是,针对Qunit 和 jsCoverage使用方法,缺少详细说明,对于初入前端的人来说,很难明白其中的意思,特此整理这篇文章,希望 ...
-
ubuntu下java的安装即使用
1.首先在官方网站(点击可以下载)下载最新的JDK,要选用self extracting installer 2.在/usr/下新建java目录,把下载的文件放到这个目录下 sudo mkdir /u ...
-
rbac 权限分配， 基于formset实现，批量增加
这里需要两个知识点: - formset - 自动发现项目中的URL1. 什么是formset: Django中 form组件 或 ModelForm组件,用于做一个表单的验证. 接收前端form表单 ...
-
【转】Mysql事务，并发问题，锁机制
转自:http://www.cnblogs.com/fidelQuan/p/4549068.html 1.什么是事务 事务是一条或多条数据库操作语句的组合,具备ACID,4个特点. 原子性:要不全部成 ...
-
【刷题】BZOJ 3512 DZY Loves Math IV
Description 给定n,m,求 模10^9+7的值. Input 仅一行,两个整数n,m. Output 仅一行答案. Sample Input 100000 1000000000 Sampl ...
-
使用CocoaPods来做iOS程序的包依赖管理
前言 每种语言发展到一个阶段,就会出现相应的依赖管理工具, 或者是*代码仓库.比如 Java: maven,Ivy Ruby: gems Python: pip, easy_install Node ...