解題區/解題區 - UVa

UVa 11669 - Non Decreasing Prime Sequence

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

每一個數字可以做質因數分解，找尋區間 [l, r] 所有數字質因數分解後，字典順序第 k 小的結果。

字典順序先按照集合個數由小到大，相同時才按照一般字典順序排序。

Sample Input

1
2
3
4
3
2 10 1
2 10 5
2 10 9

Sample Output

1
2
3
Case 1: 2
Case 2: 2 2
Case 3: 2 2 2

Solution

首先必須建質數表，之後利用 dfs 搜索出字典順序的結果，特別小心 overflow 的計算，必須使用 long long 防止在 1000000 以內的數字相乘溢位。

之後可以得到每一個數字質因數分解之後的排序結果 rank[i] = number, arank[number] = i。

然而每一組詢問，相當於在 arank 中查找 [l, r] 的第 k 小數字為何，輸出其 number 的結果。

套用區間第 k 大的解法，在離線情況下 (不更動元素)，按照順序插入 rank[number]，在 O(n log n) 時間內建表，消耗 O(n log n) 空間，在 O(log n) 回答。

在回答方面比歸併樹或者是塊狀鏈表快很多，可惜的是空間消耗相當驚人。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 K 大的時候，相當於對某個時間點之間作減法運算。

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[1048576 * 23];
int nodesize = 0;
int root[1048576];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
#define maxL (1000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[100000], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for (k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int fpath[30];
int rank[1048576], arank[1048576], ridx = 0;
void dfsBuild(int idx, long long v, int mxdep, int dep) {
    if (dep == mxdep) {
        rank[v] = ++ridx;
        arank[ridx] = v;
        return ;
    } 
    for (int i = idx; i < Pt && v * P[i] <= 1000000; i++)
        fpath[dep] = P[i], dfsBuild(i, v * P[i], mxdep, dep+1);
}
void printfactor(int n) {
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++)
                printf(" %d", P[i]);
        }		
    }
    if (n != 1)	printf(" %d", n);
    puts("");
}
int main() {
    sieve();
    for (int i = 1; i < 20; i++)
        dfsBuild(0, 1, i, 0);    
            
    nodesize = 1;
    root[0] = build(1, 1000000);        
    for (int i = 1; i <= 1000000; i++) {
        if (rank[i])
        	root[i] = change(root[i-1], rank[i], 1);
        else
        	root[i] = root[i-1];
    }
    
    int testcase, cases = 0, x, y, k;
    scanf("%d", &testcase);
    while (testcase--) {
    	scanf("%d %d %d", &x, &y, &k);
    	int ret = arank[query(root[y], root[x-1], k)];
    	printf("Case %d:", ++cases);
        printfactor(ret);
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */