CF 809D Hitchhiking in the Baltic States—

题目：http://codeforces.com/contest/809/problem/D

如果值是固定的，新加入一个值，可以让第一个值大于它的那个长度的值等于它。

如今值是一段区间，就对区间内的dp值都有影响；中间的那些的值变成了上一个的值+1，左边 l 处多了一个点，右边第一个大于等于 r 的点被删掉。

用 splay 维护这些点；点的个数就是最多能达到的长度。

又好好学习了一番 splay 。带有标记的原来是要在那个 splay 操作前那样一条链地 pushdown下来呀。

非常奇怪的是按题解写法，找第一个小于边界的值，再找右边界那个值的 nxt ，就没问题；而自己找第一个大于等于的值，就会TLE。那个T的点是所有 l , r 都是 1,1e9 的，也许和这个有关？

加“哨兵”十分方便。

别忘了 insert 也要 splay 。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=3e5+;

int n,c[N][],tg[N],val[N],fa[N],ans,rt,tot;

inline int rdn()

{

    int ret=;bool fx=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return fx?ret:-ret;

}

inline void rotate(int x,int &k)

{

    int y=fa[x],z=fa[y];

    if(y==k) k=x;

    else c[z][y==c[z][]]=x;

    int d=(x==c[y][]);

    fa[x]=z; fa[c[x][!d]]=y; fa[y]=x;

    c[y][d]=c[x][!d]; c[x][!d]=y;

}

inline void down(int cr)

{

    if(!tg[cr])return;

    int ls=c[cr][],rs=c[cr][];

    if(ls) tg[ls]+=tg[cr],val[ls]+=tg[cr];

    if(rs) tg[rs]+=tg[cr],val[rs]+=tg[cr];

    tg[cr]=;

}

inline void push(int cr)

{

    if(fa[cr]) push(fa[cr]);

    down(cr);

}

inline void splay(int x,int &k)

{

    push(x);

    while(x!=k)

    {

        int y=fa[x],z=fa[y];

        if(y!=k)

        {

            if((x==c[y][])^(y==c[z][]))

                rotate(x,k);

            else rotate(y,k);

        }

        rotate(x,k);

    }

}

inline int lower(int x)

{

    int cr=rt,ret=;

    while(cr)

    {

        down(cr);

        if(val[cr]<x)

            ret=cr,cr=c[cr][];

        else cr=c[cr][];

//        if(val[cr]>=x)

//            ret=cr,cr=c[cr][0];

//        else cr=c[cr][1];

    }

    return ret;

}

inline void del(int cr)

{

    splay(cr,rt);

    int pr=c[cr][],nt=c[cr][];

    while(c[pr][])pr=c[pr][];

    while(c[nt][])nt=c[nt][];

    splay(pr,rt); splay(nt,c[rt][]);

    fa[cr]=; c[nt][]=;

}

inline void insert(int &cr,int p,int pr)//&

{

    if(!cr){fa[cr=++tot]=pr;val[cr]=p;splay(cr,rt);return;}//

    down(cr);

    insert(c[cr][val[cr]<p],p,cr);

}

int nxt(int x)

{

    splay(x,rt);//

    int cr=c[x][];

    while(c[cr][])cr=c[cr][];

    return cr;

}

inline void solve(int l,int r)

{

    int x=lower(l),y=lower(r),t=nxt(y);

    if(x!=y)

    {

        splay(x,rt); splay(t,c[rt][]);

//        val[x]++;

        tg[c[t][]]++; val[c[t][]]++;

    }

    if(t!=) del(t),ans--;

//    if(y!=2) del(y),ans--;

    insert(rt,l,); ans++;

}

int main()

{

    n=rdn();

    val[]=-1e9-; val[]=1e9+;

    fa[]=; c[][]=; tot=; rt=;

    for(int i=,l,r;i<=n;i++)

    {

        l=rdn(); r=rdn();

        solve(l,r);

    }

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

    return ;

}

巴特西

CF 809D Hitchhiking in the Baltic States——splay+dp

最新文章

热门文章