解題區/解題區 - Zerojudge

b416. 誤會妹子序列

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 問題描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 莫隊算法
    2. 4.2. 掃描線
    3. 4.3. 可持久化

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