백준18587 Nonsence Time

작성일 | In

문제 링크

  • http://icpc.me/18587

사용 알고리즘

  • 세그먼트 트리
  • DP

시간복잡도

  • $O(N \sqrt N \log N)$

풀이

입력이 랜덤으로 주어집니다. 이 조건을 잘 이용해봅시다.

수를 하나씩 추가하는 것이 아니라 반대로 하나씩 제거한다고 생각해봅시다.
처음에 LIS를 구해놓은 다음, LIS를 구성하는 원소가 제거되는 경우 다시 LIS를 구하는 방식을 생각해볼 수 있습니다. 이때 LIS는 (원본 순열의 LIS의 길이)번 구하게 됩니다.

무작위로 구성된 순열에서 LIS의 기댓값은 $O(\sqrt N)$입니다. LIS는 $O(N \log N)$에 구할 수 있으므로 전체 시간 복잡도는 $O(N \sqrt N \log N)$이 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

struct Seg{
    pi tree[1 << 17];
    static const int sz = 1 << 16;
    void init(){ for(int i=0; i<sz+sz; i++) tree[i] = pi(0, 0); }
    void update(int x, pi v){
        x |= sz; tree[x] = max(tree[x], v);
        while(x >>= 1) tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
    }
    pi query(int l, int r){
        l |= sz; r |= sz; pi ret(0, 0);
        while(l <= r){
            if(l & 1) ret = max(ret, tree[l++]);
            if(~r & 1) ret = max(ret, tree[r--]);
            l >>= 1; r >>= 1;
        }
        return ret;
    }
} seg;

int n, p[50505], k[50505];
bitset<50505> bs, use;

int dp[50505], prv[50505], lis;
void calc(){
    use.reset(); seg.init();
    int idx = 0;
    for(int i=1; i<=n; i++){
        if(!bs[i]) continue;
        auto t = seg.query(1, p[i]-1);
        dp[i] = t.x + 1; prv[i] = t.y;
        if(dp[idx] < dp[i]) idx = i;
        seg.update(p[i], pi(dp[i], i));
    }
    lis = dp[idx];
    for(int i=idx; i; i=prv[i]) use[i] = true;
}

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> p[i];
    for(int i=1; i<=n; i++) cin >> k[i];
    bs.set();
    vector<int> ans;
    calc();
    for(int i=n; i>=2; i--){
        ans.push_back(lis);
        bs[k[i]] = false;
        if(use[k[i]]) calc();
    }
    ans.push_back(1);
    reverse(all(ans));
    for(auto i : ans) cout << i << " ";
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int t; cin >> t; while(t--) solve();
}