2015-06-27

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

1. Problem
2. Sample Input
3. Sample Output
4. Solution

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

Morris' Blog

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

contents

Problem

Sample Input

Sample Output

Solution