Loading...

A+B Problem 题解 qwq

check评论:2 条 remove_red_eye浏览量:762 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-26

普通版:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b;
    return 0;
}

平衡树版:

#include<bits/stdc++.h> 
#define MAXN 300006 
using namespace std; 
struct Node 
{ 
    int val,size; 
    Node *ls,*rs; 
    void pushup() 
    { 
        if(ls==NULL)
        {
            return ; 
        }    
        size=ls->size+rs->size; 
        val=rs->val;
    } 
    Node(int v,int s,Node *l,Node *r):val(v),size(s),ls(l),rs(r){}
    Node(){} 
}pool[MAXN]; 
int cnt=0;
Node *root=NULL; 
Node *NewNode(int val,int size,Node *ls,Node *rs) 
{ 
    pool[cnt]=Node(val,size,ls,rs); 
    return &pool[cnt++]; 
} 
int find(int k,Node *rt)
{ 
    if(rt->size==1)
    {
        return rt->val; 
    }
    if(k<=rt->ls->size)
    {
        return find(k,rt->ls);
    }     
    else 
    {
        return find(k-rt->ls->size,rt->rs); 
    }
} 
int Rank(int x,Node *rt)
{ 
    if(rt->size==1) 
    { 
        return 1; 
    } 
    else 
    { 
        if(x<=rt->ls->val)
        { 
            return Rank(x,rt->ls); 
        } 
        else
        { 
            return Rank(x,rt->rs)+rt->ls->size; 
        } 
    } 
} 
inline void maintain(Node *rt)
{ 
    if(rt->ls->size>rt->rs->size*4) 
    { 
        rt->rs=NewNode(rt->rs->val,rt->ls->rs->size+rt->rs->size,rt->ls->rs,rt->rs); 
        Node *tmp=rt->ls;
        rt->ls=rt->ls->ls;
        *tmp=*rt->rs;
        rt->rs=tmp;//垃圾回收,下面同理 
        cnt--; 
    } 
    else if(rt->ls->size*4<rt->rs->size) 
    { 
        rt->ls=NewNode(rt->rs->ls->val,rt->rs->ls->size+rt->ls->size,rt->ls,rt->rs->ls); 
        Node *tmp=rt->rs;
        rt->rs=rt->rs->rs;
        *tmp=*rt->ls;
        rt->ls=tmp; 
        cnt--; 
    } 
} 
void ins(int val,Node *&rt)
{ 
    if(rt==NULL)
    {
        rt=NewNode(val,1,NULL,NULL);
        return ;
    } 
    if(rt->size==1) 
    { 
        rt->ls=NewNode(min(val,rt->val),1,NULL,NULL); 
        rt->rs=NewNode(max(val,rt->val),1,NULL,NULL); 
    } 
    else 
    { 
        if(val>rt->ls->val)
        {
            ins(val,rt->rs);
        } 
        else 
        {
            ins(val,rt->ls); 
        }
    } 
    rt->pushup(); 
    maintain(rt); 
} 
void del(Node *rt,Node *fa,int val)
{ 
    if(rt->size==1)
    {    
        *fa=fa->ls->val==val?*fa->rs:*fa->ls;
    }     
    else 
    { 
        if(val<=rt->ls->val)
        {
            del(rt->ls,rt,val);
        } 
        else 
        {
            del(rt->rs,rt,val); 
        }
    } 
    rt->pushup(); 
} 
int main() 
{ 
    root=NewNode(2147483647,1,NULL,NULL); 
    int a,b;
    cin>>a>>b;
    ins(a,root);
    ins(b,root);
    if(a<=b)
    {
        swap(a,b);
    }
    printf("%d",find(Rank(a,root)-1,root)+find(Rank(b+1,root),root));
    del(root,NULL,a);
    del(root,NULL,b);
}

qwq

已有 2 条评论

正在回复给  
去登陆?

   点击刷新验证码

    蒟蒻
    2018 - 05 - 26 23 : 29

    平衡树版真是没谁了

    rainman
    2018 - 05 - 30 12 : 12

    这是啥

标签云

文章留名