2014-05-01

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

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
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.

>>> 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

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

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)) 時間內完整，塊狀表不用做合併操作。

#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
 */

Morris' Blog