@[林深时x见鹿](/user/294562) 开两棵平衡树干啥，mingap用堆不就行了吗
by Diaоsi @ 2021-02-27 19:18:27
@[Diaоsi](/user/137242) 确实，但是我哪里写错了呢
by EDqwq @ 2021-02-27 19:19:35
@[林深时x见鹿](/user/294562) 没仔细看你代码，你处理相同数字的情况没？有相同数字的话minsortgap就是0了。
洛谷貌似不支持下载数据，你可以去bzoj看看，我之前数据就是上那下的
by Diaоsi @ 2021-02-27 19:23:12
@[Diaоsi](/user/137242) 我处理了，你仔细看一下呗，我调了6个小时了
by EDqwq @ 2021-02-27 19:24:31
@[林深时x见鹿](/user/294562) https://www.luogu.com.cn/paste/e49nvwan
这是我的代码，需要开 ```-O2``` 才能过
by Diaоsi @ 2021-02-27 19:25:38
@[林深时x见鹿](/user/294562) 你貌似并没有处理相同数的情况
by Diaоsi @ 2021-02-27 19:42:18
@[林深时x见鹿](/user/294562)
```cpp
/*
Author: EnderDeer
Online Judge: Luogu
*/
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
mt19937 rnd(114514);
struct Treap{
struct node{
int l;
int r;
int w;
int key;
int siz;
}e[1000010];
int cnt,rt;
int newnode(int w){
cnt ++;
e[cnt].w = w;
e[cnt].key = rnd();
e[cnt].siz = 1;
return cnt;
}
void update(int i){
e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
}
void split(int i,int w,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[i].w <= w){
x = i;
split(e[i].r,w,e[i].r,y);
}
else {
y = i;
split(e[i].l,w,x,e[i].l);
}
update(i);
}
int merge(int x,int y){
if(!x || !y)return x + y;
if(e[x].key > e[y].key){
e[x].r = merge(e[x].r,y);
update(x);
return x;
}
else {
e[y].l = merge(x,e[y].l);
update(y);
return y;
}
}
int x,y,z;
void ins(int w){
split(rt,w,x,y);
rt = merge(merge(x,newnode(w)),y);
}
void del(int w){
split(rt,w,x,z);
split(x,w - 1,x,y);
y = merge(e[y].l,e[y].r);
rt = merge(merge(x,y),z);
}
int getnum(int rk){
int now = rt;
while(now){
if(e[e[now].l].siz + 1 == rk)break;
else if(e[e[now].l].siz >= rk)now = e[now].l;
else {
rk -= e[e[now].l].siz + 1;
now = e[now].r;
}
}
return e[now].w;
}
int pre(int w){
ins(-2147483647);
split(rt,w - 1,x,y);
int now = x;
while(e[now].r)now = e[now].r;
int ans = e[now].w;
rt = merge(x,y);
del(-2147483647);
return ans;
}
int nxt(int w){
ins(2147483647);
split(rt,w,x,y);
int now = y;
while(e[now].l)now = e[now].l;
int ans = e[now].w;
rt = merge(x,y);
del(2147483647);
return ans;
}
int getsize(int w){
int res;
split(rt,w,x,z);
split(x,w - 1,x,y);
res = e[y].siz;
rt = merge(merge(x,y),z);
return res;
}
}t1,t2;//t1ÊÇÔÀ´µÄÔªËØ£¬t2ÊDzî
int n,m;
int a[500010];
int b[500010];
int minsortgap = 2147483647;
signed main(){
// freopen("9.in","r",stdin);
// freopen("data.out","w",stdout);
cin>>n>>m;
for(int i = 1;i <= n;i ++)a[i] = read(),b[i] = a[i];
t1.ins(a[n]);
for(int i = 1;i <= n - 1;i ++){
t1.ins(a[i]);
t2.ins(abs(a[i + 1] - a[i]));
}
for(int i = 1;i <= n;i ++)minsortgap = min(minsortgap,min(a[i] - t1.pre(a[i]),t1.nxt(a[i]) - a[i]));
while(m --){
string op;
int i,k;
cin>>op;
if(op == "INSERT"){
i = read(),k = read();
t2.del(abs(b[i] - a[i + 1]));
t1.ins(k);
if(t1.getsize(k)>1)minsortgap = 0;
minsortgap = min(minsortgap,min(k - t1.pre(k),t1.nxt(k) - k));
t2.ins(abs(k - b[i]));
t2.ins(abs(a[i + 1] - k));
b[i] = k;
}
if(op == "MIN_GAP"){
printf("%lld\n",t2.getnum(1));
}
if(op == "MIN_SORT_GAP"){
printf("%lld\n",minsortgap);
}
}
return 0;
}
```
这样就行了，最后两个点T掉了，不过开 ```-O2``` 就过去了
by Diaоsi @ 2021-02-27 19:44:01
@[Diaоsi](/user/137242) 我在10分钟之前就已经察觉到这一点，并且更改代码，交了上去，目前是TLE最后一个点，开O2也没用
by EDqwq @ 2021-02-27 19:46:02
@[林深时x见鹿](/user/294562) 空间开小一点，实在不行就把mingap换成堆，这样常数小
by Diaоsi @ 2021-02-27 19:47:26