平衡树板子题
算法1
(暴力枚举) $O(nm)$
直接爆草,显然过不了
算法2
(平衡树+STL) $O(mlogn,但是常数比较大)$
不相邻可以用平衡树直接维护序列,每次查找前驱后继直接修改最小值即可
相邻就搞两个堆,因为每次加入一个数,会切断一对数的相邻关系,并同时增加一对数的相邻关系,那我们一个堆维护增加的,一个堆维护要切断的,每次查询前把堆顶相同元素弹掉就好了
但是好像常数有点大,于是试图卡常,然后卡常不成功,试图手动O2,水过了(大雾
算法3
(俩平衡树) $O(mlogn,但是常数比较小)$
不相邻还是一样
相邻与堆同样的思路,但是要搞个删除操作,懒得写了(
C++ 代码
下面是 手动O2 代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define min(a,b) ((a<b)?a:b)
using namespace std;
#define int long long
const int N=1e6+10;
const int INF=1e9;
inline int read() {
int r=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){r=(r<<3)+(r<<1)+(ch^48);ch=getchar();}
return r*f;
}
int n,m;
int a[N],lst[N],ans2=INF;
struct Tree {
int s[2],size;
int p,key;
int ct;
inline void init(int _p,int _key) {
p=_p,key=_key;
size=1,ct=1;
};
}tr[N];
int cnt,root;
inline void pushup(int x) {
tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}
inline void rotate(int x) {
int y=tr[x].p,z=tr[y].p;
int k=(tr[y].s[1]==x);
tr[z].s[tr[z].s[1]==y]=x,tr[x].p=z;
tr[y].s[k]=tr[x].s[k^1],tr[tr[x].s[k^1]].p=y;
tr[y].p=x,tr[x].s[k^1]=y;
pushup(x),pushup(y);
}
inline void splay(int x,int k) {
while(tr[x].p!=k) {
int y=tr[x].p,z=tr[y].p;
if(z!=k) {
if((tr[y].s[1]==x)^(tr[z].s[1]==y)) rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k) root=x;
}
inline int get_k(int k) {
int u=root;
while(1) {
if(tr[tr[u].s[0]].size>=k) u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+1==k) return u;
else k-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
}
}
inline int get_sub(int k) {
if(!tr[k].s[0]) return -1;
if(tr[k].ct>1) return tr[k].key;
int u=tr[k].s[0];
while(tr[u].s[1]) u=tr[u].s[1];
return tr[u].key;
}
inline int get_pre(int k) {
if(!tr[k].s[1]) return -1;
if(tr[k].ct>1) return tr[k].key;
int u=tr[k].s[1];
while(tr[u].s[0]) u=tr[u].s[0];
return tr[u].key;
}
unordered_map<int,int> mp;
void insert(int x) {
int u=root,p=0;
while(u) {
if(tr[u].key==x) {
tr[u].ct++;
splay(u,0);
return;
}
p=u,u=tr[u].s[x>tr[u].key];
}
u=++cnt;
if(p) tr[p].s[x>tr[p].key]=u;
tr[u].init(p,x);
mp[x]=cnt;
splay(u,0);
}
priority_queue<int,vector<int>,greater<int> > hp,hpdel;
int x,k;
char s[15];
signed main() {
n=read(),m=read();
insert(-INF),insert(INF);
for(int i=1;i<=n;++i) {
a[i]=read();
insert(a[i]);
ans2=min(ans2,min(abs(a[i]-get_pre(mp[a[i]])),abs(a[i]-get_sub(mp[a[i]]))));
if(i!=1) hp.push(abs(a[i]-a[i-1]));
lst[i]=a[i];
}
while(m--) {
scanf("%s",s);
if(s[0]=='I') {
x=read(),k=read();
insert(k);
ans2=min(ans2,min(abs(k-get_pre(mp[k])),abs(k-get_sub(mp[k]))));
hp.push(abs(lst[x]-k));
if(x+1<=n){
hp.push(abs(k-a[x+1]));
hpdel.push(abs(lst[x]-a[x+1]));
}
lst[x]=k;
}
else if(s[4]=='G') {
while(hp.size()&&hpdel.size()&&(hp.top()==hpdel.top())) hp.pop(),hpdel.pop();
printf("%lld\n",hp.top());
}
else printf("%lld\n",ans2);
}
return 0;
}
我是nt还搞个ct搞个map在这里数数