主席树 - Luogu 1001 A+B problem

看着大佬们的解法我瑟瑟发抖

我用主席树写一写吧

#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

inline int gotcha()

{

    register int _a=0;bool _b=1;register char _c=getchar();

    while((_c<'0' || _c>'9') && _c!='-')_c=getchar();

    if(_c=='-')_b=0,_c=getchar();

    while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar();

    return _b?_a:-_a;

}

const int _ = 1000002,__ = 20*_;

int a[_],n,root[__]={0},ch[__][2]={0},da[__],cnt;

inline void plant(int &d,int l,int r)

{

    d=++cnt;

    if(l==r){da[d]=a[l];return;}

    int mid=(l+r)>>1;

    plant(ch[d][0],l,mid),plant(ch[d][1],mid+1,r);

}

inline void insert(int &d,int pre,int l,int r,int tar,int dat)

{

    d=++cnt,ch[d][0]=ch[pre][0],ch[d][1]=ch[pre][1],da[d]=da[pre];

    if(l==r){da[d]=dat;return;}

    int mid=(l+r)>>1;

    if(tar<=mid)insert(ch[d][0],ch[pre][0],l,mid,tar,dat);

    else insert(ch[d][1],ch[pre][1],mid+1,r,tar,dat);

}

inline int finder(int d,int l,int r,int tar)

{

    if(l==r)return da[d];

    int mid=(l+r)>>1;

    if(tar<=mid)return finder(ch[d][0],l,mid,tar);

    else return finder(ch[d][1],mid+1,r,tar);

}

int main()

{

    register int i;

    n=2;

    for(i=1;i<=n;i++)a[i]=gotcha();

    plant(root[0],1,n);

    i=finder(root[0],1,n,1)+finder(root[0],1,n,2);

    printf("%d\n",i);

    return 0;

}

常数巨大，不要被我误导……

巴特西

主席树 - Luogu 1001 A+B problem

最新文章

热门文章