AC日记——最小正子段和 51nod 1065

最小正子段和

思路：

　　找最小的大于0的sum[j]-sum[i](j>i)；

　　高级数据结构(splay)水过；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 50005

#define ll long long

#define INF 0x7fffffff

struct TreeNodeType {

    ll w,key,opi,size,ch[];

};

struct TreeNodeType tree[maxn];

ll n,tot,root,sum[maxn],ans=INF;

inline void in(ll &now)

{

    ll if_z=;now=;

    char Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

inline ll getson(ll x)

{

    return x==tree[tree[x].opi].ch[];

}

inline void updata(ll x)

{

    tree[x].size=tree[x].w;

    if(tree[x].ch[]) tree[x].size+=tree[tree[x].ch[]].size;

    if(tree[x].ch[]) tree[x].size+=tree[tree[x].ch[]].size;

}

void rotate(ll now)

{

    ll opi=tree[now].opi,fopi=tree[opi].opi,pos=getson(now);

    tree[opi].ch[pos]=tree[now].ch[pos^];

    if(tree[opi].ch[pos]) tree[tree[opi].ch[pos]].opi=opi;

    tree[now].ch[pos^]=opi,tree[now].opi=fopi;

    if(opi) tree[fopi].ch[getson(opi)]=now;

    tree[opi].opi=now,updata(opi),updata(now);

}

void splay(ll now)

{

    if(now==root) return ;

    for(ll opi;opi=tree[now].opi;rotate(now))

    {

        if(tree[opi].opi) rotate(getson(now)==getson(opi)?opi:now);

    }

    root=now;

}

void insert(ll x)

{

    if(!root)

    {

        root=++tot;

        tree[root].w=;

        tree[root].key=x;

        tree[root].size=;

        return ;

    }

    ll now=root,opi=;

    while()

    {

        if(x==tree[now].key)

        {

            tree[now].w++,tree[now].size++;

            splay(now);

            return ;

        }

        opi=now,now=tree[now].ch[x>tree[now].key];

        if(now==)

        {

            now=++tot;

            tree[now].w=;

            tree[now].key=x;

            tree[now].size=;

            tree[now].opi=opi;

            tree[opi].ch[x>tree[opi].key]=now;

            splay(now);

            return ;

        }

    }

}

ll pre()

{

    if(tree[root].w>) return tree[root].key;

    ll now=tree[root].ch[];if(!now) return ;

    while(tree[now].ch[]!=) now=tree[now].ch[];

    return tree[now].key;

}

int main()

{

    in(n);insert();

    for(ll i=;i<=n;i++)

    {

        in(sum[i]);

        sum[i]+=sum[i-];

        insert(sum[i]);

        ll pos=pre();

        if(sum[i]-pos>) ans=min(ans,sum[i]-pos);

    }

    cout<<ans;

    return ;

}