codeforces 220c Little Elephant and Shifts

経典のテーマに出会うことはめったにありません.これは経典ではありませんが、とてもすばらしいです.タイトル
2つの1-nの配列を与えて、2つの配列の距離を定義します:すべての同じ数字の間の距離の最小値、More formally,it's such minimum|iA cyclic shift number i(1bnb1b2... bi - 1. Overall a permutation has n cyclic shifts. 出力者n個のcyclic shiftsの距離.
eg:

4
2 1 3 4
3 4 2 1

出力2 1 0 1
解題構想:nは大きい(10^5)ので、O(nlogn)のアルゴリズムだと思います.線分樹を思い浮かべますが、どのようにメンテナンスするか思い出せません.その後、同級生と議論して、1つの方法を考えました.1つ目のシーケンスはAで、2つ目はBで回転する必要があります.メンテナンスBの値がAの中で対応しているとしても、左か右か、左なら、回転後の距離+1、右側の優先キューを維持すると、-1の要素が0になると、左のシーケンスに挿入され、右のシーケンスが削除されます.最後の要素に移動する必要がある場合は、操作を挿入し、削除します.話が少し乱れているかもしれません.
しかし、いくつかの難点があります.1)削除操作はどう処理しますか.優先キューは、スタックで実装してもstlでも削除されていない操作で、私の方法は、各要素にタイムスタンプがあり、デキューされた要素のタイムスタンプが時代遅れになったら、直接チェックアウトして、気にしないことです.これで削除の役割を果たします
2)優先キュー全体の+1と-1操作については,遅延加算を用いることが考えられるが,全体+1が+1がない,すなわち,アウトキューの場合+1である以上,挿入には注意が必要であり,挿入前にこの遅延を加減してこそ,アウトキューの値の正しさを保証できることが理解される.
code:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stdlib.h>
using namespace std;
#define N 100010
int dat1[N],dat2[N];

int pos[N];
struct note
{
    int val,time,index;
    note(){}
    note(int _v,int _t,int _i):val(_v),time(_t),index(_i){}
};
struct cmp
{
    bool operator() ( note a, note b )
    {
        return a.val > b.val;
    }
};
int _time[N];
int main()
{
    int n;
    while(cin >> n)
    {
        for(int i = 0;i < n;i++) scanf("%d",&dat1[i]);
        for(int i = 0;i < n;i++) scanf("%d",&dat2[i]);

        for(int i = 0;i < n;i++) pos[dat1[i]] = i;

        priority_queue < note ,vector<note> ,cmp > l_queue,r_queue;

        memset(_time,0,sizeof(_time));
        for(int i = 0;i < n;i++)
        {
            //      
            if(pos[ dat2[i] ] >= i) l_queue.push( note(pos[dat2[i]] - i,0, pos[ dat2[i] ] ) );
            else r_queue.push( note(i-pos[dat2[i]],0, pos[ dat2[i] ] ) );
        }
        int t = 0;
        int now_time = 1;
        for(int i = 0;i < n;i++)
        {
            while(l_queue.empty() == 0 && l_queue.top().time != _time[l_queue.top().index]) l_queue.pop();

            while(r_queue.empty() == 0 && r_queue.top().time != _time[r_queue.top().index]) r_queue.pop();

            if(l_queue.size() == 0) cout << r_queue.top().val - t << "
";
            else if(r_queue.size() == 0) cout << l_queue.top().val + t << "
";
            else cout << min(l_queue.top().val+t,r_queue.top().val-t) << "
";

            if(i == n-1) continue;
            t++;
            int ttt = dat2[i];
            r_queue.push(note(n-1 - pos[ttt] + t,now_time,pos[ttt] ));
            _time[pos[ttt]] = now_time++;

            while(r_queue.empty() == 0 && r_queue.top().val - t == 0)
            {
                note tt = r_queue.top();r_queue.pop();
                tt.val = 0-t;
                l_queue.push(tt);
            }
        }
    }
    return 0;
}

ps:私はこの問題が大好きです.