bzoj 1058 bst
2024-08-26 12:51:09
因为是数列的维护,所以我们可以考虑用splay来维护,每次在x插入的时候就在x+1前面插入就行了,然后用bst来维护两问的答案,但是应该会tle。我们来考虑这个问题的性质,首先因为这个数列没有删除操作,所以每个数插入进去之后就不会出来了,换句话说,就是假设insert(x,y)那么y这个值和前面的那个数可以更新相邻差值的答案,且这个不会因为其他的插入操作而使得这个差值消失(消失值类似(x,y)插入,那么之前在x处插入的点与x+1的差值会消失),所以我们只需要存储每个位置最后插入的数,那么对于一个插入(x,y)我们只需要判断x位置是否插入过值然后讨论就行了。那么对于另一个全局差值的更新我们只需要用bst维护所有插入的数,每插入一个数就找前驱后继来更新答案就行了。因为这个答案是递减的,所以当答案为0的时候不用更新就行了,这样大概可以快3-4s。
反思:很早的时候用pascal写了splay的,满满的tle,然后转了C++之后用的set和map,快了好多,也好写了好多= =
/**************************************************************
Problem: 1058
User: BLADEVIL
Language: C++
Result: Accepted
Time:9924 ms
Memory:40700 kb
****************************************************************/
//By BLADEVIL
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#define maxn 1000010
#define inf (~0U>>1)
using namespace std;
int n,m,ans;
int a[maxn],b[maxn];
char c[];
map<int,int>ms;
set<int>bt;
void update(int x){
if (bt.count(x)) {
ans=; return;
}
set<int>::iterator p=bt.upper_bound(x);
if (p!=bt.end()) ans=min(ans,abs(*p-x));//,printf("%d->%d ",x,*p);
--p;
if (*p!=-inf) ans=min(ans,abs(*p-x));//,printf("%d<-%d",x,*p); printf("\n");
bt.insert(x);
}
void insert(int x){
map<int,int>::iterator p=ms.find(x);
if (p!=ms.end()) p->second++; else ms.insert(pair<int,int>(x,));
}
void erase(int x){
map<int,int>::iterator p=ms.find(x);
if (p->second==) ms.erase(p); else p->second--;
}
void printbt(){
for (set<int>::iterator p=bt.begin();p!=bt.end();p++) printf("%d ",*p); printf("\n");
}
void printms(){
for (map<int,int>::iterator p=ms.begin();p!=ms.end();p++) printf("|%d %d\n",p->first,p->second);
}
int main(){
ans=inf; bt.insert(-inf);
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&a[i]);
for (int i=;i<n;i++) insert(abs(a[i]-a[i+]));
for (int i=;i<=n;i++) {
if (bt.count(a[i])) {
ans=; break;
}
update(a[i]);
}
//printms(); printbt();
while (m--){
scanf("%s",&c);
if (c[]=='I'){
int x,y;
scanf("%d%d",&x,&y);
if (x==n){
if (b[x]) insert(abs(b[x]-y)); else insert(abs(a[x]-y));
} else {
if (b[x]){
erase(abs(b[x]-a[x+]));
insert(abs(b[x]-y)); insert(abs(a[x+]-y));
} else {
erase(abs(a[x]-a[x+]));
insert(abs(a[x]-y)); insert(abs(a[x+]-y));
}
}
b[x]=y;
if (ans) update(y);
} else
if (c[]=='G') {
printf("%d\n",ms.begin()->first);
} else printf("%d\n",ans);
}
return ;
}
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Time_Limit_Exceed
****************************************************************/
//By BLADEVIL
var
n, m :longint;
root, sroot :longint;
father, size :array[-..] of longint;
tree, a :array[-..] of int64;
son :array[-..,..] of longint;
numt, t, st :longint;
tot :longint;
left, right, b_size :array[..] of longint;
key :array[..] of int64;
print :int64;
function abs(x:int64):int64;
begin
if x< then exit(-x) else exit(x);
end;
function min(a,b:int64):int64;
begin
if a>b then min:=b else min:=a;
end;
procedure update(x:longint);
begin
size[x]:=size[son[x][]]+size[son[x][]]+;
end;
function build(l,r:longint):longint;
var
mid :longint;
begin
mid:=(l+r)>>;
build:=mid;
tree[mid]:=a[mid];
if mid->=l then
begin
son[mid][]:=build(l,mid-);
father[son[mid][]]:=mid;
end;
if mid+<=r then
begin
son[mid][]:=build(mid+,r);
father[son[mid][]]:=mid;
end;
update(mid);
end;
procedure rotate(x,y:longint);
var
f :longint;
begin
f:=father[x];
son[f][y]:=son[x][y xor ];
father[son[x][y xor ]]:=f;
if f=root then root:=x else
if f=son[father[f]][] then
son[father[f]][]:=x else
if f=son[father[f]][] then
son[father[f]][]:=x;
son[x][y xor ]:=f;
father[x]:=father[f];
father[f]:=x;
update(f);
update(x);
end;
procedure splay(x,y:longint);
var
u, v :longint;
begin
while father[x]<>y do
if father[father[x]]=y then
rotate(x,ord(x=son[father[x]][])) else
begin
if x=son[father[x]][] then u:= else u:=-;
if father[x]=son[father[father[x]]][] then v:= else v:=-;
if u*v= then
begin
rotate(father[x],ord(x=son[father[x]][]));
rotate(x,ord(x=son[father[x]][]));
end else
begin
rotate(x,ord(x=son[father[x]][]));
rotate(x,ord(x=son[father[x]][]));
end;
end;
update(x);
end;
function find(x:int64):int64;
var
t :longint;
begin
t:=root;
while true do
begin
if size[son[t][]]+=x then exit(t) else
if size[son[t][]]+>x then t:=son[t][] else
begin
x:=x-(size[son[t][]]+);
t:=son[t][];
end;
end;
end;
procedure left_rotate(var t:longint);
var
k :longint;
begin
k:=right[t];
right[t]:=left[k];
left[k]:=t;
b_size[k]:=b_size[t];
b_size[t]:=b_size[left[t]]+b_size[right[t]]+;
t:=k;
end;
procedure right_rotate(var t:longint);
var
k :longint;
begin
k:=left[t];
left[t]:=right[k];
right[k]:=t;
b_size[k]:=b_size[t];
b_size[t]:=b_size[left[t]]+b_size[right[t]]+;
t:=k;
end;
procedure maintain(var t:longint;flag:boolean);
begin
if not flag then
begin
if b_size[left[left[t]]]>b_size[right[t]] then
right_rotate(t) else
if b_size[right[left[t]]]>b_size[right[t]] then
begin
left_rotate(left[t]);
right_rotate(t);
end else exit;
end else
begin
if b_size[right[right[t]]]>b_size[left[t]] then
left_rotate(t) else
if b_size[left[right[t]]]>b_size[left[t]] then
begin
right_rotate(right[t]);
left_rotate(t);
end else exit;
end;
maintain(left[t],false);
maintain(right[t],true);
maintain(t,true);
maintain(t,false);
end;
procedure insert(var t:longint;v:int64);
begin
if t= then
begin
inc(tot);
t:=tot;
key[t]:=v;
b_size[t]:=;
left[t]:=;
right[t]:=;
end else
begin
b_size[t]:=b_size[t]+;
if v<key[t] then insert(left[t],v) else insert(right[t],v);
maintain(t,v>=key[t]);
end;
end;
function pred(var t:longint;v:int64):int64;
begin
if t= then exit(maxlongint>>);
if key[t]>v then pred:=pred(left[t],v) else
begin
pred:=pred(right[t],v);
if pred=maxlongint>> then exit(key[t]);
end;
end;
function succ(var t:longint;v:int64):int64;
begin
if t= then exit(maxlongint>>);
if key[t]<v then succ:=succ(right[t],v) else
begin
succ:=succ(left[t],v);
if succ=maxlongint>> then exit(key[t]);
end;
end;
function delete(var t:longint;v:int64):int64;
begin
b_size[t]:=b_size[t]-;
if (key[t]=v) or (v>key[t]) and (right[t]=) or (v<key[t]) and (left[t]=) then
begin
delete:=key[t];
if (left[t]=) or (right[t]=) then
t:=left[t]+right[t] else
key[t]:=delete(left[t],v+);
end else
if v>=key[t] then delete:=delete(right[t],v) else delete:=delete(left[t],v);
end;
procedure change(x:longint;y:int64);
var
q, p :int64;
begin
splay(x,sroot);
p:=size[son[root][]];
p:=find(p);
splay(p,root);
delete(t,abs(tree[p]-tree[root]));
insert(t,abs(y-tree[p]));
insert(t,abs(y-tree[root]));
inc(n);
a[n]:=y;
tree[n]:=y;
son[son[root][]][]:=n;
father[n]:=son[root][];
size[n]:=;
update(son[root][]);
update(root);
p:=pred(numt,y);
q:=succ(numt,y);
if p=maxlongint>> then insert(st,abs(q-y)) else
if q=maxlongint>> then insert(st,abs(p-y)) else
insert(st,min(abs(p-y),abs(q-y)));
insert(numt,y);
end;
function mini(var t:longint):int64;
begin
if left[t]= then exit(key[t]) else exit(mini(left[t]));
end;
procedure init;
var
i :longint;
x, y :int64;
begin
readln(n,m);
for i:= to n do read(a[i]);
readln;
numt:=;
st:=;
for i:= to n do
begin
x:=succ(numt,a[i]);
y:=pred(numt,a[i]);
insert(numt,a[i]);
if x=maxlongint>> then insert(st,abs(y-a[i])) else
if y=maxlongint>> then insert(st,abs(x-a[i])) else
insert(st,min(abs(x-a[i]),abs(y-a[i])));
end;
t:=;
for i:= to n- do
insert(t,abs(a[i+]-a[i]));
fillchar(son,sizeof(son),);
sroot:=-;
inc(n);
root:=build(,n);
father[root]:=sroot;
end;
procedure main;
var
i :longint;
s :ansistring;
ch :char;
x :longint;
y :int64;
begin
print:=maxlongint>>;
for i:= to m do
begin
read(ch);
if ch='I' then
begin
s:='';
while ch<>' ' do
begin
s:=s+ch;
read(ch);
end;
readln(x,y);
change(x+,y);
end else
begin
readln(s);
if s[]='S' then
begin
if print= then
begin
writeln();
end else
begin
if mini(st)<print then print:=mini(st);
writeln(print);
end;
end else
writeln(mini(t));
end;
end;
end;
begin
init;
main;
end.
最新文章
- 连载 [ LTS + Top ]
- OpenGL学习笔记1——第一个程序
- ReactiveCocoa基础知识内容
- 学习Coding-iOS开源项目日志(一)
- AVL树插入操作实现
- SVN的目录说明
- SQL增加、删除、更改表中的字段名
- oracle row_number()
- 安装mysql 5.7 最完整版教程
- localStorage的一些简单的操作
- Bitmap、CBitmap、HBITMAP以及BITMAP的相互转换
- dll的概念 dll导出变量 函数 类
- SendMessage和PostMessage区别以及WPARAM 和 LPARAM区别
- uva 688 - Mobile Phone Coverage
- android 后台运行
- javascript高级知识点——临时作用域
- 在线xss练习平台
- js this小记
- Confluence 6 有关空间的一些提示
- 第十章I/O
热门文章
- C#中pictureBox笔记
- python2 对URL编码进行编译
- android异常Unable to instantiate activity ComponentInfo解决方法
- WPF实例,以getFiles()获取文件夹,treeview的应用
- 【Asp.Net Core】ASP.NET Core 2.0 + EF6 + Linux +MySql混搭
- 编译 python 生成静态库 libpython2.7.so
- python深浅copy-转自EVA的博客
- CentOS 压缩(打包)和解压
- CF757G Can Bash Save the Day?
- [洛谷P4312][COCI 2009] OTOCI / 极地旅行社