解題區/解題區 - UVa

UVa 12776 - Query for Divisor-free Numbers

contents

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

Problem

給一個序列 A，請問在 A[l:r] 中 A[i] 不被 A[j] 整除的個數為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3

Sample Output

1
2
3
4
5
6
7
8
9
10
Case 1:
4
3
4
4
4
Case 2:
1
2
1

Solution

首先先貪心 A[i]，找到左側最鄰近的因數、右側最鄰近的因數的位置找出 L[i], R[i]。

以下使用 binary indexed tree 進行區域操作。

然後對於詢問 [l, r] 事先讀進來，加入掃描線算法，確保能夠詢問 [l, r] 時，找尋 BIT[r] 的值為何。

掃描時，當我們遇到某個因數所展開的區間 [L[i], R[i]] 的左端點

  • 對於 BIT[i, R[i]] 範圍元素都加上 1，而在遇到區間對應的 A[i] 位置進行移除區間 (不用等到右端點，必須在中間就移除掉，確保查詢的時 A[i] 還在裡面)，BIT[i, R[i]] 範圍元素都減去 1。
  • 對於遇到詢問 [l, r] 的左端點時，詢問 BIT[r] 的值為何。

因此資料結構要維護

  • 將一個區間內的元素都加上 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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define maxL (50000>>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[32767], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 50000;
    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;
        }
    }
}
vector< pair<int, int> > factor(int n) {
    int on = n;
    vector< pair<int, int> > R;
    
    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++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
void make(int idx, int n, int m, vector< pair<int, int> > &v, vector<int> &ret) {
    if(idx == v.size()) {
        ret.push_back(m);
        return;
    }
    int a = m, b = v[idx].first;
    for(int i = v[idx].second; i >= 0; i--)
        make(idx + 1, n, a, v, ret), a *= b;
}
int A[131072], L[131072], R[131072];
vector<int> Af[131072], RM[131072];
vector< pair<int, int> > Q[131072], QL[131072];
int OUT[131072];
int BIT[131072];
void modify(int x, int val, int L) {
    while (x <= L) {
        BIT[x] += val;
        x += (x)&(-x);
    }
}
int query(int x) {
    int ret = 0;
    while (x) {
        ret += BIT[x];
        x -= (x)&(-x);
    }
    return ret;
}
int main() {
//		freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
    sieve();
    int testcase, cases = 0;
    int n, m, x, y;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            vector< pair<int, int> > f = factor(A[i]);
            Af[i].clear();
            make(0, A[i], 1, f, Af[i]);
        }
        for (int i = 0; i < n + 20; i++)
            Q[i].clear(), QL[i].clear(), RM[i].clear();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            Q[x].push_back(make_pair(y, i));
        }
        map<int, int> mp;
        map<int, int>::iterator mpit;
        for (int i = 1; i <= n; i++) {
            x = 0;
            for (int j = 0; j < Af[i].size(); j++)
                x = max(x, mp[Af[i][j]]);
            mp[A[i]] = i;
            L[i] = x + 1;
        }
        mp.clear();
        for (int i = n; i >= 1; i--) {
            x = n + 1;
            for (int j = 0; j < Af[i].size(); j++) {
                mpit = mp.find(Af[i][j]);
                if (mpit != mp.end())
                    x = min(x, mpit->second);
            }
            mp[A[i]] = i;
            R[i] = x - 1;
        }
        for (int i = 1; i <= n; i++) {
            QL[L[i]].push_back(make_pair(R[i], i));
            RM[i].push_back(R[i]);
        }
        for (int i = 1; i <= n + 20; i++)
            BIT[i] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < QL[i].size(); j++) {
                modify(QL[i][j].second, 1, n + 20);
                modify(QL[i][j].first + 1, -1, n + 20);
//				printf("add [%d %d]\n", QL[i][j].second, QL[i][j].first);
            }
            if (i)
            for (int j = 0; j < RM[i-1].size(); j++) {
                modify(i-1, -1, n + 20);
                modify(RM[i-1][j] + 1, 1, n + 20);
//				printf("rm [%d %d]\n", i-1, RM[i][j]);
            }
            for (int j = 0; j < Q[i].size(); j++) {
                int v = query(Q[i][j].first);
                OUT[Q[i][j].second] = v;
//				printf("%d %d - %d\n", Q[i][j].first, Q[i][j].second, v);
            }
//			puts("--");
        }
        printf("Case %d:\n", ++cases);
        for (int i = 0; i < m; i++)
            printf("%d\n", OUT[i]);
    }
    return 0;
}
/*
2
10 5
4 6 2 7 5 11 14 21 13 2
2 6
4 8
2 8
3 7
4 9
5 3
4 6 8 1 5
1 5
2 3
3 3
*/