从哪里开始,从哪里结束

P1001 A+B Problem

skywang @ 2019-11-19 20:36:58

//A+B Problem 2019.11.19 
//从哪里开始,从哪里结束
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define int long long
using namespace std;
struct tree_point{
    int lson,rson,size,heap,v;
}t[400001];
int root=0,cnt=0;
struct son{
    int lson,rson;
};

void update(int k){
    t[k].size=t[t[k].lson].size+t[t[k].rson].size+1;
}

int Rank(int k,int x){
    if (!k) return 0;
    int rt=root;
    if (x>t[k].v) return Rank(t[k].rson,x)+t[t[k].lson].size+1;
    else return Rank(t[k].lson,x);
}/*
int Rank(int k,int x){ 
    int tmp=root,ans=0;
    while(tmp){
        if(x>t[tmp].v){
            ans+=t[t[tmp].lson].size+1;
            tmp=t[tmp].rson;
        }
        else tmp=t[tmp].lson;
    }
    return ans;
}*/
int merge(int Lson,int Rson){
    if (Lson==0) return Rson;
    if (Rson==0) return Lson;
    if(t[Lson].heap<t[Rson].heap){   
        t[Lson].rson=merge(t[Lson].rson,Rson);
        update(Lson);
        return Lson;
    }else{      
        t[Rson].lson=merge(Lson,t[Rson].lson);
        update(Rson);
        return Rson;
    }
}

son cut(int k,int x){
    son ans={0,0};
    if (k==0) return ans;
    if (x>=t[t[k].lson].size+1){
        ans=cut(t[k].rson,x-t[t[k].lson].size-1);
        t[k].rson=ans.lson;
        ans.lson=k;
    }else{
        ans=cut(t[k].lson,x);
        t[k].lson=ans.rson;
        ans.rson=k;
    }
    update(k);
    return ans;
}

void ins(int x){
    t[++cnt].v=x;
    t[cnt].heap=rand();
    t[cnt].size=1;
    son s=cut(root,Rank(root,x));
    int rt=merge(s.lson,cnt);
    root=merge(rt,s.rson);
}
void del(int x){
    son s=cut(root,Rank(root,x));
    son ss=cut(s.rson,1);
    root=merge(s.lson,ss.rson);
}

int find(int k,int x){
    if (x==t[t[k].lson].size+1) return t[k].v;
    if (x<t[t[k].lson].size+1) return find(t[k].lson,x);
    if (x>t[t[k].lson].size+1) return find(t[k].rson,x-1-t[t[k].lson].size);
}
int smaller(int x){
    son s=cut(root,Rank(root,x));
    int tt=find(s.lson,t[s.lson].size);
    root=merge(s.lson,s.rson);
    return tt;
}
int bigger(int x){
    son s=cut(root,Rank(root,x+1));
    int tt=find(s.rson,1);
    root=merge(s.lson,s.rson);
    return tt;
}
signed main(){
    int opt=1,x;
    for (int i=1;i<=2;i++){
        cin>>x;
        switch(opt){
            case 1:ins(x);break;
            case 2:del(x);break;
            case 3:cout<<Rank(root,x)+1<<endl;break;
            case 4:cout<<find(root,x)<<endl;break;
            case 5:cout<<smaller(x)<<endl;break;
            case 6:cout<<bigger(x)<<endl;break;
        }
    }
    cout<<find(root,1)+find(root,2)<<endl;
    return 0;
} 

by AFO_9 @ 2019-11-19 20:39:26

走好


by _SeeleVollerei_ @ 2019-11-19 20:43:59

@skywang 泪别


by tobie @ 2019-11-19 20:49:53

你牛,A+B Problem 能写成玄学代码


by 梦里调音 @ 2019-11-19 20:52:43

加油!


by tobie @ 2019-11-19 20:52:44

牛牪犇


by 谬悠 @ 2019-11-19 20:58:14

走好qwq


by QAQQWQ @ 2019-11-19 20:58:53

走好qaq


by ____OccDreamer @ 2019-11-19 21:09:27

走好......


by __wfx @ 2020-01-03 20:17:13

走好


by kkk的脑残粉 @ 2020-01-24 10:46:55

走好


| 下一页