解題區/解題區 - Zerojudge

b422. Colorful Life and Monochromatic Life

Problem

將一張 rgb 表示的彩色影像變成灰階影像。

套用公式 round((r + g + b)/3) 得到新的像素色彩。

Sample Input

1
2
3
3 2
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18

Sample Output

1
2
3
3 2
2 2 2 5 5 5 8 8 8
11 11 11 14 14 14 17 17 17

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h> 
using namespace std;
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        printf("%d %d\n", n, m);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int r, g, b, w;
                scanf("%d %d %d", &r, &g, &b);
                w = (int) round((r + g + b)/3.0);
                printf("%d %d %d%c", w, w, w, j == n-1 ? '\n' : ' ');
            }
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b419. 公平的硬幣

Problem

一天，liouzhou_101 去打印店裏打印了幾張複習資料，花了 4 毛錢，他給了店主1張塊錢的鈔票，結果店主補了他兩枚硬幣，一個5毛錢，一個 1 毛錢。

在走回宿舍的途中，liouzhou_101 一直在想一個問題，5 毛錢的硬幣和 1 毛錢的硬幣哪個更公平？所謂公平，就是指將一枚硬幣拋擲 1 次，他正面朝上的概率是 12，反面朝上的概率也是 12。

結果他一會去就把1毛錢的硬幣拋了 1000 次， 記下來有 531 次正面朝上。然後他突然說道：“這硬幣不公平！！！”

真的不公平嗎？他希望你計算一下出現這種情況的概率。

Sample Input

1
2
3
4
5
10 5 5
20 6 8
100 40 60
1000 531 531
5000 2345 2456

Sample Output

1
2
3
4
5
0.2461
0.2310
0.9648
0.0037
0.1093

Solution

跟柳柳州互相出題目，已經來到了第 n 天，儘管我出的都是垃圾跟搬運題目，一出題被電得好愉悅，出在多的垃圾題都電不到柳柳州。

在擲硬幣找區間次數 $[a, b]$ 的機率，由於是離散的統計上就只能推組合數學，但又不是曲棍棒的模型 (Hockey Stick Pattern)，算了先手動窮舉，用 Stirling’s formula 計算組合，後來發現有幾組數據有問題。

當 n 太大的時候，機率分布就相當稀疏，直接套用數值積分，直接去積分自然分布得到公式稍微困難，利用 simpson 或者是 romberg 去解決，但這樣還會有一個問題，只有在平均值的部分機率非常高 (類似離散的 00000100000)，導致自適應辛普森積分會判斷錯誤，提醒剖半積分後測資就正確了不少。似乎合作出了一個可怕的題目，儘管如此，還是得用 mathlab 或者是 wolframalpha 來協助測資的檢驗，剩下的部分就交給柳柳州了。

關於自然分布 (normal distribution)：

  • 骰子擲 $n$ 次，命中的機率 $p = 1/2$
  • 期望值 $\mu = np = n/2$
  • 標準差為 $\sigma = \sqrt{np(1-p)} = \sqrt{n/4}$。

期望值 $E[x] = \sum_{k=1}^{n} k \binom{n}{k} p^k (1-p)^{n-k}$，消階層之後提出，計算後得到 $E[x] = np$。

而標準差 $\sigma$ 先從變異數下手

  • 定義： $Var[x] = E[(x - \mu)^2] = \sum (x - \mu)^2 P[X = x]$
  • 拆解步驟 1： $Var[x] = \sum (x^2 - 2 \mu x + \mu^{2}) P[X = x]$
  • 拆解步驟 2： $Var[x] = E[x^2] - 2 E[x] E[x] + E[x] E[x] = E[x^2] - E[x]^2$
  • 拆解步驟 3： $E[x^2] = E[x(x-1)] + E[x] = n(n-1)p^2 + np$
  • 拆解步驟 4： $Var[x] = np(1-p)$

接下來直接帶入自然分布的公式，參數 $(\mu, \sigma)$，特別小心使用辛普森積分 $[a, b]$ 時，由於問題是離散的，要改變成 $[a - 0.5, b + 0.5]$，防止 $a = b$ 時造成積分錯誤。

特別感謝學弟 firejox 的數學指導。

不久之後，firejox 說道內建函數 erf() 可以解決積分問題，詳見 wiki Gauss error function，因此這一題也可以不寫辛普森積分，套用內建函數在不到 10 行內解決此題。

暴力檢測

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
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1), e = exp(1);
const int MAXN = 100001;
double f[MAXN];
double stirling(int n) {
    if (n < MAXN)
        return f[n];
    return log2(sqrt(2*PI*n)) + n*log2(n/e);
}
double logC(int n, int m) {
    return stirling(n) - stirling(n - m) - stirling(m);
}
int main() {
    f[0] = 0;
    for (int i = 1; i < MAXN; i++)
        f[i] = log2(i) + f[i-1];
    int n, a, b;
    int cases = 0;
    while (scanf("%d %d %d", &n, &a, &b) == 3) {
        double ret = 0;
        for (int i = a; i <= b; i++)
            ret += pow(2, logC(n, i) - log2(2) * n);
        printf("%.4lf\n", ret);
        if (++cases > 100)
            break;
    }
    return 0;
}

數值積分

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
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1), e = exp(1);
const int MAXN = 1001;
double f[MAXN];
double stirling(int n) {
    if (n < MAXN)
        return f[n];
    return log2(sqrt(2*PI*n)) + n*log2(n/e);
}
double logC(int n, int m) {
    return stirling(n) - stirling(n - m) - stirling(m);
}
class SimpsonIntegral {
public:
    const double eps = 1e-6;
    const double pi = acos(-1);
    const double sqr2pi = sqrt(2 * pi);
    double mu, sigma; // function coefficient
    double f(double x) { // usually replace
        return exp(-(pow(x - mu, 2)/2.0/sigma/sigma))/ sigma / sqr2pi;
    }
    void setCoefficient(double m, double s) {
        this->mu = m, this->sigma = s;
    } 
    double simpson(double a, double b, double fa, double fb, double fab) {
        return (fa + 4 * fab + fb) * (b - a) / 6.0;
    }
    double integral(double l, double r) {
        return integral(l, r, eps);
    }
private:
    double integral(double a, double b, double c, double eps, double A, double fa, double fb, double fc) {
        double ab = (a + b)/2, bc = (b + c)/2;
        double fab = f(ab), fbc = f(bc);
        double L = simpson(a, b, fa, fb, fab), R = simpson(b, c, fb, fc, fbc);
        if (fabs(L + R - A) <= 15 * eps)
            return L + R + (L + R - A) / 15.0;
        return integral(a, ab, b, eps/2, L, fa, fab, fb) + integral(b, bc, c, eps/2, R, fb, fbc, fc);
    }
    double integral(double a, double b, double eps) {
        double ab = (a + b) /2;
        double fa = f(a), fb = f(b), fab = f(ab);
        return integral(a, ab, b, eps, simpson(a, b, fa, fb, fab), fa, fab, fb);
    }
} tool;
double binom(double n, double a, double b) {
    double a1, b1;
    double d = sqrt(n/2.0);
    a1 = 0.5 * (1.0 + erf((a - n/2.0 - 0.5) / d));
    b1 = 0.5 * (1.0 + erf((b - n/2.0 + 0.5) / d));
    return b1 - a1;
}
int main() {
    f[0] = 0;
    for (int i = 1; i < MAXN; i++)
        f[i] = log2(i) + f[i-1];
    int n, a, b;
    int cases = 0;
    while (scanf("%d %d %d", &n, &a, &b) == 3) {
        cases++;
        if (n < MAXN) {
            double ret = 0;
            for (int i = a; i <= b; i++)
                ret += pow(2, logC(n, i) - log2(2) * n);
            printf("%.4lf\n", ret);
        } else {
//			tool.setCoefficient(n/2.0, sqrt(n/4.0));
//			double ret = 0, l = a - 0.5, r = b + 0.5;
//			if (r < n/2.0 || l > n/2.0)
//				ret = tool.integral(l, r);
//			else
//				ret = tool.integral(l, n/2.0) + tool.integral(n/2.0, r);
//			printf("%.4lf\n", ret);
            printf("%.4lf\n", binom(n, a, b));
        } 
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b417. 區間眾數

Problem

背景

大學上課是怎麼回事的呢？談論到學期成績計算，很多奇聞軼事可以說的，例如教授任選三題批改、同學任選三題作答、滿分三百、沒有考試、 … 等。筆試類型的考試只是最常見的一種，還有所謂的多才華加分，例如上台報告、舉手發問、參與展覽、參加競賽、 … 等。

不幸地，某 M 修了一堂怪課，教授每一堂課結束後總是會大聲宣揚「葛萊分多加 5 分」對於需要不斷複習演練的某 M 而言，這門課的即時評分方式讓其非常挫敗。神奇的是，有一次教授這麼問同學「給一序列，請計算眾數、平均數、中位數，答對加分。」某 M 剎那間傻住，大學的學期成績可以用這種問題獲得，當他在懷疑這個問題時，問題早已被同學回答走。

某 M 非常不甘心，計算眾數、平均數、中位數就能夠加分，要求只是 n = 10 的序列。既然加分有理，出題吧！

題目描述

平均數、中位數可以藉由區間總和、區間 K 小問題來完成，現在來解決眾數。

給定一個長度為 $n$ ( $1 \le n \le 100000$ ) 的正整數序列 $s$ ($1 \le s_i \le n$)，對於 $m$ ( $1 \le m \le 1000000$) 次詢問 $l, r$，每次輸出 $[s_l, \text{... },s_r]$ 中，出現最多次的次數以及有多少種數字出現最多次。

Sample Input

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

Sample Output

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

Solution

眾數區間查找 Range mode query 性質可以參考維基百科。

在這一題中，這裡提供三種解法，但我的寫法中只有莫隊算法可以通過，其餘算法受到時間跟空間上的限制，需要額外的優化，細節就不多做說明：

  • 莫隊算法
    只能離線處理，無法強制在線詢問，維護眾數最高頻率指針，來統計眾數的對應次數和等價眾數的個數，由於指針移動都是 $O(1)$，整體上時間效能為 $O(N^{1.5})$。
  • 分塊在線 1
    離線預處理 $O(N^{0.5} \times N^{0.5} \times \log{N})$
    提供在線詢問 $O(\text{ans} \times \log{N})$，由於知道每一個塊中的代表眾數都可能是答案，因此預處理每一個塊的眾數，其餘的非眾數捨棄掉，最慘情況是每個數字都出現一次，在線詢問時複雜度會掉到 $O(N \log N)$。
  • 分塊在線 2
    • 離線預處理時間 $O(N \times L^2)$，提供在線詢問 $O(N/L)$，其中 $L$ 表示有多少個分塊。
    • 預處理分塊編號 $PILE[i, j]$ 的眾數情況 (類似莫隊維護指針)，因此記憶體消耗 $O(N \times L^2)$。
    • 對於每一處詢問，會對應預處理中的區域塊的紀錄 $PILE[L, R]$，接著頭尾兩端的殘存數字再依序加入，意即 $A[a, L-1]$ 和 $A[R+1, b]$ 的數字加入的複雜度 $O(1)$，隨後再進行撤銷 $O(1)$。
    • 假設詢問次數 $Q$ 與 $N$ 呈現性關係，整體需要 $O(N \times L^2 + N^2 / L)$，則 $L = N^{1/3}$ 是最好的情況，意即每一個塊具有 $O(N^{2/3})$ 個數字，最後得到整體時間效能為 $O(N^{1.66})$。

由於這一題目標不是找到眾數為何 (這牽涉到最小字典順序)，而是找眾數的出現個數和有幾種眾數可能，莫隊算法會快於其他算法。若是要求最小眾數莫隊算法需要 $O(N^{1.5} \log{N})$，分塊在線 1 也是 $O(N^{1.5} \log{N})$。

分塊在線 2 在此題不僅僅遇到記憶體過大，只好鬆弛 $L$ 來壓低記憶體用量，但增加時間需求，時間上慢個 10 倍以上。

莫隊算法

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
const int MAXV = 100005;
const int MAXQ = 1000005;
class Offline {
public:
    struct Event {
        static int PILE, belong[MAXV];
        int l, r, qid;
        Event(int a = 0, int b = 0, int e = 0):
            l(a), r(b), qid(e) {}
        bool operator<(const Event &x) const {
            if (belong[l] != belong[x.l])
                return l < x.l;
            return r < x.r; 
        }
    } event[MAXQ];
    int A[MAXN], N, qsize;
    int ret[MAXQ][2];
    void init(int N) {
        this->N = N, qsize = 0;
        memset(val_count, 0, sizeof(val_count));
        memset(mode_freq, 0, sizeof(mode_freq));
        mode_idx = 0;
        Event::PILE = sqrt(N);
        for (int i = N; i >= 1; i--)
            Event::belong[i] = i / Event::PILE;
    }
    void q_add(int l, int r) {
        event[qsize] = Event(l, r, 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][0] = mode_idx;
            ret[event[i].qid][1] = mode_freq[mode_idx];
        }
    }
private:
    // unrolled
    int val_count[MAXV], mode_freq[MAXN], mode_idx;
    inline void update(int x, int val) {
        if (val == 1) {
            mode_freq[val_count[x]]--;
            val_count[x]++;
            mode_freq[val_count[x]]++;
            if (mode_freq[mode_idx+1] != 0)
                mode_idx++;
        } else if (val == -1) {
            mode_freq[val_count[x]]--;
            val_count[x]--;
            mode_freq[val_count[x]]++;
            if (mode_freq[mode_idx] == 0)
                mode_idx--;
        }
    }
} off;
int Offline::Event::PILE = 16, Offline::Event::belong[MAXV];
namespace mLocalStream {
    class M {
    public:
        static const int N = 1048576;
        char buf[N], *p, *end;
        M() {
            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++;
            }
        }	
        static inline int readchar() {
            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++;
        }
        static 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;
        }
        ~M() {
            *p = '\0';
            printf("%s", buf);
        }		
    } bprint;
}
int main() {
    int n, m, l, r, a, b;
    while (mLocalStream::M::ReadInt(&n)) {
        mLocalStream::M::ReadInt(&m);
        off.init(n);
        for (int i = 1; i <= n; i++)
            mLocalStream::M::ReadInt(&off.A[i]);
        for (int i = 0; i < m; i++) {
            mLocalStream::M::ReadInt(&l);
            mLocalStream::M::ReadInt(&r);
            off.q_add(l, r);
        }
        
        off.run();
        for (int i = 0; i < m; i++)
            printf("%d %d\n", off.ret[i][0], off.ret[i][1]);
    }
    return 0;
}

分塊在線 1

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
class ModeQuery {
public:
    int A[MAXN], N, PILE, belong[MAXN];
    vector< vector<int> > V, Vmode;
    vector<int> POS[MAXN];
    int q_dup[MAXN], q_cases;
    void make(int n) {
        N = n, q_cases = 0;
        for (PILE = 1; PILE * PILE < N; PILE <<= 1);
        
        V.clear(), Vmode.clear();
        for (int l = 0, r; l < N; l = r+1) {
            r = min(l + PILE - 1, N-1);
            V.push_back(vector<int>(A+l, A+r+1));
            Vmode.push_back(vector<int>());
        }
        
        for (int i = 0; i < V.size(); i++) {
            sort(V[i].begin(), V[i].end());
            int mx_cnt = 1, cnt = 1;
            for (int j = 1; j <= V[i].size(); j++) {
                if (j == V[i].size() || V[i][j] != V[i][j-1]) {
                    if (cnt > mx_cnt)	
                        mx_cnt = cnt, Vmode[i].clear();
                    if (cnt == mx_cnt)
                        Vmode[i].push_back(V[i][j-1]);
                    cnt = 1;
                } else {
                    cnt++;
                }
            }
        }
        
        for (int i = 1; i <= N; i++) // value range
            POS[i].clear(), q_dup[i] = 0;
        for (int i = 0; i < N; i++)
            POS[A[i]].push_back(i);
        for (int i = N-1; i >= 0; i--)
            belong[i] = i / PILE;
    }
    int compute_cnt(int x, int l, int r) {
        if (q_dup[x] == q_cases)
            return 0;
        q_dup[x] = q_cases;
        int va = (int) (lower_bound(POS[x].begin(), POS[x].end(), l) - POS[x].begin()) - 1;
        int vb = (int) (upper_bound(POS[x].begin(), POS[x].end(), r) - POS[x].begin()) - 1;
        return vb - va;
    }
    void query(int l, int r, int &a, int &b) {
        static int t;
        q_cases++;
        a = b = 0;
        if (belong[l] == belong[r]) {
            for (int i = l; i <= r; i++) {
                t = compute_cnt(A[i], l, r);
                if (t > a)	a = t, b = 0;
                if (t == a)	b++;
            }	
            return ;		
        }
        for (int i = belong[l]+1; i < belong[r]; i++) {
            for (int j = 0; j < Vmode[i].size(); j++) {
                t = compute_cnt(Vmode[i][j], l, r);
                if (t > a)	a = t, b = 0;
                if (t == a)	b++;
            }
        }
        for (int i = (belong[a]+1)*PILE-1; i >= l; i--) {
            t = compute_cnt(A[i], l, r);
            if (t > a)	a = t, b = 0;
            if (t == a)	b++;
        }
        for (int i = (belong[b])*PILE; i <= r; i++) {
            t = compute_cnt(A[i], l, r);
            if (t > a)	a = t, b = 0;
            if (t == a)	b++;
        }
    }
} dream;
int main() {
    int n, m, l, r, a, b;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &dream.A[i]);
        dream.make(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &l, &r);
            l--, r--;
            dream.query(l, r, a, b);
            printf("%d %d\n", a, b);
        }
    }
    return 0;
}

分塊在線 2

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
#include <bits/stdc++.h> 
using namespace std;
const int MAXN = 100005;
const int MAXS = 35;
class ModeQuery {
public:
    struct Kit {
        unsigned short cnt[MAXN], freq[MAXN];
        int mode_idx;
        Kit() {
            init();
        }
        void init() {
            mode_idx = 0;
        }
        void add(int x, int val) {
            freq[cnt[x]]--;
            cnt[x] += val;
            freq[cnt[x]]++;
            if (cnt[x] > mode_idx)
                mode_idx = cnt[x];
        }
        void resume(int x, int val) {
            freq[cnt[x]]--;
            cnt[x] -= val;
            freq[cnt[x]]++;
        } 
    } f[MAXS * MAXS/2], kit;
    int fr[MAXS][MAXS];
    int A[MAXN], N, PILE, belong[MAXN];
    vector< pair<int, int> > V;
    void heavy() {
        int ff = 0;
        for (int i = 0; i < V.size(); i++)
            for (int j = i; j < V.size(); j++)
                fr[i][j] = ff++;
        for (int i = 0; i < V.size(); i++)
            for (int j = 0; j < i; j++)
                fr[i][j] = ff;
        for (int i = 0; i < V.size(); i++) {
            f[fr[i][i]].init();
            for (int j = V[i].first; j <= V[i].second; j++)
                f[fr[i][i]].add(A[j], 1);
        }
        for (int i = 0; i < V.size(); i++) {
            for (int j = i+1; j < V.size(); j++) {
                f[fr[i][j]] = f[fr[i][j-1]];
                for (int k = V[j].first; k <= V[j].second; k++)
                    f[fr[i][j]].add(A[k], 1);
            }
        }
    }
    void make(int n) {
        N = n;
        PILE = (int) pow(n, 0.70) + 1;
                
        V.clear();
        for (int l = 0, r; l < N; l = r+1) {
            r = min(l + PILE - 1, N-1);
            V.push_back(make_pair(l, r));
        }
        for (int i = N-1; i >= 0; i--)
            belong[i] = i / PILE;
        heavy();
    }
    void query(int l, int r, int &a, int &b) {
        int bl = belong[l], br = belong[r];
        if (bl == br || r - l <= PILE + 10) {
            kit.init();
            for (int i = l; i <= r; i++)
                kit.add(A[i], 1);
            a = kit.freq[kit.mode_idx], b = kit.mode_idx;
            for (int i = l; i <= r; i++)
                kit.resume(A[i], 1);
            return ;
        }
        if (l >= 0 && belong[l-1] == bl)	
            bl++;
        if (r < N && belong[r+1] == br)
            br--;
        Kit &tmp = f[fr[bl][br]];
        int tmp_mode_idx = tmp.mode_idx;
        for (int i = bl*PILE - 1; i >= l; i--)
            tmp.add(A[i], 1);
        for (int i = (br+1)*PILE; i <= r; i++)
            tmp.add(A[i], 1);
        a = tmp.freq[tmp.mode_idx], b = tmp.mode_idx;
        for (int i = bl*PILE - 1; i >= l; i--)
            tmp.resume(A[i], 1);
        for (int i = (br+1)*PILE; i <= r; i++)
            tmp.resume(A[i], 1);
        tmp.mode_idx = tmp_mode_idx;
    }
} dream;
int main() {
    int n, m, l, r, a, b;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 0; i < n; i++)
            scanf("%d", &dream.A[i]);
        dream.make(n);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &l, &r);
            l--, r--;
            dream.query(l, r, a, b);
            printf("%d %d\n", b, a);
        }
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b418. 八成真物

Problem

「偽物比真物更有價值」—貝木泥舟
「真物和偽物一樣有價值」—忍野咩咩
「偽娘比真娘更有價值」—精英島民

任兩個物品的相似度$sim(A, B) = \frac{|A \cap B|}{|A \cup B|}$，換句話說把 $A$ 具有的特徵和 $B$ 具有的特徵類型取交集、聯集個數，相除就能得到其相似度。例如有 5 個特徵，若 A 表示成 11001、B 表示成 01100$sim(A, B) = \frac{|{2}|}{|{1, 2, 3, 5}|} = 0.25$。

現在盤面上有 N 個物品、M 種特徵，請問相似度大於等於 0.8 的相似對數 $S$ 有多少種。為了讓這一題更有趣味，算法允許偽物，輸出$\frac{S}{N(N-1)/2} \times 100$。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
8 10
0111101101
0111101100
0111101100
0111101101
1100101010
0111101100
0111101100
0011101111
  
8 10
1111101100
1011101100
1010101100
1010111010
0100110100
1011101100
1110110000
1011111100

Sample Output

1
2
53.57
25.00

Solution

利用 std::bitset 加速交集和聯集運算，將數個屬性壓縮到一個 32-bits 單位，然後藉 bitcount 盡可能在 $O(1)$ 的時間內完成，就有機會通過這一題。一般的 $O(N^2 M)$ 比 $O(N^2 M/32)$ 慢個五六倍。

此外，特別小心浮點數計算誤差，5.0/4.0 >= 0.8 == false，用乘法判定大於閥值的操作。

關於 LSH 的部分，還在進行測試，若 signature 計算太慢，還不如直接暴力法，若能分散找到 signature 或者是預先有辦法處理好，那分桶計算就會好一點。

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
#include <bits/stdc++.h> 
using namespace std;
int main() {
    int n, m;
    char s[1024];
    while (scanf("%d %d", &n, &m) == 2) {
        bitset<512> attr[n];
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            attr[i] = bitset<512>(s);
        }
        
        double ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                int a = (attr[i]&attr[j]).count();
                int b = (attr[i]|attr[j]).count();
                if (5 * a >= 4 * b)
                    ret++;
            }
        }
        printf("%.2lf\n", ret * 100 / (n * (n-1)/2));
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

b413. 虛擬女友

Problem

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

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

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

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

Sample Input

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

Sample Output

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

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，寫起來會比較不方便。

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
#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 +
解題區/解題區 - 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

1
2
3
4
5
6
7
8
9
10
11
12
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

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

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。

莫隊算法

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
#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;
}

掃描線

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
//#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;
}

可持久化

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
#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 +
解題區/解題區 - 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

1
2
3
4
5
6
7
8
9
10
11
12
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

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

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})$

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
#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 +
解題區/解題區 - 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 來得快。

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
#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 +
解題區/解題區 - Zerojudge

d476. 區間查詢

Problem

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

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

Sample Input

1
2
3
4
5
5 3
1 2 3 4 5
Q 1 4 2
C 2 5
Q 1 4 2

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 以內的數量，詢問往右放，如此一來就完成了。

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
#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 +
解題區/解題區 - Zerojudge

b412. 記憶中的并查集

Problem

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

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

Sample Input

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

Sample Output

1
2
3
0
1
0

Solution

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

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

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

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