let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

C11SEQ - Dãy số

solution.md

Bài này có cách làm thông thường là sửa dụng cây Fenwick:

Duyệt \(i\) từ 1 đến N, ở mỗi bước ta cần đếm số lượng vị trí \(j < i\) có \(L \le S[i] - S[j] \le R\) \(\iff S[i] - R \le S[j] \le S[i] - L\)

Cách làm đơn giản (không AC) sẽ như sau:

Duyệt \(i\) từ 1 đến N:

  • Tính \(S[i] = S[i-1] + A[i]\)
  • Truy vấn trên cây BIT để tính tổng trong đoạn \([S[i]-R, S[i]-L]\)
  • Truy vấn trên cây BIT, tăng phần tử ở vị trí \(S[i]\)

Dễ thấy cách làm này không thể AC vì giá trị của \(S[i]\) có thể lên đến \(10^{14}\), không thể lưu nổi.

Giải quyết vấn đề này bằng cách rời rạc hóa:

  • Sắp xếp lại \(S\), loại bỏ các phần tử bị trùng. Gọi mảng mới sau khi sắp xếp và loại phần tử trùng là \(X\).
  • Với truy vấn tăng phần tử ở vị trí \(S[i]\), ta tìm kiếm nhị phân để xác định vị trí của \(S[i]\) trên mảng \(X\). Rồi dùng giá trị này để thay thế \(S[i]\).
  • Với truy vấn tính tổng trong đoạn \([S[i]-R, S[i]-L]\), tương tự như trên, tìm kiếm nhị phân 2 giá trị \(S[i]-R\) và \(S[i]-L\) trên mảng \(X\).

Có thể thấy, cách làm trên khá rườm rà. Bài này có thể sử dụng cây nhị phân tìm kiếm. Ở mỗi bước chỉ cần duyệt trên cây để đếm số phần tử nằm trong khoảng \([S[i]-R, S[i]-R]\), sau đó cập nhật thêm \(S[i]\) vào cây. Code treap.cpp cài đặt phương pháp này sử dụng cấu trúc Treap, là một loại cây nhị phân tìm kiếm có kết hợp với yếu tố ngẫu nhiên để vừa hiệu quả vừa dễ cài đặt.

bit.cpp
Open in Github • Download 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define LL long long

struct SumIndex: private vector<LL> {
    SumIndex(const vector<int> &a) {
        set<LL> s;
        LL sum = 0;
        s.insert(sum);
        for (int x: a) sum += x, s.insert(sum);
        vector<LL>::operator=(vector<LL>(s.begin(), s.end()));
    }
    int operator()(LL x) const {
        return upper_bound(begin(), end(), x) - begin();
    }
    int size() const {
        return vector::size();
    }
};

struct Fenwick {
    int n, *f;
    Fenwick(int n): n(n), f(new int[n+1]()) {}
    ~Fenwick() { delete[] f; }
    void up(int i) {
        for (; i<=n; i += i&-i) f[i]++;
    }
    int sum(int i) {
        int res = 0;
        for (; i>0; i -= i&-i) res += f[i];
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    LL l, r; cin >> l >> r;
    vector<int> a(n);
    for (int &x: a) cin >> x;
    SumIndex index(a);
    LL sum = 0, res = 0;
    Fenwick f(index.size());
    f.up(index(sum));
    for (int x: a) {
        sum += x;
        res += f.sum(index(sum - l)) - f.sum(index(sum-r-1));
        f.up(index(sum));
    }
    cout << res;
    return 0;
}
treap.cpp
Open in Github • Download 
#include <iostream>
using namespace std;
#define LL long long
 
struct TreapNode {
    LL key;
    int prio, cnt = 1;
    TreapNode *left = NULL, *right = NULL;
    TreapNode(LL key): key(key), prio(rand()) {}
};

int get_cnt(TreapNode *p) {
    return p? p->cnt : 0;
}

TreapNode* rightRotate(TreapNode *y) {
    TreapNode *x = y->left, *T2 = x->right;
    x->right = y;
    y->left = T2;
    int temp = y->cnt;
    y->cnt = y->cnt - x->cnt + get_cnt(T2);
    x->cnt = temp;
    return x;
}
 
TreapNode* leftRotate(TreapNode *x) {
    TreapNode *y = x->right, *T2 = y->left;
    y->left = x;
    x->right = T2;
    int temp = x->cnt;
    x->cnt = x->cnt - y->cnt + get_cnt(T2);
    y->cnt = temp;
    return y;
}
 
TreapNode* insert(TreapNode* root, LL key) {
    if (!root) return new TreapNode(key);
    root->cnt += 1;
    if (key < root->key) {
        root->left = insert(root->left, key);
        if (root->left->prio > root->prio) root = rightRotate(root);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
        if (root->right->prio > root->prio) root = leftRotate(root);
    }
    return root;
}
 
int count_less(TreapNode* root, LL key) {
    if (!root) return 0;
    if (key == root->key) return get_cnt(root->left);
    if (key < root->key) return count_less(root->left, key);
    return root->cnt - get_cnt(root->right) + count_less(root->right, key);
}

int main() {
    srand(time(NULL));
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    LL l, r; cin >> l >> r;
    LL sum = 0, res = 0;
    TreapNode* root = NULL;
    root = insert(root, sum);
    while (n--) {
        int x; cin >> x;
        sum += x;
        res += count_less(root, sum - l + 1) - count_less(root, sum - r);
        root = insert(root, sum);
    }
    cout << res;
    return 0;
}
Comments