けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

SPOJ DQUERY - D-query

Mo のアルゴリズムの練習に

問題へのリンク

問題概要

 N 要素の整数列  a_1, a_2, \dots, a_N が与えられる。以下の  Q 個のクエリに答えよ:

  • 数列の区間 [  l, r ) 内に何種類の整数があるかを答えよ

制約

  •  1 \le N \le 30000
  •  1 \le Q \le 2000000
  •  1 \le a_i \le 10^{6}

考えたこと

うしさんの記事の写経。Mo 法を手に入れた!!!

ライブラリの使い方としては、

int A[300001];
int res[200001];
int cnt[1000001];
int num_kind = 0;

void Mo::insert(int id) {
    int val = A[id];
    if (cnt[val] == 0) ++num_kind;
    ++cnt[val];
}

void Mo::erase(int id) {
    int val = A[id];
    --cnt[val];
    if (cnt[val] == 0) --num_kind;
}

の部分を毎回個別に書く。区間に対する情報を、

  • insert(id): 数 A[id] を区間に新たに加えるとどうなるかを更新
  • erase(id): 数 A[id] を区間から除くと加えるとどうなるかを更新
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
using namespace std;

struct Mo {
    vector<int> left, right, index; // the interval's left, right, index
    vector<bool> v;
    int window;
    int nl, nr, ptr;
    
    Mo(int n) : window((int)sqrt(n)), nl(0), nr(0), ptr(0), v(n, false) { }
    
    /* push */
    void push(int l, int r) { left.push_back(l), right.push_back(r); }
    
    /* sort intervals */
    void build() {
        index.resize(left.size());
        iota(index.begin(), index.end(), 0);
        sort(begin(index), end(index), [&](int a, int b)
        {
            if (left[a] / window != left[b] / window) return left[a] < left[b];
            return bool((right[a] < right[b]) ^ (left[a] / window % 2));
        });
        
        //        sort(index.begin(), index.end(), [&](int a, int b) {
        //            if (left[a] / window != right[b] / window) return left[a] < left[b];
        //            else return right[a] < right[b];
        //        });
    }
    
    /* extend-shorten */
    void extend_shorten(int id) {
        v[id].flip();
        if (v[id]) insert(id);
        else erase(id);
    }
    
    /* next id of interval */
    int next() {
        if (ptr == index.size()) return -1;
        int id = index[ptr];
        while (nl > left[id]) extend_shorten(--nl);
        while (nr < right[id]) extend_shorten(nr++);
        while (nl < left[id]) extend_shorten(nl++);
        while (nr > right[id]) extend_shorten(--nr);
        return index[ptr++];
    }
    
    /* insert, erase (to be set appropriately) */
    void insert(int id);
    void erase(int id);
};

int N, Q;
int A[300001];
int res[200001];
int cnt[1000001];
int num_kind = 0;

void Mo::insert(int id) {
    int val = A[id];
    if (cnt[val] == 0) ++num_kind;
    ++cnt[val];
}

void Mo::erase(int id) {
    int val = A[id];
    --cnt[val];
    if (cnt[val] == 0) --num_kind;
}

int main() {
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", &A[i]);
    scanf("%d", &Q);
    Mo mo(N);
    for(int i = 0; i < Q; i++) {
        int l, r; scanf("%d %d", &l, &r);
        mo.push(--l, r);
    }
    mo.build();
    for(int i = 0; i < Q; i++) res[mo.next()] = num_kind;
    for(int i = 0; i < Q; i++) printf("%d\n", res[i]);
}