AC日记——Little Elephant and Shifts codeforces 221e

E - Little Elephant and Shifts

思路：

　　一次函数线段树（疯狂debug）；

　　b不断循环左移,判断每次最小的|i-j|，a[i]=b[j]；

　　仔细观察发现，每个bi移动时，|i-j|呈现多个一次函数图像；

　　所以用线段树来维护这些一次函数图像；

　　线段树维护一次函数，当两个函数在区间没有交点时；

　　判断哪个在图像较下的位置，然后覆盖；

　　当有交点时，保留最优，将另一条传下去；

　　时间复杂度O(nlog^2n);

代码：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define maxn 100005

#define INF 0x7fffffff

struct TreeNodeType {

    int l,r,k,b,mid;

    bool if_;

};

struct TreeNodeType tree[maxn<<];

int n,ai[maxn],p[maxn],X;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

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

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

void tree_build(int now,int l,int r)

{

    tree[now].l=l,tree[now].r=r,tree[now].mid=l+r>>;

    if(l==r) return ;

    tree_build(now<<,l,tree[now].mid);

    tree_build(now<<|,tree[now].mid+,r);

}

double com(int k1,int b1,int k2,int b2)

{

    if(k1==k2) return ;

    return (double)(b2-b1)/(double)(k1-k2);

}

void tree_down(int now,int k,int b)

{

    if(!tree[now].if_)

    {

        tree[now].if_=true,tree[now].k=k,tree[now].b=b;

        return ;

    }

    double x=com(k,b,tree[now].k,tree[now].b);

    if(x<=tree[now].l||x>=tree[now].r)

    {

        double mid=(double)(tree[now].l+tree[now].r)/;

        if(mid*k+b<mid*tree[now].k+tree[now].b) tree[now].k=k,tree[now].b=b;

        return ;

    }

    if(x<=tree[now].mid)

    {

        if(k>tree[now].k) tree_down(now<<,k,b);

        else

        {

            tree_down(now<<,tree[now].k,tree[now].b);

            tree[now].k=k,tree[now].b=b;

        }

    }

    else

    {

        if(k<tree[now].k) tree_down(now<<|,k,b);

        else

        {

            tree_down(now<<|,tree[now].k,tree[now].b);

            tree[now].k=k,tree[now].b=b;

        }

    }

}

void tree_add(int now,int l,int r,int k,int b)

{

    if(tree[now].l==l&&tree[now].r==r)

    {

        if(tree[now].if_)

        {

            if(k==tree[now].k&&b==tree[now].b);

            else tree_down(now,k,b);

        }

        else tree[now].if_=true,tree[now].k=k,tree[now].b=b;

        return ;

    }

    if(l>tree[now].mid) tree_add(now<<|,l,r,k,b);

    else if(r<=tree[now].mid) tree_add(now<<,l,r,k,b);

    else

    {

        tree_add(now<<,l,tree[now].mid,k,b);

        tree_add(now<<|,tree[now].mid+,r,k,b);

    }

}

void tree_query(int now,int to)

{

    if(tree[now].if_) X=min(X,tree[now].k*to+tree[now].b);

    if(tree[now].l==tree[now].r) return ;

    if(to<=tree[now].mid) tree_query(now<<,to);

    else tree_query(now<<|,to);

}

int main()

{

    in(n);int pos,debug;

    for(int i=;i<=n;i++) in(ai[i]);

    for(int i=;i<=n;i++) in(pos),p[pos]=i;

    tree_build(,,n);

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

    {

        if(i<p[ai[i]])

        {

            tree_add(,,p[ai[i]]-i+,-,p[ai[i]]+-i);

            if(i!=) tree_add(,p[ai[i]]-i+,p[ai[i]],,i-p[ai[i]]-);

            if(p[ai[i]]!=n) tree_add(,p[ai[i]]+,n,-,n-i+p[ai[i]]+);

        }

        if(i>p[ai[i]])

        {

            tree_add(,,p[ai[i]],,i-p[ai[i]]-);

            tree_add(,p[ai[i]]+,p[ai[i]]+n-i+,-,n-i+p[ai[i]]+);

            if(i-p[ai[i]]>) tree_add(,p[ai[i]]+n-i+,n,,i-n-p[ai[i]]-);

        }

        if(i==p[ai[i]])

        {

            tree_add(,,i,,-);

            if(i!=n) tree_add(,i+,n,-,n+);

        }

    }

    for(int i=;i<=n;i++) X=INF,tree_query(,i),printf("%d\n",X);

    return ;

}

巴特西

AC日记——Little Elephant and Shifts codeforces 221e

最新文章

热门文章