2015-06-29

b413. 虛擬女友

Problem

曾經有一部採訪影片《BBC 紀錄片：別和日本人談性 No Sex. We’re Japanese.》在網路上流傳，其中有一段談到虛擬遊戲中的生活，不少男性以遊戲中的女角發生關係，其中以一款遊戲「Love Plus」為大宗，即使是擁有現實和虛擬的生活，若要選擇其中一方站，不少男性仍然「我選擇死亡」回答。

現在先不解決男女雙方的問題、在彼此關係上要如何運作，如何回到早些年沒有遊戲機、沒有網路、更沒有虛擬女友的交際生活，只有同性朋友要怎麼交流呢？於是有一場專門為這些男性舉行的一場交友會，規則如下所述：

一開始全場男性都彼此不認識
每一個男性分別喜歡各自的虛擬女友 (可以是同一個)
每一個時刻，其中兩個男性會因談論遊戲而成為朋友
自己朋友的朋友也會成為朋友
如果朋友的虛擬女友的類型不同，他們有可能會因偏好女友類型不同而爭吵，稱為不穩定對。

請問每一個時刻下，有多少穩定對朋友。

Sample Input

Sample Output

Solution

IPSC 2015 F 那一題發生於男女雙方都會進行聯集，而這一題只有男方會進行聯集。

合併兩團男時，只有下標 (女友類型) 相同會成為穩定對，可以利用合併排序來完成，能發生合併表示男的彼此之間不認識，只要考慮有多少女方相同即可。每一次將小堆合併到大堆中，由於要計數合併複雜度需要 $O(min(|A|, |B|) \times \log N)$，若搭配 hash 可以降到 $O(min(|A|, |B|)$。一般并查集 joint 複雜度為 $O(1)$，整體操作只需要 $O(N)$，但為了要計數，整體的複雜度為 $O(N \log N)$。

可以選擇合併排序來完成，每一次把兩堆的女方列出來，把兩堆相同類型的次數相乘，列出來可以循序做，或者是串列完成，每一次保證堆裡面的女方順序是由小排到大，合併複雜度就為 $O(|A| + |B|)$，均攤下複雜度為 $O(N \log N)$，當測資不夠隨機複雜度會掉到 $O(N^2)$，情況是每一次只把大小為 1 的堆合併到大小 i-1 的堆。

在測資隨機生成下，第二種作法會來得比第一種快。第一種做法要搭配 ordered_map 或者是 unordered_map，寫起來會比較不方便。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65536;
vector<int> son[MAXN];
int parent[MAXN], A[MAXN];
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        long long tot_pair = 0;
        int x, y;
        map< pair<int, int>, int > R;
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            son[i].resize(1, i);
            R[pair<int, int>(i, A[i])] = 1;
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            x = parent[x], y = parent[y];
            if (x != y) { // merge small to large
                if (son[x].size() > son[y].size())
                    swap(x, y);
                for (auto &e: son[x]) {
                    pair<int, int> t(parent[e], A[e]);
                    R[t]--;
                    if (R[t] == 0)  R.erase(t);
                    parent[e] = y;
                    son[y].push_back(e);
                    tot_pair += R[pair<int, int>(parent[e], A[e])];
                }
                for (auto &e: son[x])
                    R[pair<int, int>(parent[e], A[e])]++;
                son[x].clear();
            }
            printf("%lld\n", tot_pair);
        }
    }
    return 0;
}

Read More +

2015-06-27

解題區/解題區 - Zerojudge

b416. 誤會妹子序列

Problem

背景

在 2015 年 6 月的 Facebook 上，不少以「靠北」為前綴命名的粉絲頁面，就如靠北工程師為例，不少業界工程師匿名在上面抱怨工作過時、主管、生活 … 等。突然有一篇 #靠北工程師7257 抱怨著編程競賽的零零種種，從回應中能明白存在業界工程師不清楚編程競賽，以 UI 介面、cmd 指令 … 等方式理解比賽的目標、運行。

網路處處有答案，演算法和資料結構到底重不重要？抄下來能用就行，大部分的要求是不講求效率的，但對於曾經在編程競賽待過一陣子的小夥伴而言，看到他們的理解方式開始感到憤憤不平，進行了一陣子的爭吵。

過一陣子，大批的學生開始進入靠北工程師裡發文，開始爭論學校、系所哪個是比較有未來的，突然間有一位資管系的同學發問這一道算法題 ‪#‎靠北工程師7780‬ ，結果一不小心就看錯題目，把種類數誤看成個數，於是討論了不少其他的算法來完成，現在就把這個問題交給你。

用各種算法解決這個誤解的題目。

問題描述

Autumn 和 Bakser 又在研究 Gty 的妹子序列了！

但他們遇到了一個難題，對於一段妹子們，他們想讓你幫忙求出這之內美麗度 $s_i \in [a, b]$ 的妹子個數。為了方便，我們規定妹子們的美麗度全都在 $[1,n]$ 中。

給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$)，對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r, a, b$，每次輸出 $[s_l, \text{... },s_r]$ 中，權值 $s_i \in [a, b]$ 的個數。

Sample Input

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

Sample Output

Solution

相較於 b414. BZOJ 3809 Gty 的二逼妹子序列解法會相對多樣，單純計數就會變得比較簡單。

在這一題中，這裡提供三種解法：

莫隊算法
只能離線處理，無法強制在線詢問，算法複雜度由分塊降到 $O(N^{1.5})$。可參考 b414 的解法。
掃描線 + BIT
只能離線處理，把題目轉換成二維情況 $(i, A[i])$，詢問相當於找到矩形內部 $[l, r] \times [a, b]$ 有多少點座標，所以可以當作二維前綴來完成計數 $f(l, r, a, b) = f(r, b) - f(l-1, b) - f(r, a-1) - f(l-1, a-1)$。$f(x, y)$ 表示從原點 $(0, 0)$ 到 $(x, y)$ 的點數量，這樣的方式記憶體過多，利用掃描線算法降下來，對 x 由小掃描到大，依序將點插入詢問 $f(x, y)$ 會在掃瞄到 x 時，詢問 $[0, y]$ 之間的累計個數得到，最後將每一個詢問離線成四個詢問，掃描一次即可。
可持久化線段樹
必須預處理，支持在線詢問，不帶操作修改。將序列權值排序 $(A[i], i)$，依序索引值插入線段樹，紀錄每一個插入完的線段樹狀態，接著當詢問 $l, r, a, b$，相當於在版本 ver_b - ver_a 查詢線段樹區間 $[l, r]$ 的總和。由於是計數符合區間減法才能這樣做，否則持久化線段樹還要套別的小技巧來完成。

補充一點，雖然 KD-tree 效能是 $O(\sqrt{N} + K)$，它也支持 range searching，但必須搭配 report K 操作，那個 $O(\sqrt{N})$ 的花費是伴隨著 report 存在，因此單一筆計數詢問是無法達到 $O(\sqrt{N})$，天真的我寫下去直接 TLE。

莫隊算法

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
const int MAXV = 100005;
const int MAXQ = 1000005;
const int MAXSQRTV = 512;
class Offline {
public:
    struct Event {
        static int PILE, belong[MAXV];
        int l, r, x, y, qid;
        Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0):
            l(a), r(b), x(c), y(d), qid(e) {}
        bool operator<(const Event &x) const {
            if (belong[l] != belong[x.l])
                return l < x.l;
            return r < x.r; 
        }
    };
    int A[MAXN], N, qsize;
    Event event[MAXQ];
    int ret[MAXQ];
    void init(int N) {
        this->N = N, qsize = 0;
        memset(pile, 0, sizeof(pile));
        memset(val_count, 0, sizeof(val_count));
        val_PILE = Event::PILE = sqrt(N);
        for (int i = N; i >= 1; i--)
            val_belong[i] = Event::belong[i] = i / Event::PILE;
    }
    void q_add(int l, int r, int a, int b) {
        event[qsize] = Event(l, r, a, b, qsize);
        qsize++;
    }
    void run() {
        sort(event, event+qsize);
        
        int l = 1, r = 0;
        for (int i = 0; i < qsize; i++) {
            while (r < event[i].r)	r++, update(A[r], 1);
            while (r > event[i].r)	update(A[r], -1), r--;
            while (l > event[i].l)	l--, update(A[l], 1);
            while (l < event[i].l)	update(A[l], -1), l++;
            ret[event[i].qid] = query(event[i].x, event[i].y);
        }
    }
private:
    // unrolled
    int pile[MAXSQRTV], val_count[MAXV], val_belong[MAXV], val_PILE;
    inline void update(int x, int val) {
        val_count[x] += val;
        pile[val_belong[x]] += val;
    }
    int query(int a, int b) {
        int ret = 0;
        if (val_belong[a] == val_belong[b]) {
            for (int i = a; i <= b; i++)
                ret += val_count[i];
            return ret;
        }
        for (int i = val_belong[a]+1; i < val_belong[b]; i++)
            ret += pile[i];
        for (int i = (val_belong[a]+1)*val_PILE-1; i >= a; i--)
            ret += val_count[i];
        for (int i = (val_belong[b])*val_PILE; i <= b; i++)
            ret += val_count[i];
        return ret;
    }
} off;
int Offline::Event::PILE = 16, Offline::Event::belong[MAXV];
namespace mLocalStream {
    inline int readchar() {
        const int N = 1048576;
        static char buf[N];
        static char *p = buf, *end = buf;
        if(p == end) {
            if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
            p = buf;
        }
        return *p++;
    }
    inline int ReadInt(int *x) {
        static char c, neg;
        while((c = readchar()) < '-')    {if(c == EOF) return 0;}
        neg = (c == '-') ? -1 : 1;
        *x = (neg == 1) ? c-'0' : 0;
        while((c = readchar()) >= '0')
            *x = (*x << 3) + (*x << 1) + c-'0';
        *x *= neg;
        return 1;
    }
    class Print {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        Print() {
            p = buf, end = buf + N - 1;
        }
        void printInt(int x) {
            static char stk[16];
            int idx = 0;
            stk[idx++] = '\n';
            if (!x)	
                stk[idx++] = '0';
            while (x)
                stk[idx++] = x%10 + '0', x /= 10;
            while (idx) {
                if (p == end) {
                    *p = '\0';
                    printf("%s", buf), p = buf;
                }
                *p = stk[--idx], p++;
            }
        }
        ~Print() {
            *p = '\0';
            printf("%s", buf);
        }		
    } bprint;
}
int main() {
    int n, m, l, r, a, b;
    while (mLocalStream::ReadInt(&n)) {
        mLocalStream::ReadInt(&m);
        off.init(n);
        for (int i = 1; i <= n; i++)
            mLocalStream::ReadInt(&off.A[i]);
        for (int i = 0; i < m; i++) {
            mLocalStream::ReadInt(&l);
            mLocalStream::ReadInt(&r);
            mLocalStream::ReadInt(&a);
            mLocalStream::ReadInt(&b);
            off.q_add(l, r, a, b);
        }
        
        off.run();
        for (int i = 0; i < m; i++)
            mLocalStream::bprint.printInt(off.ret[i]);
//			printf("%d\n", off.ret[i]);
    }
    return 0;
}

掃描線

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
const int MAXQ = 1000005;
struct Event {
    int y, qid, qtype;
    Event(int a = 0, int b = 0, int c = 0):
    y(a), qid(b), qtype(c) {}
};
class BIT {
public:
    int v[MAXN], N;
    void init(int N) {
        this->N = N;
        for (int i = 0; i <= N; i++)
            v[i] = 0;
    }
    void add(int x, int val) {
        while (x <= N) {
            v[x] += val;
            x += x&(-x);
        }
    }
    int query(int x) {
        int sum = 0;
        while (x) {
            sum += v[x];
            x -= x&(-x);
        }
        return sum;
    }
} bit;
namespace mLocalStream {
    inline int readchar() {
        const int N = 1048576;
        static char buf[N];
        static char *p = buf, *end = buf;
        if(p == end) {
            if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
            p = buf;
        }
        return *p++;
    }
    inline int ReadInt(int *x) {
        static char c, neg;
        while((c = readchar()) < '-')    {if(c == EOF) return 0;}
        neg = (c == '-') ? -1 : 1;
        *x = (neg == 1) ? c-'0' : 0;
        while((c = readchar()) >= '0')
            *x = (*x << 3) + (*x << 1) + c-'0';
        *x *= neg;
        return 1;
    }
    class Print {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        Print() {
            p = buf, end = buf + N - 1;
        }
        void printInt(int x) {
            static char stk[16];
            int idx = 0;
            stk[idx++] = '\n';
            if (!x)
                stk[idx++] = '0';
            while (x)
                stk[idx++] = x%10 + '0', x /= 10;
            while (idx) {
                if (p == end) {
                    *p = '\0';
                    printf("%s", buf), p = buf;
                }
                *p = stk[--idx], p++;
            }
        }
        ~Print() {
            *p = '\0';
            printf("%s", buf);
        }		
    } bprint;
}
int n, m, A[MAXN], ret[MAXQ];
vector<Event> event[MAXN]; // event[pos]
int main() {
    while (mLocalStream::ReadInt(&n)) {
        mLocalStream::ReadInt(&m);
        for (int i = 1; i <= n; i++)
            mLocalStream::ReadInt(A+i), event[i].clear();
        for (int i = 0; i < m; i++) {
            int l, r, a, b;
            mLocalStream::ReadInt(&l);
            mLocalStream::ReadInt(&r);
            mLocalStream::ReadInt(&a);
            mLocalStream::ReadInt(&b);
            // area [l, a] - [r, b] = [r, b] - [l-1, b] - [r, a-1] + [l-1, a-1]
            event[r].push_back(Event(b, i, 1));
            event[l-1].push_back(Event(b, i, -1));
            event[r].push_back(Event(a-1, i, -1));
            event[l-1].push_back(Event(a-1, i, 1));
            ret[i] = 0;
        }
        
        bit.init(n);
        for (int i = 1; i <= n; i++) {
            bit.add(A[i], 1);
            for (auto &e: event[i]) {
                int val = bit.query(e.y);
                ret[e.qid] += e.qtype * val;
            }
        }
        
        for (int i = 0; i < m; i++)
            printf("%d\n", ret[i]);
    }
    return 0;
}

可持久化

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
const int MAXNODE = 3000000;
const int MAXN = 100005;
const int MAXQ = 100005;
class SegementTree {
public:
    struct Node {
        Node *lson, *rson;
        int val;
    } nodes[MAXNODE];
    int nodesize, L, R;
    Node* init(int l, int r) {
        nodesize = 0;
        L = l, R = r;
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        if (nodesize >= MAXNODE)
            exit(0);
        return &nodes[nodesize++];
    }
    Node* cloneNode(Node *p) {
        if (nodesize >= MAXNODE)
            exit(0);
        Node* u = &nodes[nodesize++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        u->lson = u->rson = NULL;
        if (l == r) {
            u->val = 0;
        } else {
            int m = (l + r)/2;
            u->lson = build(l, m);
            u->rson = build(m+1, r);
        }
        return u;
    }
    Node* add(Node *p, int x, int val) {
        return add(p, x, val, L, R);
    }
    int query(Node *tp, Node *tq, int x, int y) {
        return query(tp, tq, L, R, x, y);
    }
private:
    Node* add(Node *p, int x, int val, int l, int r) {
        Node *u = cloneNode(p);
        u->val += val;
        if (l == r) {
            return u;
        } else {
            int mid = (l + r)/2;
            if (x <= mid)
                u->lson = add(p->lson, x, val, l, mid);
            else
                u->rson = add(p->rson, x, val, mid+1, r);
        }
        return u;
    }
    int query(Node *tp, Node *tq, int l, int r, int x, int y) {
        if (x <= l && r <= y)
            return tq->val - tp->val;
        int mid = (l+r)/2;
        if (y <= mid)
            return query(tp->lson, tq->lson, l, mid, x, y);
        else if (x > mid)
            return query(tp->rson, tq->rson, mid+1, r, x, y);
        else
            return query(tp->lson, tq->lson, l, mid, x, mid) +
                query(tp->rson, tq->rson, mid+1, r, mid+1, y);
    }
} segTree;
namespace mLocalStream {
    inline int readchar() {
        const int N = 1048576;
        static char buf[N];
        static char *p = buf, *end = buf;
        if(p == end) {
            if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
            p = buf;
        }
        return *p++;
    }
    inline int ReadInt(int *x) {
        static char c, neg;
        while((c = readchar()) < '-')    {if(c == EOF) return 0;}
        neg = (c == '-') ? -1 : 1;
        *x = (neg == 1) ? c-'0' : 0;
        while((c = readchar()) >= '0')
            *x = (*x << 3) + (*x << 1) + c-'0';
        *x *= neg;
        return 1;
    }
    class Print {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        Print() {
            p = buf, end = buf + N - 1;
        }
        void printInt(int x) {
            static char stk[16];
            int idx = 0;
            stk[idx++] = '\n';
            if (!x)
                stk[idx++] = '0';
            while (x)
                stk[idx++] = x%10 + '0', x /= 10;
            while (idx) {
                if (p == end) {
                    *p = '\0';
                    printf("%s", buf), p = buf;
                }
                *p = stk[--idx], p++;
            }
        }
        ~Print() {
            *p = '\0';
            printf("%s", buf);
        }		
    } bprint;
}
SegementTree::Node *ver[MAXQ];
pair<int, int> A[MAXN];
int fver[MAXN];
int main() {
    int n, m, x;
    while (mLocalStream::ReadInt(&n)) {
        mLocalStream::ReadInt(&m);
        for (int i = 1; i <= n; i++)
            mLocalStream::ReadInt(&x), A[i] = make_pair(x, i);
        sort(A+1, A+n+1);
        
        ver[0] = segTree.init(1, n);
        for (int i = 1; i <= n; i++) {
            ver[i] = segTree.add(ver[i-1], A[i].second, 1);
            fver[i] = A[i].first;
        }
        for (int i = 0; i < m; i++) {
            int l, r, a, b;
            mLocalStream::ReadInt(&l);
            mLocalStream::ReadInt(&r);
            mLocalStream::ReadInt(&a);
            mLocalStream::ReadInt(&b);
            int va = (int) (lower_bound(fver+1, fver+n+1, a) - fver) - 1;
            int vb = (int) (upper_bound(fver+1, fver+n+1, b) - fver) - 1;
            mLocalStream::bprint.printInt(segTree.query(ver[va], ver[vb], l, r));
        }
    }
    return 0;
}

Read More +

2015-06-27

解題區/解題區 - Zerojudge

b414. BZOJ 3809 Gty 的二逼妹子序列

Problem

Autumn 和 Bakser 又在研究 Gty 的妹子序列了！

但他們遇到了一個難題，對於一段妹子們，他們想讓你幫忙求出這之內美麗度 $s_i \in [a, b]$ 的妹子的美麗度的種類數。為了方便，我們規定妹子們的美麗度全都在 $[1,n]$ 中。

給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$)，對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r, a, b$，每次輸出 $[s_l, \text{... },s_r]$ 中，權值 $s_i \in [a, b]$ 的權值種類數。

Sample Input

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

Sample Output

Solution

解決區間內數字在某個值域內部的種類數。

前情提要 ，如果單純問區間種類數 (獨特)，可以轉換成找區間內部有多少數字大於右端點，要預處理每一個數字的下一個相同數字的位置，只要符合大於右端點的條件即為獨特。可以使用持久化線段樹來做這件事情，依序加入序列數字，貪心去保留最右側的相同數字是獨特的，藉由多版本的區間相減來完成。

現在特別要求在某個值域內部，那就沒有好方法可解，可以使用莫隊下去完成。但是莫隊算法在區間轉移 (example [l, r] to [l, r+1]) 的效能要縮小到 $O(1)$，若使用一般樹結構，莫隊算法會衰退到 $O(N^{1.5} \log N)$，還不如修改快一點 $O(1)$，詢問慢一點 $O(\sqrt{N})$，將值域使用塊狀表方式記錄，來達到 $O(N^{1.5} + Q \sqrt{N})$

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
const int MAXV = 100005;
const int MAXQ = 1000005;
const int MAXSQRTV = 512;
class Offline {
public:
    struct Event {
        static int PILE, belong[MAXV];
        int l, r, x, y, qid;
        Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0):
            l(a), r(b), x(c), y(d), qid(e) {}
        bool operator<(const Event &x) const {
            if (belong[l] != belong[x.l])
                return l < x.l;
            return r < x.r; 
        }
    };
    int A[MAXN], N, qsize;
    Event event[MAXQ];
    int ret[MAXQ];
    void init(int N) {
        this->N = N, qsize = 0;
        memset(pile, 0, sizeof(pile));
        memset(val_count, 0, sizeof(val_count));
        val_PILE = Event::PILE = sqrt(N);
        for (int i = N; i >= 1; i--)
            val_belong[i] = Event::belong[i] = i / Event::PILE;
    }
    void q_add(int l, int r, int a, int b) {
        event[qsize] = Event(l, r, a, b, qsize);
        qsize++;
    }
    void run() {
        sort(event, event+qsize);
        
        int l = 1, r = 0;
        for (int i = 0; i < qsize; i++) {
            while (r < event[i].r)	r++, update(A[r], 1);
            while (r > event[i].r)	update(A[r], -1), r--;
            while (l > event[i].l)	l--, update(A[l], 1);
            while (l < event[i].l)	update(A[l], -1), l++;
            ret[event[i].qid] = query(event[i].x, event[i].y);
        }
    }
private:
    // unrolled
    int pile[MAXSQRTV], val_count[MAXV], val_belong[MAXV], val_PILE;
    inline void update(int x, int val) {
        val_count[x] += val;
        if (val == -1 && val_count[x] == 0)
            pile[val_belong[x]]--;
        if (val == 1 && val_count[x] == 1)
            pile[val_belong[x]]++;
    }
    int query(int a, int b) {
        int ret = 0;
        if (val_belong[a] == val_belong[b]) {
            for (int i = a; i <= b; i++)
                ret += val_count[i] > 0;
            return ret;
        }
        for (int i = val_belong[a]+1; i < val_belong[b]; i++)
            ret += pile[i];
        for (int i = (val_belong[a]+1)*val_PILE-1; i >= a; i--)
            ret += val_count[i] > 0;
        for (int i = (val_belong[b])*val_PILE; i <= b; i++)
            ret += val_count[i] > 0;
        return ret;
    }
} off;
int Offline::Event::PILE = 16, Offline::Event::belong[MAXV];
namespace mLocalStream {
    inline int readchar() {
        const int N = 1048576;
        static char buf[N];
        static char *p = buf, *end = buf;
        if(p == end) {
            if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
            p = buf;
        }
        return *p++;
    }
    inline int ReadInt(int *x) {
        static char c, neg;
        while((c = readchar()) < '-')    {if(c == EOF) return 0;}
        neg = (c == '-') ? -1 : 1;
        *x = (neg == 1) ? c-'0' : 0;
        while((c = readchar()) >= '0')
            *x = (*x << 3) + (*x << 1) + c-'0';
        *x *= neg;
        return 1;
    }
    class Print {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        Print() {
            p = buf, end = buf + N - 1;
        }
        void printInt(int x) {
            static char stk[16];
            int idx = 0;
            stk[idx++] = '\n';
            if (!x)	
                stk[idx++] = '0';
            while (x)
                stk[idx++] = x%10 + '0', x /= 10;
            while (idx) {
                if (p == end) {
                    *p = '\0';
                    printf("%s", buf), p = buf;
                }
                *p = stk[--idx], p++;
            }
        }
        ~Print() {
            *p = '\0';
            printf("%s", buf);
        }		
    } bprint;
}
int main() {
    int n, m, l, r, a, b;
    while (mLocalStream::ReadInt(&n)) {
        mLocalStream::ReadInt(&m);
        off.init(n);
        for (int i = 1; i <= n; i++)
            mLocalStream::ReadInt(&off.A[i]);
        for (int i = 0; i < m; i++) {
            mLocalStream::ReadInt(&l);
            mLocalStream::ReadInt(&r);
            mLocalStream::ReadInt(&a);
            mLocalStream::ReadInt(&b);
            off.q_add(l, r, a, b);
        }
        
        off.run();
        for (int i = 0; i < m; i++)
            mLocalStream::bprint.printInt(off.ret[i]);
//			printf("%d\n", off.ret[i]);
    }
    return 0;
}

Read More +

2015-06-26

解題區/解題區 - Zerojudge

b415. 輸出優化練習

Problem

寫題目不只會遇到算法複雜度問題，還會遇到語法上的瓶頸，了解更深入的作業系統架構、語言特性，了解每一個函數的實作方法，就能把代碼效能發揮到淋淋盡緻。當然，對於代碼轉成執行檔的最佳化技巧也是如此，接下來就來做個基礎題吧。

現在請處理一個偽隨機數計算，輸出前 $m$ 個值。

$x_{i+1} \equiv x_{i}^{2} \mod n$

有興趣的同學，可以查閱 Blum Blum Shub (BBS) Generator 相關隨機數算法。

Sample Input

1
2
3

90 141 5
52 57 5
19 129 5

Sample Output

1
2
3

90 63 21 18 42
52 25 55 4 16
19 103 31 58 10

Solution

手動轉字串，減少函數 printf() 的呼叫，一次將答案吐出來便可以達到加速，由於有一部分時間都花在取模，速度最多提升個兩到三倍。

用 putchar() 速度也會比 printf() 快一點，但沒有實作 buffer 來得快。

#include <bits/stdc++.h> 
  
namespace mLocalStream {
    inline int readchar() {
        const int N = 1048576;
        static char buf[N];
        static char *p = buf, *end = buf;
        if(p == end) {
            if((end = buf + fread(buf, 1, N, stdin)) == buf) return EOF;
            p = buf;
        }
        return *p++;
    }
    inline int ReadInt(int *x) {
        static char c, neg;
        while((c = readchar()) < '-')    {if(c == EOF) return 0;}
        neg = (c == '-') ? -1 : 1;
        *x = (neg == 1) ? c-'0' : 0;
        while((c = readchar()) >= '0')
            *x = (*x << 3) + (*x << 1) + c-'0';
        *x *= neg;
        return 1;
    }
    class Print {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        Print() {
            p = buf, end = buf + N - 1;
        }
        void printInt(int x, char padding) {
            static char stk[16];
            int idx = 0;
            stk[idx++] = padding;
            if (!x)	
                stk[idx++] = '0';
            while (x)
                stk[idx++] = x%10 + '0', x /= 10;
            while (idx) {
                if (p == end) {
                    *p = '\0';
                    printf("%s", buf), p = buf;
                }
                *p = stk[--idx], p++;
            }
        }
        static inline void online_printInt(int x) {
            static char ch[16];
            static int idx;
            idx = 0;
            if (x == 0)	ch[++idx] = 0;
            while (x > 0) ch[++idx] = x % 10, x /= 10;
            while (idx) 
                putchar(ch[idx--]+48);
        }
        ~Print() {
            *p = '\0';
            printf("%s", buf);
        }
    } bprint;
}
int main() {
    int x0, p, n;
    while (scanf("%d %d %d", &x0, &p, &n) == 3) {
        for (int i = 0; i < n; i++) {
            mLocalStream::bprint.printInt(x0, i == n-1 ? '\n' : ' ');
//			mLocalStream::Print::online_printInt(x0);
//			putchar(i == n-1 ? '\n' : ' ');
            x0 = ((long long) x0 * x0)%p;
        }
    }
    return 0;
}

Read More +

2015-06-25

解題區/解題區 - Zerojudge

d476. 區間查詢

Problem

一個長度為 n 的序列，支持兩種操作：

输出 $[A, B]$ 區間第 k 小的數 (從小到大排序後第 k 個)
修改第 I 個數為 W

Sample Input

Sample Output

1
2

2
3

Solution

前言

在討論用一些雜七雜八的樹類結構去跟莫隊算法搏鬥之餘，用了轉幾何方向去兜資料結構，隨後發現題目尋找的是 unique 而非計數，因此很多想法就垮台，當然出成另一道題目也是不錯。決定尋找其他想法！

開始

整體二分是什麼呢？假設操作只有修改、詢問，不包含插入、刪除，而且詢問是一個數值結果，這個數值結果可以藉由二分 + 掃描來完成，那就可以使用整體二分來離線支持。

對答案值域分治，將相關操作分治在一起，同時要保留順序性，分治過程中會不斷地累加每一個詢問的掃描數值，最後滿溢時紀錄答案。每一個操作最多在 $\log \text{MAXV}$ 層計算，因此複雜度是 $O(Q \log \text{MAXV})$。

好處是可以用常數較低的結構，所以會比較快？

應用

這一道經典題有很多作法，如持久化線段樹、塊狀鏈表、歸併樹、劃分樹、 … 等。其中能支持修改的有塊狀鏈表、複雜的持久化線段樹 (主席樹)。

帶修改的區間 K 小，概略說明二分答案 $x$，然後去查找小於等於 $x$ 的數字在區間 $[l, r]$ 內出現的次數是否大於等於 $K$。然後修改元素有加入跟移除，二分答案 mid，要將加入、移除會影響的 $A[i] \le mid$，加入或移除時對該數字的索引值 $i$ 建造統計方案。

對於(位置, 值) $\left \langle i, A[i] \right \rangle$ 來說，一開始的前 $N$ 個操作是加入 $\left \langle i, A[i] \right \rangle$，二分答案時，用一個 binary indexed tree 去維護 index 的個數，也就是說，對於修改元素 $\left \langle i, A[i] \right \rangle$ 相當於在二分答案 mid 時，插入 BIT.add(i, 1)，那對於區間詢問，相當於查找 BIT.query([l, r]) 如此一來就能知道區間 $[l, r]$ 在 mid 以內有幾個數字符合。

假設計數大於 k，詢問往左放，反之扣除已知 mid 以內的數量，詢問往右放，如此一來就完成了。

#include <bits/stdc++.h> 
using namespace std;
const int MAXQ = 65536;
const int MAXN = 65536;
const int INF = 0x3f3f3f3f;
class Offline {
public:
    struct Event {
        int x, y, k, qtype, qid;
        int calc; //
        Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0):
            x(a), y(b), k(c), qtype(d), qid(e), calc(f) {}
    };
    vector<Event> event;
    int N, ret[MAXQ];
    void init(int N) {
        this->N = N;
        event.clear();
    }
    void addEvent(int qtype, int qid, int x, int y, int k) {
        event.push_back(Event(x, y, k, qtype, qid));
    }
    void run() {
        DC(0, event.size()-1, 0, INF);
    }
private:
    // buffer
    int buf[MAXQ];
    Event ebuf1[MAXQ], ebuf2[MAXQ];
    // binary indexed tree
    int bit[MAXN];
    void add(int x, int val) {
        while (x <= N) {
            bit[x] += val;
            x += (x)&(-x);
        }
    }
    int query(int x) {
        int ret = 0;
        while (x) {
            ret += bit[x];
            x -= (x)&(-x);
        }
        return ret;
    }
    void DC(int q_l, int q_r, int val_l, int val_r) {
        if (q_l > q_r)	return ;
        if (val_l == val_r) {	// find
            for (int i = q_l; i <= q_r; i++)
                if (event[i].qtype == 2)
                    ret[event[i].qid] = val_l;
            return ;
        }
        int mid = (val_l + val_r)/2;
        for (int i = q_l; i <= q_r; i++) {
            if (event[i].qtype == 0 && event[i].y <= mid)
                add(event[i].x, 1);
            else if (event[i].qtype == 1 && event[i].y <= mid)
                add(event[i].x, -1);
            else if (event[i].qtype == 2)
                buf[i] = query(event[i].y) - query(event[i].x-1);
        }
        for (int i = q_l; i <= q_r; i++) { // resume
            if (event[i].qtype == 0 && event[i].y <= mid)
                add(event[i].x, -1);
            else if (event[i].qtype == 1 && event[i].y <= mid)
                add(event[i].x, 1);
        }
        int lidx = 0, ridx = 0;
        for (int i = q_l; i <= q_r; i++) {
            if (event[i].qtype == 0 || event[i].qtype == 1) {
                if (event[i].y <= mid)
                    ebuf1[lidx++] = event[i];
                else
                    ebuf2[ridx++] = event[i];
            } else {
                if (event[i].calc + buf[i] > event[i].k - 1)
                    ebuf1[lidx++] = event[i];
                else {
                    event[i].calc += buf[i];
                    ebuf2[ridx++] = event[i];
                }
            }
        }
        for (int i = 0; i < lidx; i++)
            event[q_l+i] = ebuf1[i];
        for (int i = 0; i < ridx; i++)
            event[q_l+lidx+i] = ebuf2[i];
        DC(q_l, q_l+lidx-1, val_l, mid);
        DC(q_l+lidx, q_r, mid+1, val_r);
    }
} off;
int main() {
    int n, m, x, y, k, v;
    int A[65536];
    char cmd[10];
    while (scanf("%d %d", &n, &m) == 2) {
        off.init(n);
        // qtype 0:add, 1:remove, 2: query
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
            off.addEvent(0, 0, i, A[i], 0);
        }
        
        int qid = 0;
        for (int i = 0; i < m; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'Q') {
                scanf("%d %d %d", &x, &y, &k);
                off.addEvent(2, qid++, x, y, k);
            } else {
                scanf("%d %d", &x, &v);
                off.addEvent(1, 0, x, A[x], 0);
                off.addEvent(0, 0, x, v, 0);
                A[x] = v;
            }
        }
        
        off.run();		
        for (int i = 0; i < qid; i++)
            printf("%d\n", off.ret[i]);
    }
    return 0;
}

Read More +

2015-06-22

解題區/解題區 - 其他題目

TIOJ 1475 錄製專輯 (Record)

Problem

Jolin 是個愛唱歌的小孩，每次總喜歡邊唱邊用電腦把自己的歌聲錄下來，因此長久下來，在她的電腦裡，已儲存了為數不小的個人歌唱作品。由於耶誕節快要到了，為了準備一份特別的耶誕禮物給爸爸，Jolin 準備從電腦中儲存的個人歌唱作品，挑選幾首歌製成一張個人專輯 CD。由於每張 CD 的容量有限，而Jolin 的個人歌唱作品早已遠遠超過一張 CD 可收錄的容量，因此 Jolin 希望你可以幫她想辦法，讓她所製作的專輯中，能有數目最多的歌曲（請注意：每一首歌只能被收錄一次），同時必需剛好裝滿整張 CD，不留下任何未使用的空間。

Sample Input

5
10 50 30 70 60
80 
5
10 50 30 70 60
20

Sample Output

1
2

2 4
0 0

Solution

實作 C++ 簡單的加法、乘法大數，直接把別提的拿過來用。

套用 0/1 背包問題，額外增加大數紀錄方法數，最後乘上 $N!$ 即可。

#include <bits/stdc++.h> 
using namespace std;
class BigInteger {
public:
    vector<long long> v;
    long long MAXC;
    BigInteger(int x = 0) {
        v = vector<long long>(10, 0);
        v[0] = x;
        MAXC = 100000000;
        normal();
    }
    BigInteger operator+(const BigInteger &x) const {
        BigInteger r(0);
        r.v.resize(max(v.size(), x.v.size()) + 2, 0);
        for (int i = 0; i < v.size(); i++)
            r.v[i] += v[i];
        for (int i = 0; i < x.v.size(); i++)
            r.v[i] += x.v[i];
        r.normal();
        return r;
    }
    BigInteger operator*(const BigInteger &x) const {
        BigInteger r(0);
        r.v.resize(v.size() + x.v.size() + 2, 0);
        for (int i = 0; i < v.size(); i++) {
            if (v[i] == 0)
                continue;
            for (int j = 0; j < x.v.size(); j++)
                r.v[i+j] += v[i] * x.v[j];
        }
        r.normal();
        return r;
    }
    void normal() {
        for (int i = 0; i < v.size(); i++) {
            if (v[i] >= MAXC) {
                v[i+1] += v[i] / MAXC;
                v[i] %= MAXC;
            }
        }
        int s = (int) v.size() - 1;
        while (s > 0 && v[s] == 0)
            s--;
        v.resize(s+1);
    }
    bool isZero() const {
        if (v.size() > 1)   return false;
        return v[0] == 0;
    }
    bool operator<(const BigInteger &x) const {
    	if (v.size() != x.v.size())
    		return v.size() < x.v.size();
    	for (int i = v.size()-1; i >= 0; i--) {
    		if (v[i] != x.v[i])
    			return v[i] < x.v[i];
    	}
    	return false;
    }
    bool operator==(const BigInteger &x)  const {
        if (v.size() != x.v.size())
            return false;
        for (int i = v.size()-1; i >= 0; i--)
            if (v[i] != x.v[i])
                return false;
        return true;
    }
    void print() {
        printf("%lld", v[v.size()-1]);
        for (int i = (int) v.size() - 2; i >= 0; i--)
            printf("%08lld", v[i]);
    }
};
int main() {
    int N, M, A[128];
    BigInteger f[128] = {};
    f[0] = BigInteger(1);
    for (int i = 1; i < 128; i++)
        f[i] = f[i-1] * BigInteger(i);
    while (scanf("%d", &N) == 1) {
        for (int i = 0; i < N; i++)
            scanf("%d", &A[i]);
        scanf("%d", &M);
        
        sort(A, A + N);
        int dp[10005] = {};
        BigInteger dp2[10005] = {};
        dp2[0] = BigInteger(1), dp[0] = 0;
        for (int i = 0; i < N; i++) {
            int x = A[i];
            for (int j = M; j >= x; j--) {
                if (dp[j] < dp[j-x] + 1 && !dp2[j-x].isZero())
                    dp[j] = dp[j-x] + 1, dp2[j] = BigInteger(0);
                if (dp[j] == dp[j-x] + 1 && !dp2[j-x].isZero())
                    dp2[j] = dp2[j] + dp2[j-x];
            }
        }
        int a = dp[M];
        BigInteger b = dp2[M] * f[a];
        
        printf("%d ", a);
        b.print();
        puts("");
    }
    return 0;
}
/*
5
10 50 30 70 60
20 
*/

Read More +

2015-06-22

解題區/解題區 - 其他題目

BZOJ 2038 小 Z 的袜子

Problem

給一個序列，詢問一個區間中任挑兩個數字，這兩個數字相同的機率為何，將答案化簡後輸出。

Sample Input

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output

2/5
0/1
1/1
4/15

Solution

莫隊算法命名是莫濤隊伍想出來的，不算是特別算法命名，估計是比賽中想到，目前沒看到英文命名。

莫隊算法處理離線詢問，回答所有答案複雜度為 $O(N^{1.5})$，其中 N 是區間索引值的範圍大小。概念在於分塊處理如下：

對於每個詢問的左端點放置於同一塊去處理
每一次處理一個塊狀的所有詢問
對於同一塊，詢問的右端點嚴格遞增去處理，讓左端點不斷地移動

發現到單獨看左端點指針的移動，約為 $O(N^{1.5})$，只考慮同一塊，最多有 $N$ 的詢問，一個詢問會造成左端點移動 $O(N^{0.5})$。而單獨看又端點指針的移動，約為 $O(N^{1.5})$，由於只會有 $O(N^{0.5})$ 塊，每一塊最慘就是遞增的移動 $O(N)$。

只要轉移區間 (維護區間的答案、計數，例如從 [l, r] 變成 [l, r-1] 的答案維護，把區間左右端點變大變小 1 的轉移計算) 的速度快，則複雜度約為 $O(N^{1.5})$。有不少情況需要 $O(\log N)$ 的其他數據結構維護轉移，複雜度就會變成 $O(N^{1.5} \log N)$，必要時使用塊狀表去作為數據結構進行轉移，當詢問次數 Q 與序列長度 N 呈線性關係，塊狀表支持 $O(1)$ 修改，$O(N^{0.5})$ 統計，那複雜度又能壓回 $O(N^{1.5})$。

能使用莫隊算法的題目，其中也不少能使用持久化結構來完成，若不考慮空間使用量，持久化結構能支持離線預處理、在線詢問。

#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 50005;
const int MAXV = 50005;
class Offline {
public:
    struct Event {
        static int PILE;
        int l, r, qid;
        Event(int a = 0, int b = 0, int c = 0):
            l(a), r(b), qid(c) {}
        bool operator<(const Event &x) const {
            if (l / PILE != x.l / PILE)
                return l < x.l;
            return r < x.r; 
        }
    };
    int A[MAXN], N, qsize;
    vector<Event> event;
    vector< pair<long long, long long> > ret;
    void init(int N) {
        this->N = N, qsize = 0;
        event.clear();
        memset(B, 0, sizeof(B));
        for (Event::PILE = 1; Event::PILE * Event::PILE < N; Event::PILE <<= 1);
    }
    void q_add(int l, int r) {
        event.push_back(Event(l, r, qsize));
        qsize++;
    }
    void run() {
        sort(event.begin(), event.end());
        ret.resize(event.size());
        
        int l = 1, r = 0;
        q_stat = 0;
        for (int i = 0; i < event.size(); i++) {
            while (r < event[i].r)	r++, update(A[r], 1);
            while (r > event[i].r)	update(A[r], -1), r--;
            while (l > event[i].l)	l--, update(A[l], 1);
            while (l < event[i].l)	update(A[l], -1), l++;
            long long a, b, len = event[i].r - event[i].l + 1;
            if (len > 1) {
                a = q_stat - len;
                b = len * (len - 1);
            } else {
                a = 0, b = 1;
            }
            ret[event[i].qid] = make_pair(a, b);
        }
    }
private:
    long long B[MAXV], q_stat;
    void update(int x, int val) {
        B[x] += val;
        q_stat += val * 2 * B[x] - 1;
    }
} off;
int Offline::Event::PILE = 16;
long long llgcd(long long x, long long y) {
    long long t;
    while (x%y)
        t = x, x = y, y = t%y;
    return y;
}
int main() {
    int N, M, l, r;
    while (scanf("%d %d", &N, &M) == 2) {
        off.init(N);
        for (int i = 1; i <= N; i++)
            scanf("%d", &off.A[i]);
        for (int i = 0; i < M; i++) {
            scanf("%d %d", &l, &r);
            off.q_add(l, r);
        }
        off.run();
        for (int i = 0; i < off.ret.size(); i++) {
            long long a = off.ret[i].first;
            long long b = off.ret[i].second;
            long long g = llgcd(a, b);
            a /= g, b /= g;
            printf("%lld/%lld\n", a, b);
        }
    }
    return 0;
}
/*
1 1
5
1 1
*/

Read More +

2015-06-22

解題區/解題區 - 其他題目

BZOJ 3065 帶插入區間 K 小值

Problem

詢問區間 K 小，額外支持插入一個元素到序列中。

Sample Input

10
10 5 8 28 0 19 2 31 1 22 
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27

Sample Output

Solution

直接修改可持久化塊狀鏈表的那一題 Zerojudge b411 記憶中的序列 2，把可持久化的記憶體拔掉，這樣就免得記憶體需求過大。出題者是想用替罪羊樹掛另一個平衡樹下去做。應該沒設想到塊狀鏈表在此題的速度也不算差。時限 60 秒大概跑了 30 秒，還不比樹套樹來得慢。

因為有插入操作，不管是主席樹還是函數式線段樹 (這兩個應該是同一個傢伙)，都無法辦到，只能靠可插入的平衡樹。

#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 65536;
const int MAXQ = 262144;
class UnrolledLinkedList {
public:
    struct Node {
        vector<int> A, B;
        Node *next, *alias;
        Node() {
            A.clear(), B.clear(), next = alias = NULL;
        }
        Node* real() {
            if (alias)	return alias;
            return this;
        }
        void insert(int x, int val) {
            if (alias) {
                A = alias->A, B = alias->B;
                alias = NULL;
            }
            A.insert(A.begin() + x, val);
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void erase(int x) {
            int val = A[x];
            A.erase(A.begin()+x);
            B.erase(lower_bound(B.begin(), B.end(), val));
        }
        void change(int x, int val) {
            int t = A[x];
            A[x] = val;
            B.erase(lower_bound(B.begin(), B.end(), t));
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void relax() {
            B = A;
            sort(B.begin(), B.end());
        }
    };
    int PSIZE;
    stack<Node*> mem;
    Node* init(int A[], int n) { // A[1:n]
        free();
        PSIZE = max((int) sqrt(n), 2);
        for (int i = 1; ; i <<= 1) {
            if (i >= PSIZE) {
                PSIZE = i;
                break;
            }
        }
        
        Node *u, *v, *head;
        
        head = newNode();
        u = head, v = NULL;
        for (int i = 1; i <= n; i++) {
            if (u->A.size() == PSIZE) {
                u->next = newNode();
                v = u, u = u->next;
            }
            u->A.push_back(A[i]);
        }
        for (u = head; u != NULL; u = u->next)
            u->relax();
        return head;
    }
    Node* newNode() {
        Node* p = new Node();
        mem.push(p);
        return p;
    }
    Node* cloneNode(Node *u) {
        Node *t = u->real();
        Node *p = new Node();
        *p = *t, p->next = u->next, mem.push(p);
        return p; 
    }
    Node* aliasNode(Node *u) {
        Node *t = u->real();
//		Node* p = new Node();
//		p->alias = t, p->next = u->next, mem.push(p);
//		return p;
        return u;
    }
    Node* erase(Node *ver, int x) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->erase(x - l);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* insert(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l-1 <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->insert(x - l + 1, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* change(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->change(x - l, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
        Node *u, *v;
        int ret = 0;
        u = ver;
        for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
            r = l + u->real()->A.size() - 1;
            if (L <= l && r <= R) {
                ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
                L = r + 1;
            } else if ((l <= L && L <= r) || (l <= R && R <= r)) {
                int i = L - l;
                while (i < u->real()->A.size() && L <= R) {
                    if (u->real()->A[i] <= val)
                        ret++;
                    i++, L++;
                }
            }
            if (ret >= threshold)	return ret;
        }
        return ret;
    }
    int find(Node *ver, int L, int R, int k)  {	// kth-number
        int l = 0, r = 100005, mid, t = 0; // value in A[]
        while (l <= r) {
            mid = (l + r)/2;
            if (findRank(ver, L, R, mid, k) >= k)
                r = mid - 1, t = mid;
            else
                l = mid + 1;
        }
        return t;
    }
    Node* mergeNode(Node *u, Node *v) {
        Node *p, *q;
        Node *a = newNode();
        p = u->real(), q = v->real();
        a->next = v->next;
        a->A.insert(a->A.end(), p->A.begin(), p->A.end());
        a->A.insert(a->A.end(), q->A.begin(), q->A.end());
        a->B.resize(a->A.size());
        merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
        return a;
    }
    Node* splitNode(Node *u) {
        Node *t = u->real();
        Node *a = newNode(), *b = newNode();
        int n = t->A.size()/2;
        a->next = b, b->next = u->next;
        a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
        b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
        a->relax(), b->relax();
        return a;
    }
    Node* relaxList(Node *ver) {
        Node *a, *b, *u, *v, *t;
        int need = 0;
        for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
            	need = 1;
            if (u->real()->A.size() > (PSIZE<<1))	// split
            	need = 1;
        }
        if (!need)
        	return ver;
        stack<Node*> remove;	// static used 
        for (u = ver, a = NULL; u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
            	if (a == NULL)
            		a = mergeNode(u, u->next), b = a;
            	else
            		b->next = mergeNode(u, u->next), b = b->next;
            	remove.push(u), remove.push(u->next); // static used  
                u = u->next;
            } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
            	if (a == NULL)
            		a = splitNode(u), b = a->next;
            	else
            		b->next = splitNode(u), b = b->next->next;
            	remove.push(u); // static used  
            } else {
            	if (a == NULL)	
                    a = aliasNode(u), b = a;
            	else			
                    b->next = aliasNode(u), b = b->next;
            }
        }
        while (!remove.empty()) { // static used  
        	u = remove.top(), remove.pop();
        	delete u;
        }	    	
        return a;
    }
    void debug(Node *head) {
        Node *u = head;
        printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
    }
    void free() {
        return ;
        while (!mem.empty()) {
            Node *u = mem.top();
            mem.pop();
            delete u;
        }
    }
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
    int x, y, v;
    char cmd[10];
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
        int encrypt = 0;
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%s", cmd);
            if (cmd[0] == 'I') {
                // insert A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.insert(ver[i-1], x-1, v);
            } else if (cmd[0] == 'Q') {
                scanf("%d %d %d", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                int t = dream.find(ver[i-1], x, y, v);
                printf("%d\n", t);
                encrypt = t;
                ver[i] = ver[i-1];
            } else if (cmd[0] == 'M') {
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.change(ver[i-1], x, v);
            }
//			dream.debug(ver[i]);
        }
    }
    return 0;
}
/*
5
1 2 3 4 5
9999
4 1 5 2
1 2 1
4 1 5 2
0 1
4 1 5 2
2 1
1 0 5
3 3 9
4 1 1 1
*/

Read More +

2015-06-22

解題區/解題區 - Zerojudge

b412. 記憶中的并查集

Problem

維護一個並查集的操作，並且支持版本回溯。

合併兩個堆
詢問兩個元素是否同堆
版本回溯

Sample Input

Sample Output

1
2
3

0
1
0

Solution

持久化概念，相當於維護 parent[] 陣列的版本，這一點可以利用可持久化線段樹來維護。

並查集的查詢功能不修改 parent[] 陣列，合併操作卻有可能修改數個 parent[]，為了降低記憶體用量，盡可能少用路徑壓縮這個技巧，雖然在一般並查集都會使用這個來加速，否則很容易變很慢，是因為持久化是會拉低速度，因為持久化需要 $O(\log N)$ 的時間去更改 parent[]，單筆路徑壓縮長度為 $M$ 個點，需要 $O(M \log N)$ 的調整，$M$ 在並查集中是常數類。

詢問不多時用啟發式合併就好，將小堆的元素合併到大堆中。效能會比較好。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
const int MAXN = 3000000;
class SegementTree {
public:
    struct Node {
        Node *lson, *rson;
        pair<int, int> val;
    } nodes[MAXN];
    int nodesize, L, R;
    Node* init(int l, int r) {
        nodesize = 0;
        L = l, R = r;
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        if (nodesize >= MAXN)
            exit(0);
        return &nodes[nodesize++];
    }
    Node* cloneNode(Node *p) {
        if (nodesize >= MAXN)
            exit(0);
        Node* u = &nodes[nodesize++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        u->lson = u->rson = NULL;
        if (l == r) {
            u->val = make_pair(l, 1);
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, pair<int, int> val, int l, int r) {
        Node *u = cloneNode(p);
        if (l == r) {
        	u->val = val;
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, val, l, mid);
        	else
         		u->rson = change(p->rson, x, val, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, pair<int, int> val) {
        return change(p, x, val, L, R);
    }
    pair<int, int> find(Node *ver, int x, int l, int r) {
        if (l == r)
        	return ver->val;
        int mid = (l + r)/2;
        if (x <= mid)
            return find(ver->lson, x, l, mid);
        else
            return find(ver->rson, x, mid+1, r);
    }
    pair<int, int> find(Node *ver, int x) {
        return find(ver, x, L, R);
    }
    // disjoint set
    pair<int, int> findp(Node *ver, int x) {
        pair<int, int> p = find(ver, x);
        return x == p.first ? p : findp(ver, p.first);
    }
    Node* joint(Node *ver, int x, int y) {
        pair<int, int> a = findp(ver, x);
        pair<int, int> b = findp(ver, y);
        if (a.first == b.first)
            return ver;
        Node *u = ver;
        if (a.second > b.second) {
            u = change(u, b.first, make_pair(a.first, b.second));
            u = change(u, a.first, make_pair(a.first, a.second + b.second));
        } else {
            u = change(u, a.first, make_pair(b.first, a.second));
            u = change(u, b.first, make_pair(b.first, a.second + b.second));
        }
        return u;
    }
} segTree;
const int MAXQ = 262144;
SegementTree::Node *ver[MAXQ];
int main() {
    int n, m;
    int cmd, x, y, v;
    while (scanf("%d %d", &n, &m) == 2) {
        ver[0] = segTree.init(1, n);
        int encrypt = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d", &cmd);
            cmd ^= encrypt;
            if (cmd == 0) { 		// back
                scanf("%d", &v);
                v ^= encrypt;
                ver[i] = ver[v];
            } else if (cmd == 1) {	// joint
                scanf("%d %d", &x, &y);
                x ^= encrypt, y ^= encrypt; 
                ver[i] = segTree.joint(ver[i-1], x, y);
            } else if (cmd == 2) {	// find
                scanf("%d %d", &x, &y);
                x ^= encrypt, y ^= encrypt;
                pair<int, int> a = segTree.findp(ver[i-1], x);
                pair<int, int> b = segTree.findp(ver[i-1], y);
                int t = a.first == b.first;
                printf("%d\n", t);
                ver[i] = ver[i-1];
                encrypt = t;
            } else {
                puts("WTF");
                return 0;
            }
        }
    }
    return 0;
}

Read More +

2015-06-22

解題區/解題區 - Zerojudge

b411. 記憶中的序列 2

Problem

動態區間 K 小，有四種操作

插入元素
刪除元素
修改元素
版本回溯
詢問某個區間的第 K 小元素

Sample Input

Sample Output

1
2
3

2
1
2

Solution

每次操作最多增加 $O(\sqrt{n})$ 記憶體，需要針對節點作抽象化，修改節點時再進行實體化，如此一來不用針對搜索路徑上的每一節點都進行複製，一般持久化平衡樹進行時，會直接複製整個節點，但塊狀鏈表若是複製下去會退化成時間、空間都是 $O(n)$ 的情況。

詢問時仍然需要二分搜索答案，看答案是否符合 K 小元素，也就是說要得到某個元素在區間中的排名。

塊狀鏈表代碼很醜，看看就好。如果需要支持修改、增加元素的區間 K 小，雖然複雜度高，但常數小、記憶體快取優勢，速度不比二元樹類型的資料結構來得慢，不管需不需要持久化塊狀鏈表都是這類型不錯的選擇。

另解

假設詢問為 $Q$ 個，聽說可以用區間 $[1, 2NQ]$ 的線段樹之類的超大區間線段樹，必要的探訪時進行開花 (將子節點打開)，利用標記計算相對位置來進行查詢。相對位置計算大概會在邊緣情況崩潰。

至於柳柳州提到的替罪羊樹是樹套樹下去持久化，每一個節點表示一個區間，接著在節點中建造一個平衡樹來查找區間 K 小元素。這樣的做法一樣需要二分搜索答案。但塊狀鏈表在速度跟記憶體都贏了，因為樹套樹的常數比較大，增加的記憶體也多。

#include <stdio.h>
#include <math.h>
#include <stack>
#include <assert.h>
#include <vector>
#include <limits.h>
#include <map>
#include <algorithm>
using namespace std;
const int MAXN = 32767;
const int MAXQ = 131072;
class UnrolledLinkedList {
public:
    struct Node {
        vector<int> A, B;
        Node *next, *alias;
        Node() {
            A.clear(), B.clear(), next = alias = NULL;
        }
        Node* real() {
            if (alias)	return alias;
            return this;
        }
        void insert(int x, int val) {
            if (alias) {
                A = alias->A, B = alias->B;
                alias = NULL;
            }
            A.insert(A.begin() + x, val);
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void erase(int x) {
            int val = A[x];
            A.erase(A.begin()+x);
            B.erase(lower_bound(B.begin(), B.end(), val));
        }
        void change(int x, int val) {
            int t = A[x];
            A[x] = val;
            B.erase(lower_bound(B.begin(), B.end(), t));
            B.resize(A.size());
            B[A.size()-1] = val;
            for (int i = (int) A.size()-1; i > 0 && B[i] < B[i-1]; i--)
                swap(B[i], B[i-1]);
        }
        void relax() {
            B = A;
            sort(B.begin(), B.end());
        }
    };
    int PSIZE;
    stack<Node*> mem;
    Node* init(int A[], int n) { // A[1:n]
        free();
        PSIZE = max((int) sqrt(n), 2);
        for (int i = 1; ; i <<= 1) {
            if (i >= PSIZE) {
                PSIZE = i;
                break;
            }
        }
        
        Node *u, *v, *head;
        
        head = newNode();
        u = head, v = NULL;
        for (int i = 1; i <= n; i++) {
            if (u->A.size() == PSIZE) {
                u->next = newNode();
                v = u, u = u->next;
            }
            u->A.push_back(A[i]);
        }
        for (u = head; u != NULL; u = u->next)
            u->relax();
        return head;
    }
    Node* newNode() {
        Node* p = new Node();
        mem.push(p);
        return p;
    }
    Node* cloneNode(Node *u) {
        Node *t = u->real();
        Node *p = new Node();
        *p = *t, p->next = u->next, mem.push(p);
        return p; 
    }
    Node* aliasNode(Node *u) {
        Node *t = u->real();
        Node* p = new Node();
        p->alias = t, p->next = u->next, mem.push(p);
        return p;
    }
    Node* erase(Node *ver, int x) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->erase(x - l);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* insert(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l-1 <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->insert(x - l + 1, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return relaxList(a);
    }
    Node* change(Node *ver, int x, int val) {
        Node *a, *b, *u, *v, *t;
        u = ver, a = NULL;
        for (int l = 1, r; u; l = r+1, u = u->next) {
            r = l + u->real()->A.size() - 1;
            if (l <= x && x <= r) {
                t = cloneNode(u);
                if (a == NULL)
                    a = t, b = a;
                else
                    b->next = t, b = b->next;
                t->change(x - l, val);
                t->next = u->next;
                break;
            } else {
                if (a == NULL)
                    a = aliasNode(u), b = a;
                else
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    int findRank(Node *ver, int L, int R, int val, int threshold = INT_MAX) {
        Node *u, *v;
        int ret = 0;
        u = ver;
        for (int l = 1, r; u != NULL; u = u->next, l = r+1) {
            r = l + u->real()->A.size() - 1;
            if (L <= l && r <= R) {
                ret += upper_bound(u->real()->B.begin(), u->real()->B.end(), val) - u->real()->B.begin();
                L = r + 1;
            } else if ((l <= L && L <= r) || (l <= R && R <= r)) {
                int i = L - l;
                while (i < u->real()->A.size() && L <= R) {
                    if (u->real()->A[i] <= val)
                        ret++;
                    i++, L++;
                }
            }
            if (ret >= threshold)	return ret;
        }
        return ret;
    }
    int find(Node *ver, int L, int R, int k)  {	// kth-number
        int l = 0, r = 100000, mid, t = 0; // value in A[]
        while (l <= r) {
            mid = (l + r)/2;
            if (findRank(ver, L, R, mid, k) >= k)
                r = mid - 1, t = mid;
            else
                l = mid + 1;
        }
        return t;
    }
    Node* mergeNode(Node *u, Node *v) {
        Node *p, *q;
        Node *a = newNode();
        p = u->real(), q = v->real();
        a->next = v->next;
        a->A.insert(a->A.end(), p->A.begin(), p->A.end());
        a->A.insert(a->A.end(), q->A.begin(), q->A.end());
        a->B.resize(a->A.size());
        merge(p->B.begin(), p->B.end(), q->B.begin(), q->B.end(), a->B.begin());
        return a;
    }
    Node* splitNode(Node *u) {
        Node *t = u->real();
        Node *a = newNode(), *b = newNode();
        int n = t->A.size()/2;
        a->next = b, b->next = u->next;
        a->A.insert(a->A.begin(), t->A.begin(), t->A.begin()+n);
        b->A.insert(b->A.begin(), t->A.begin()+n, t->A.end());
        a->relax(), b->relax();
        return a;
    }
    Node* relaxList(Node *ver) {
        Node *a, *b, *u, *v, *t;
        int need = 0;
        for (u = ver, a = NULL; !need && u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) // merge
            	need = 1;
            if (u->real()->A.size() > (PSIZE<<1))	// split
            	need = 1;
        }
        if (!need)
        	return ver;
        	
        for (u = ver, a = NULL; u != NULL; u = u->next) {
            if (u->next != NULL && u->real()->A.size() + u->next->real()->A.size() < (PSIZE<<1)) {	// merge
            	if (a == NULL)
            		a = mergeNode(u, u->next), b = a;
            	else
            		b->next = mergeNode(u, u->next), b = b->next;
                u = u->next;
            } else if (u->real()->A.size() > (PSIZE<<1)) {	// split
            	if (a == NULL)
            		a = splitNode(u), b = a->next;
            	else
            		b->next = splitNode(u), b = b->next->next;
            } else {
            	if (a == NULL)	
                    a = aliasNode(u), b = a;
            	else			
                    b->next = aliasNode(u), b = b->next;
            }
        }
        return a;
    }
    void debug(Node *head) {
        Node *u = head;
        printf("[");
    	while (u != NULL) {
        	for(int i = 0; i < u->real()->A.size(); i++)
            	printf("%d%s", u->real()->A[i], i != u->real()->A.size()-1 ? " " : " ");
        	u = u->next;
    	}
    	puts("]");
    }
    void free() {
        while (!mem.empty()) {
            Node *u = mem.top();
            mem.pop();
            delete u;
        }
    }
} dream; 
int A[MAXN], n, q;
UnrolledLinkedList::Node *ver[MAXQ];
int main() {
    int x, y, v, cmd;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]);
        ver[0] = dream.init(A, n);
//		dream.debug(ver[0]);
        int encrypt = 0;
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            scanf("%d", &cmd);
            cmd ^= encrypt;
            if (cmd == 0) {			// back version v
                scanf("%d", &v);
                v ^= encrypt;
                ver[i] = ver[v];
            } else if (cmd == 1) { 	// insert A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.insert(ver[i-1], x, v);
            } else if (cmd == 2) {	// delete A[x]
                scanf("%d", &x);
                x ^= encrypt;
                ver[i] = dream.erase(ver[i-1], x);
            } else if (cmd == 3) {	// make A[x] = v
                scanf("%d %d", &x, &v);
                x ^= encrypt, v ^= encrypt;
                ver[i] = dream.change(ver[i-1], x, v);
            } else if (cmd == 4) {
                scanf("%d %d %d", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                int t = dream.find(ver[i-1], x, y, v);
                printf("%d\n", t);
                encrypt = t;
                ver[i] = ver[i-1];
            } else {
                puts("WTF");
                return 0;
            }
//			dream.debug(ver[i]);
        }
    }
    return 0;
}

Read More +