解題區►解題區 - UVa

UVa 12345 - Dynamic len(set(a[L:R]))

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

In python, we can use len(start(a[L:R])) to calculate the number of distinct values of elements a[L], a[L+1], …, a[R-1].

Here are some interactive examples that may help you understand how it is done. Remember that the indices of python lists start from 0. 

1
2
3
4
5
6
7
8
9
10
11
12
>>> a=[1,2,1,3,2,1,4]
>>> print a[1:6]
[2, 1, 3, 2, 1]
>>> print set(a[1:6])
set([1, 2, 3])
>>> print len(set(a[1:6]))
3
>>> a[3]=2
>>> print len(set(a[1:6]))
2
>>> print len(set(a[3:5]))
1

Your task is to simulate this process.

Input

There will be only one test case. The first line contains two integers n and m (1 ≤ n,m ≤ 50,000). The next line contains the original list.

All the integers are between 1 and 1,000,000 (inclusive). The next m lines contain the statements that you need to execute.

A line formatted as “M x y” (1 ≤ y ≤ 1,000,000) means “a[x] = y”, and a line formatted as “Q x y” means “print len(set(a[x:y]))”.

It is guaranteed that the statements will not cause “index out of range” error.

Output

Print the simulated result, one line for each query.

Sample Input

1
2
3
4
5
6
7 4
1 2 1 3 2 1 4
Q 1 6
M 3 2
Q 1 6
Q 3 5

Output for Sample Input

1
2
3
3
2
1

Solution

題目描述：

  1. 支持查找區間內有多少不同數字。
  2. 支持單點值修改

題目解法：

維護每一個數字的前面相同數字的位置，如果前面沒有一樣的就是 -1

1
2
3
  i   0  1  2  3  4  5  6
A[]   1  2  1  3  2  1  4
P[]  -1 -1  0 -1  1  2 -1

對於詢問 [l, r]，返回 P[l, r] 內小於 l 的個數。

這裡使用塊狀表維護資訊，也可以使用 線段樹 + 平衡樹。

  • 塊狀表 作法

    • 對於詢問
      對於完整的塊進行二分搜尋。如果所在是不完整的塊，則窮舉搜尋。

    • 對於修改

      • 向後搜索舊值
        將指向自己的修改成原本指向的。
      • 向前搜索新值
        將指向連到前方的相同數字。
      • 向後搜索新值
        將後面最靠近的相同數字連向自己。

    • 維護資訊

      • 堆的 prev 排序後的資訊
        用在詢問 query 區間內小於 l 的二分搜
      • 堆的 value 排序後的資訊
        維護 prev 時，查找前一個和後一個的時候使用。
    • 堆更新時，最簡單是直接排序，複雜度 O(sqrt(n) * log(sqrt(n))) 看起來是不會很多，如果不使用這種方式，則必須對 prev 和 value 數組增加映射來找到相對應的原位置，然後用插入排序的方式，達到 O(sqrt(n))。但是在 UVa 運行前者在 1.200 s 左右，基本上可以不用再優化，紀錄的資訊增加一倍 又或者 代碼要長一點。

每一個操作約在 O(sqrt(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
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <stdio.h>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
int pSIZE, pCOUNT;
int Pval[256][256], Ppre[256][256], Plen[256];
int A[65536], P[65536];
void build(int n) {
	int pxIdx = -1, pyIdx = pSIZE;
	map<int, int> PREV;
	map<int, int>::iterator it;
	
	memset(Plen, 0, sizeof(Plen));
	
	for(int i = 0; i < n; i++) {
		if(pyIdx == pSIZE)
			pxIdx++, pyIdx = 0;
		Pval[pxIdx][pyIdx] = A[i];
		it = PREV.find(A[i]);
		if(it == PREV.end()) {
			Ppre[pxIdx][pyIdx] = -1;
			PREV[A[i]] = i;
		} else {
			Ppre[pxIdx][pyIdx] = it->second;
			it->second = i;
		}
		P[i] = Ppre[pxIdx][pyIdx];
		pyIdx++;
		Plen[pxIdx] = pyIdx;
	}
	
	pCOUNT = pxIdx + 1;
	
	for(int i = 0; i < pCOUNT; i++) {
		sort(Pval[i], Pval[i] + Plen[i]);
		sort(Ppre[i], Ppre[i] + Plen[i]);
	}
}
int query(int L, int R) {
	int B = L;
	int ret = 0;
	while(L%pSIZE && L <= R) {
		if(P[L] < B)	ret++;
		L++;
	}
	while((R+1)%pSIZE && L <= R) {
		if(P[R] < B)	ret++;
		R--;
	}
	if(L > R)	return ret;
	L /= pSIZE, R /= pSIZE;
	while(L <= R) {
		int cnt = upper_bound(Ppre[L], Ppre[L] + pSIZE, B - 1) - Ppre[L];
		ret += cnt;
		L++;
	}
	return ret;
}
void updatePrev(int x) {
	for(int i = x * pSIZE, j = 0; j < Plen[x]; i++, j++)
		Ppre[x][j] = P[i];
	sort(Ppre[x], Ppre[x] + Plen[x]);
}
void update(int x) {
    for(int i = x * pSIZE, j = 0; j < Plen[x]; i++, j++)
		Pval[x][j] = A[i], Ppre[x][j] = P[i];
	sort(Pval[x], Pval[x] + Plen[x]);
	sort(Ppre[x], Ppre[x] + Plen[x]);
}
void getNext(int x, int val, int &NEXT, int &nx) {
	int y = x/pSIZE * pSIZE + Plen[x / pSIZE] - 1;
	NEXT = 0x3f3f3f3f, nx = -1;
	while(x%pSIZE && x <= y) {
		if(A[x] == val) {
			NEXT = x, nx = x / pSIZE;
			return;
		}
		x++;
	}
	int L = x / pSIZE, R = pCOUNT - 1;
	if(L * pSIZE < x)	return;
	for(int i = L; i <= R; i++) {
		int pos = binary_search(Pval[i], Pval[i] + Plen[i], val);
		if(pos == true) {
			NEXT = i * pSIZE;
			while(A[NEXT] != val)	NEXT++;
			nx = i;
			return;
		}
	}
}
void getPrev(int y, int val, int &PREV, int &px) {
	int x = 0;
	PREV = -1, px = -1;
	while((y+1)%pSIZE && x <= y) {
		if(A[y] == val) {
			PREV = y, px = y / pSIZE;
			return;
		}
		y--;
	}
	int L = 0, R = y / pSIZE;
	if(R * pSIZE > y)	return;
	for(int i = R; i >= L; i--) {
        int pos = binary_search(Pval[i], Pval[i] + Plen[i], val);
		if(pos == true) {
			PREV = i * pSIZE + Plen[i] - 1;
			while(A[PREV] != val)	PREV--;
			px = i;
			return;
		}
	}
}
void modify(int X, int nval) {
	if(A[X] == nval)	return ;
	int oval = A[X];
	int NEXT, PREV, nx, px;
	PREV = P[X], px = -1;
	if(PREV >= 0)	px = PREV / pSIZE;
	
	getNext(X + 1, oval, NEXT, nx);
	if(nx != -1) {
		P[NEXT] = PREV;
		updatePrev(nx);
	}
    
	getNext(X + 1, nval, NEXT, nx);
	if(nx != -1) {
		P[NEXT] = X;
		updatePrev(nx);
	}
    
	getPrev(X - 1, nval, PREV, px);
	A[X] = nval, P[X] = PREV;
	update(X / pSIZE);
}
int main() {
    //	freopen("in.txt", "r+t", stdin);
    //	freopen("out2.txt", "w+t", stdout);
	int n, m, L, R;
	char cmd[4];
	while(scanf("%d %d", &n, &m) == 2) {
		for(pSIZE = 1; pSIZE * pSIZE < n; pSIZE++);
		
		for(int i = 0; i < n; i++)
			scanf("%d", &A[i]);
		build(n);
		
		while(m--) {
			scanf("%s %d %d", cmd, &L, &R);
			if(cmd[0] == 'Q') {
				R--;
				int r = query(L, R);
				printf("%d\n", r);
			} else {
				modify(L, R);
			}
		}
	}
	return 0;
}
/*
 30 50
 4 19 18 17 16 7 16 9 18 14 4 11 4 2 8 8 1 3 1 5 5 8 3 8 11 17 10 0 2 16
 M 20 12 
 Q 2 29
 M 8 9
 Q 7 7
 M 25 12
 M 19 13
 Q 12 22
 Q 8 11
 M 5 5
 M 15 8
 Q 9 26
 */