CDQZ Challenge 8

앞에서 말 했 듯 이 "CDQZ" 시리즈 의 제목 데 이 터 는 절대 양심 (심혈 을 기울 여 233) 입 니 다. 인터넷 주 소 를 제출 할 때 필요 하 다 면 개인 편지 본 을 보 내 주세요.1008: Challenge 8 보기 제출 통계 질문 총 시간 제한: 10000 ms 단일 테스트 포인트 시간 제한: 1000 ms 메모리 제한: 262144 kB 는 N 길이 의 수열 에 설명 하고 M 번 조작 이 있 으 며 매번 조작 은 다음 과 같은 세 가지 중 하나 입 니 다.
(1) 숫자 를 삽입 합 니 다. 존재 하면 무시 합 니 다.
(2) 하나의 수 를 삭제 하고 존재 하지 않 으 면 무시 합 니 다.
(3) 수열 중 임의의 두 수의 차 절대 치 의 최소 치 를 구한다.
첫 줄 의 정수 N 과 M 두 개 를 입력 하 십시오.두 번 째 줄 N 의 정 수 는 이 수열 을 나타 낸다.중복 되 는 숫자 가 있 으 면 하나 로 간주 하도록 주의 하 세 요.다음 M 줄 은 줄 마다 시작 하 는 문자 입 니 다. 이 문자 가 'I' 라면 삽입 동작 을 표시 하고 다음 정수 x 는 숫자 x 를 삽입 하 는 것 을 표시 합 니 다.이 문자 가 'D' 이면 삭제 동작 을 표시 하고 다음 정수 x 는 숫자 x 를 삭제 하 는 것 을 표시 합 니 다.이 문자 가 'Q' 라면 질문 동작 을 표시 합 니 다. 수열 에 있 는 임의의 두 수의 차 이 를 구 하 는 절대 값 의 최소 값 입 니 다. 최소 두 개의 숫자 가 존재 하지 않 으 면 출력 - 1.출력 은 모든 질문 동작 에 대해 한 줄 을 따로 출력 하여 답 을 표시 합 니 다.샘플 입력 5 3 1 9 3 7 5 Q I 2 Q 샘플 출력 2 1 알림 1 < = N < = 10 ^ 5, 1 < = M < = 10 ^ 5, 입력 보증 합 법 적 이 며 모든 정 수 는 기호 32 비트 정형 으로 저장 할 수 있 습 니 다.
문제 풀이: treap / splay + 더미, treap 에 하나의 수 를 추가 할 때마다 더미 에 두 개의 요 소 를 추가 합 니 다. 현재 수 - 전구, 후계 - 현재 수, 하나의 요 소 를 삭제 합 니 다: 후계 - 전구;삭제 하면 거꾸로.쌓 기 우선 대기 열 로 이 루어 집 니 다. 삭제 할 수 없습니다. 맵 으로 표시 할 수 있 습 니 다. 질문 할 때 판단 하면 됩 니 다.
메모: 원래 수열 뒤에 새로운 요 소 를 삽입 하려 면 배열 을 많이 열 어야 합 니 다. 그렇지 않 으 면 오전 에 orz 가 없습니다.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+2;
int n,m,tim,root;
int pre,suc;
priority_queue<int,vector<int>,greater<int> > q;
map<int ,int > d;
inline int read() {
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
struct DATA {
    int l,r,v,rnd;
    inline DATA() {l=r=0;}
}node[maxn<<1];
inline void rturn(int &k) {
    int t=node[k].l;
    node[k].l=node[t].r;
    node[t].r=k;
    k=t;
}
inline void lturn(int &k) {
    int t=node[k].r;
    node[k].r=node[t].l;
    node[t].l=k;
    k=t;
}
bool Insert(int &k,int x) {
    if (k==0) {
        k=++tim;
        node[k].v=x,node[k].rnd=rand();
        return true;
    }
    if (x==node[k].v) return false;
    else if (x>node[k].v) {
        int t=Insert(node[k].r,x);
        if (node[node[k].r].rndreturn t;
    }
    else {
        int t=Insert(node[k].l,x);
        if (node[node[k].l].rndreturn t;
    }
}
bool del(int &k,int x) {
    if (k==0) return false;
    if (x==node[k].v) {
        bool j=true;
        if (!node[k].l||!node[k].r) k=node[k].l+node[k].r;
        else if (node[node[k].l].rndelse lturn(k),j=del(k,x);
        return j;
    }
    else if (x>node[k].v) return del(node[k].r,x);
    else return del(node[k].l,x);
}
inline void pro(int k,int x) {
    while (k) {
        if (node[k].velse k=node[k].l;
    }
}
inline void sub(int k,int x) {
    while (k) {
        if (node[k].v>x) suc=k,k=node[k].l;
        else k=node[k].r;
    }
}
inline void update1(int val) {
    pre=0,suc=0;
    pro(root,val),sub(root,val);
    if (pre) q.push(val-node[pre].v);
    if (suc) q.push(node[suc].v-val);
    if (pre&&suc) ++d[node[suc].v-node[pre].v];
}
inline void update2(int val) {
    pre=0,suc=0;
    pro(root,val),sub(root,val);
    if (pre) ++d[val-node[pre].v];
    if (suc) ++d[node[suc].v-val];
    if (pre&&suc) q.push(node[suc].v-node[pre].v);
}
inline void mt() {
    while (1) {
        if (q.empty()) {puts("-1");return ;}
        int t=q.top();
        if (d[t])
            while (d[t]) q.pop(),--d[t];//delete
        if (q.empty()) {puts("-1");return ;}
        if (t==q.top()) {printf("%d
",t);return ;}
    }
}
int main() {
//  freopen("C8.in","r",stdin);
    n=read(),m=read();
    tim=0,root=0,d.clear();
    for (register int i=1;i<=n;++i) {
        int val=read();
        bool j=Insert(root,val);
        if (j) update1(val);
    }
    for (register int i=1;i<=m;++i) {
        char ss;
        while (!isalpha(ss=getchar()));
        if (ss=='I') {
            int val=read();
            bool j=Insert(root,val);
            if (j) update1(val);
        }
        else if (ss=='D') {
            int val=read();
            bool j=del(root,val);
            if (j) update2(val);
        }
        else mt();
    }
    return 0;
}