yukicoder No.318 学学学学学

問題
No.318 学学学学学 - yukicoder
数列が与えられる．からについて順番に，同じ数で挟まれた数をで置き換える．書き換えられた後の数列を出力する問題．

解法
双方向リストを使う．大きい数から順番に以下の操作を行う．

1. 一番左のが，一番右のがとすると，についてをに書き換える．このとき，前に書き換えられた数は書き換えない．
2. 双方向リストをの範囲を飛ばすように書き換える．

双方向リストは次の位置は配列nxtで前の位置は配列prvで表すようにした．双方向リストを使わない場合，同じ数を何回も確認することになるのでTLEになる．

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

int a[100100], nxt[100100], prv[100100];
bool used[100100];

int main(void) {
    int i, n;
    map<int,pair<int,int>> mp;
    scanf("%d",&n);
    REP (i,1,n) {
        scanf("%d",a+i);
        if (!mp.count(a[i]))
            mp[a[i]].first = i;
        else 
            mp[a[i]].second = i;
        nxt[i] = i+1;
        prv[i] = i-1;
    }
    nxt[0] = 1;
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        int left, right, p;
        left = it->second.first;
        right = it->second.second == 0 ? it->second.first : it->second.second;
        p = left;
        while (p <= right) {
            if (!used[p])
                a[p] = it->first;
            used[p] = true;
            p = nxt[p];
        }
        p = left;
        while (p <= right) {
            int tmp = nxt[p];
            nxt[p] = nxt[right];
            prv[p] = prv[left];
            p = tmp;
        }
        nxt[prv[left]] = nxt[right];
        prv[nxt[right]] = prv[left];
    }
    REP (i,1,n) printf("%d%c",a[i],i < n ? ' ' : '\n');
    return 0;
}

遅延セグメント木を使っても解ける．
ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP (i,0,(int)(n)-1)
#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP (i,(int)(n)-1,0)
#define INF (int)1e8
#define MOD (int)(1e9+7)

typedef long long ll;

struct ST {
    vector<ll> seg, lazy;
    int size;

    ST(int n) {
        size = 1;
        while (size < n) size *= 2;
        seg.resize(size * 2);
        lazy.resize(size * 2, -1);
    }

    void push(int k, int l, int r) {
        if (lazy[k] != -1) {
            seg[k] = lazy[k] * (r - l);
            if (r - l > 1) {
                lazy[k * 2 + 1] = lazy[k];
                lazy[k * 2 + 2] = lazy[k];
            }
            lazy[k] = -1;
        }
    }

    void update(int a, int b, ll v, int k, int l, int r) {
        push(k, l, r);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] = v;
            push(k, l, r);
        }
        else {
            update(a, b, v, k * 2 + 1, l, (l + r) / 2);
            update(a, b, v, k * 2 + 2, (l + r) / 2, r);
            seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
        }
    }

    void update(int a, int b, ll v) {
        update(a, b, v, 0, 0, size);
    }

    ll query(int a, int b, int k, int l, int r) {
        push(k, l, r);
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        ll x = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll y = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return x + y;
    }

    ll query(int a, int b) {
        return query(a, b, 0, 0, size);
    }
};

int main(void) {
    int i, n;
    cin >> n;
    vector<int> a(n);
    rep (i, n) scanf("%d",&a[i]);
    map<int, int> first, last;
    rrep (i, n) first[a[i]] = i;
    rep (i, n) last[a[i]] = i;
    ST st(n);
    rep (i, n) st.update(i, i + 1, a[i]);
    for (auto kv : first) if (last.count(kv.first)) {
        st.update(kv.second, last[kv.first] + 1, kv.first);
    }

    rep (i, n) printf("%d ", (int)st.query(i, i + 1));
    cout << endl;
    return 0;
}