2014-05-01

UVa 1417 - Traffic Jam

Problem

The kingdom of Tripbansai has an unusual traffic system. The city locations in the kingdom can be described as a grid and all the roads connect neighboring cities. This rectangular grid has 2 rows and C columns where every point represents a city. So there are 2 C cities and 3 C - 2 roads in this system.

Sometimes two adjacent cities become disconnected because of traffic jam, and sometimes the traffic problem has been solved so that a road can be usedd again. We can assume that every road is closed at first.

Ministry of Communications will give some instructions to you. Your task is to implement a program as a traffic response information system.

Each instruction appears as a single line in one ofthe formats below:

Close r1 c1 r2 c2 Close the road connecting the adjacent cities located on (r1, c1) and (r2, c2) .
Open r1 c1 r2 c2 Open the road connecting the adjacent cities located on (r1, c1) and (r2, c2) .
Ask r1 c1 r2 c2 Reply with Y if there exists a way from the city on (r1, c1) to the city on (r2, c2) ;
reply with N if there doesn’t.
Exit No more requests are forthcoming. The problem should exit.

Input

The first line ofthe input contains a single integer T (1$\le$T$\le$11) , representing the number of test cases that follow.

The first line of each test case consists of a single integer C (1$\le$C$\le$100000) , which is the number of columns.

There are some lines following, each for an instruction. Each test case ends with an instruction ``Exit”. There are no more than 100000 instructions in each test case. All the roads are closed initially, and each case is an independent problem.

Output

For each instruction Ask r1 c1 r2 c2, display a line containing Y or N.

Sample Input

3
2
Open 1 1 1 2
Open 1 2 2 2
Ask 1 1 2 2
Ask 2 1 2 2
Exit
3
Open 1 1 1 2
Ask 1 1 1 2
Close 1 1 1 2
Ask 1 1 1 2
Exit
2
Open 1 1 1 2
Open 1 2 2 2
Open 2 1 2 2
Ask 1 1 2 1
Exit

Sample Output

Y
N
Y
N
Y

Solution

題目描述：

對於一個 2 x C 的方格點來說，將會有 3 * C - 2 條邊。

題目解法：

維護一個區間角落四個點之間的連接資訊，也就是總共六種。

c[0] 左上右上
c[1] 左上右下
c[2] 左下右上
c[3] 左下右下
c[4] 左上左下
c[5] 右上右下

上方 r = 1 下方 r = 2 左方 c = left 右方 c = right

對於區間 [l, r] 我們只維護這個區間的資訊，不考慮繞此外的結果。
而對於區間的編號，由左而右，構成 0, 1, 2, 3, …, C，每一個可以看作是一個方格。

#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
struct Node {
    int c[6];
}; // - \ / _ | |
Node ST[262144 + 10];
void build(int k, int l, int r) {
    if(l > r)	return;
    if(l == r) {
        memset(&ST[k], 0, sizeof(ST[k]));
        return;
    }
    int mid = (l + r)/2;
    build(k<<1, l, mid);
    build(k<<1|1, mid+1, r);
}
Node combine(Node s1, Node s2) {
    Node s;
    s.c[0] = (s1.c[0] && s2.c[0]) || (s1.c[1] && s2.c[2]);
    s.c[1] = (s1.c[0] && s2.c[1]) || (s1.c[1] && s2.c[3]);
    s.c[2] = (s1.c[2] && s2.c[0]) || (s1.c[3] && s2.c[2]);
    s.c[3] = (s1.c[2] && s2.c[1]) || (s1.c[3] && s2.c[3]);
    s.c[4] = (s1.c[4]) || (s1.c[0] && s2.c[4] && s1.c[3]);
    s.c[5] = (s2.c[5]) || (s2.c[0] && s1.c[5] && s2.c[3]);
    return s;
}
void modify(int k, int l, int r, int qidx, int qfield, int qval) {
    if(l > r)	return;
    if(l == r) {
        ST[k].c[qfield] = qval;
        ST[k].c[1] = (ST[k].c[0] && ST[k].c[5]) || (ST[k].c[3] && ST[k].c[4]);
        ST[k].c[2] = (ST[k].c[0] && ST[k].c[4]) || (ST[k].c[3] && ST[k].c[5]);
        return;
    }
    int mid = (l + r)/2;
    if(qidx > mid)
        modify(k<<1|1, mid+1, r, qidx, qfield, qval);
    else
        modify(k<<1, l, mid, qidx, qfield, qval);
    ST[k] = combine(ST[k<<1], ST[k<<1|1]);
}
Node query(int k, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr)
        return ST[k];
    int mid = (l + r)/2;
    if(ql > mid)
        return query(k<<1|1, mid+1, r, ql, qr);
    else if(qr <= mid)
        return query(k<<1, l, mid, ql, qr);
    else
        return combine(query(k<<1, l, mid, ql, qr), 
                        query(k<<1|1, mid+1, r, ql, qr));
}
int main() {
    int testcase, C;
    int r1, r2, c1, c2;
    int lines = 0;
    char cmd[10];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &C);
        memset(ST, 0, sizeof(ST));
        build(1, 0, C);
        while(scanf("%s", cmd) == 1 && cmd[0] != 'E') {
            scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
            if(cmd[0] == 'O' || cmd[0] == 'C') { // open
                int qval = cmd[0] == 'O' ? 1 : 0;
                if(c1 != c2) {
                    modify(1, 0, C, min(c1, c2), r1 == 1 ? 0 : 3, qval);
                } else {
                    modify(1, 0, C, min(c1, c2) - 1, 5, qval);
                    modify(1, 0, C, min(c1, c2), 4, qval);
                }
            } else {
                if(c1 > c2) {
                    swap(c1, c2);
                    swap(r1, r2);
                }
                if(r1 == r2 && c1 == c2) {
                    puts("Y");
                } else if(r1 != r2 && c1 == c2) {
                    Node l = query(1, 0, C, 0, c1 - 1);
                    Node r = query(1, 0, C, c1, C);
                    if(l.c[5] || r.c[4])
                        puts("Y");
                    else
                        puts("N");
                } else {
                    Node l = query(1, 0, C, 0, c1 - 1);
                    Node r = query(1, 0, C, c2, C);
                    Node m = query(1, 0, C, c1, c2 - 1);
                    int kc[2][2] = { {0, 1}, {2, 3} };
                    if(m.c[kc[r1 - 1][r2 - 1]] || 
                        (l.c[5] && m.c[kc[(3 - r1) - 1][r2 - 1]]) ||
                        (r.c[4] && m.c[kc[r1 - 1][(3 - r2) - 1]]) ||
                        (l.c[5] && r.c[4] && m.c[kc[(3 - r1) - 1][(3 - r2) - 1]]))
                        puts("Y");
                    else
                        puts("N");
                }
            }
        }
    }
    return 0;
}

UVa 1608 - Non-boring sequences

Problem

We were afraid of making this problem statement too boring, so we decided to keep it short. A sequence is called non-boring if its every connected subsequence contains a unique element, i.e. an element such that no other element of that subsequence has the same value.
Given a sequence of integers, decide whether it is non-boring.

Input

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:
Each test case starts with an integer n (1 <= n <= 200000) denoting the length of the sequence. In the next line the n elements of the sequence follow, separated with single spaces. The elements are non-negative integers less than 10^9.

Output

Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line containing the word non-boring or boring.

Sample Input

Sample Output

non-boring
boring
non-boring
boring

Solution

題目描述：

對於所有連續區間，都符合至少有一個獨特的數字。即每個區間中都會有一個數字不重複。

題目解法：

對於一個區間 [l, r] 來說，符合條件時，會存在一個獨特的數字位於 m，則對於 i in [l, m-1] and j in [m+1, r]，所有 [i, j] 產生的區間必然會符合，則遞歸下去查找 [l, m-1] 和 [m+1, r] 有沒有符合。

這題有趣的地方在於－如何快速得到這個獨特數字，不過也不難想地，建出數字的前一個相同和下一個相同。判斷該數字在區間是獨特時，則前一個和下一個皆不會在區間中。

這樣仍不會通過測資，如果是想要接近中間的方式去切割，則會接受 TLE 的殘酷事實，當初在想是不是遞迴太深還怎麼的，這裡留下困惑，根據快速排序的經驗，如果切割點在中間是比較好的，複雜度為 O(n log n)。

lang: cpp

#include <stdio.h> 
#include <algorithm>
#include <map>
using namespace std;
int A[262144];
int NEXT[262144], PREV[262144];
map<int, int> R;
int dfs(int l, int r) {
    if(l >= r)	return 1;
    for(int i = 0; i <= (r-l+1)/2; i++) {
        if(NEXT[l+i] > r && PREV[l+i] < l)
            return dfs(l, l+i-1) && dfs(l+i+1, r);
        if(NEXT[r-i] > r && PREV[r-i] < l)
            return dfs(l, r-i-1) && dfs(r-i+1, r);
    }
    return 0;
}
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            NEXT[i] = n+1;
            PREV[i] = 0;
        }
        R.clear();
        for(int i = 1; i <= n; i++) {
            PREV[i] = R[A[i]], NEXT[PREV[i]] = i;
            R[A[i]] = i;
        }
        puts(dfs(1, n) ? "non-boring" : "boring");
    }
    return 0;
}
/*
20
6
1 2 3 1 2 3
5
1 2 3 4 5
5
1 1 1 1 1
5
1 2 3 2 1
5
1 1 2 1 1
*/

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

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