K-query II

Điểm: 1,01 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy ~n~ phần tử ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ và một số các truy vấn-k. Ngoài ra còn có một số thao tác cập nhật.

Một thao tác cập nhật là một cặp (~i~, ~v~) nghĩa là ~a_{i}~ cần được gán giá trị ~v~.

Một truy vấn-k là một bộ ba (~i~, ~j~, ~k~) (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~).

Với mỗi truy vấn-k (~i~, ~j~, ~k~), bạn phải trả về số phần tử lớn hơn ~k~ nằm trong dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~.

Input

Dòng ~1~: ~n~ (~1~ ~\leq~ ~n~ ~\leq~ ~30000~).
Dòng ~2~: ~n~ số ~a_{1}~, ~a_{2}~, ..., ~a_{n}~ (~1~ ~\leq~ ~a_{i}~ ~\leq~ ~10^{4}~).
Dòng ~3~: ~q~ (~1~ ~\leq~ ~q~ ~\leq~ ~200000~), số truy vấn và cập nhật.
~q~ dòng tiếp theo, số đầu tiên trong mỗi dòng là ~0~ hoặc ~1~. Số ~0~ theo sau bởi ~2~ số ~i~ và ~v~ (~1~ ~\leq~ ~i~ ~\leq~ ~n~, ~1~ ~\leq~ ~v~ ~\leq~ ~10^{4}~) cho biết một thao tác cập nhật. Số ~1~ theo sau bởi ~3~ số nguyên ~i~, ~j~, ~k~ (~1~ ~\leq~ ~i~ ~\leq~ ~j~ ~\leq~ ~n~, ~1~ ~\leq~ ~k~ ~\leq~ ~10^{4}~) cho biết một truy vấn-k.

Output

Với mỗi truy vấn-k (~i~, ~j~, ~k~), in ra số phần tử lớn hơn ~k~ trong dãy con ~a_{i}~, ~a_{i+1}~, ..., ~a_{j}~ trên một dòng.

Sample Input

Sample Output

2
1
2

Bình luận

Hãy đọc nội quy trước khi bình luận.

Anphat đã bình luận lúc 10, Tháng 8, 2025, 4:57 ← sửa 3 →

Mình thấy lời giải của bạn trangtrangVN khá hay, mình xin chia sẻ một lời giải khác.

Sử dụng thuật toán Mo.

Ta cần giải quyết hai vấn đề:

Tìm số lượng số lớn hơn ~k~ trong đoạn ~[l, r]~

Gọi ~c[i]~ là tần suất xuất hiện của ~i~. Để duy trì ~c[i]~ khá đơn giản. Nhưng để tìm số lượng số lớn hơn ~k~ nhanh thì chỉ dùng ~c~ là không đủ.

Ta sẽ chia mảng ~c~ thành các nhóm, mỗi nhóm có độ lớn khoảng ~100~. Gọi ~f[x]~ là tổng các ~c[i]~ có ~i~ nằm trong nhóm thứ ~x~.

Như vậy để tính số lượng số lớn hơn ~k~ trong đoạn ~[l, r]~ chỉ tốn ~O(100)~ khi duyệt qua các nhóm.

Cập nhật ~a[p] = v~

Các truy vấn update ta xử lý đơn giản bằng Mo with update.

Code:

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define uni(a) sort(all(a)), (a).resize(unique(all(a)) - (a).begin())

typedef pair <int, int> ii;

const int N = 2e5 + 10;
const int S = 1024;

struct query {
    int l, r, k, t, id;
};

struct update {
    int pos, prv, cur;
};

bool comp(query &a, query &b) {
    if (a.l / S != b.l / S) return a.l < b.l;
    else if (a.r / S != b.r / S) 
        return a.r < b.r;
    return a.t < b.t;
}

vector <update> modify;
vector <query> ask;

int n, q, a[N], l, r, t, c[N], b[N], f[N], ans[N];
vector <vector <int>> save;
vector <int> cp;
ll cnt[N];

void add(int x) {
    f[x / 100]++;
    c[x]++;
}

void sub(int x) {
    f[x / 100]--;
    c[x]--;
}

void upd(int p, int v) {
    if (l <= p && p <= r) {
        sub(a[p]);
        add(v);
    }
    a[p] = v;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }

    cin >> q;
    for (int i = 1; i <= q; i++) {
        int t, x, y, k;
        cin >> t >> x >> y;
        if (t == 0) {
            modify.push_back({x, b[x], y});
            b[x] = y;
        } else {
            cin >> k;
            ask.push_back({x, y, k, sz(modify) - 1, i});
        }
        ans[i] = -1;
    }
    sort(all(ask), comp);

    l = ask[0].l, r = ask[0].l - 1, t = -1;

    for (query &hehe : ask) {
        while (t < hehe.t) t++, upd(modify[t].pos, modify[t].cur);
        while (t > hehe.t) upd(modify[t].pos, modify[t].prv), t--;
        while (l > hehe.l) add(a[--l]);
        while (r < hehe.r) add(a[++r]);
        while (l < hehe.l) sub(a[l++]);
        while (r > hehe.r) sub(a[r--]);

        ans[hehe.id] = 0;
        for (int i = 100; i > hehe.k / 100; i--) {
            ans[hehe.id] += f[i];
        }

        for (int i = hehe.k + 1; i < (hehe.k / 100 + 1) * 100; i++) {
            ans[hehe.id] += c[i];
        }
    }

    for (int i = 1; i <= q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    } 

    return 0;
}

-4

dobaonam8386 đã bình luận lúc 28, Tháng 7, 2025, 16:36

mọi người giúp em bài này với ạ

-7

Huy_inIT đã bình luận lúc 10, Tháng 10, 2024, 5:11

Có bạn nào làm bằng merge sort tree không, mình xin code đọc với, mình bị tle

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-30

khiemgia1105 đã bình luận lúc 4, Tháng 10, 2024, 13:16

mấy dạng cho trẻ con :v

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-9

06DinhManhDung đã bình luận lúc 2, Tháng 8, 2024, 9:24

bài hay quá

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

68
trangtrangVN đã bình luận lúc 20, Tháng 2, 2024, 6:56 ← sửa 38 →
K-Query 2 làm như sau:

* Giải thuật bình thường: Dùng chia căn, chia mảng ra sqrt(n) block.Mỗi block dùng fenwick tree để quản lí.

Update: O(log(10000));

Trả lời: O(log(10000)*sqrt(n) + sqrt(n))

Tổng: O(q(log(10000)sqrt(n) + sqrt(n)))

Làm như trên sẽ TLE nên ta dùng segment tree để quản lí các block:

// Build:

build(1,1,sqrt(n)) // Cách build đọc trên wiki vì không có gì đặc biệt

Độ phức tạp O(m*log(m)) với m = sqrt(n);

+// Update:

int id = id của block quản lí vị trí update

while(id/=2) updateBIT(id,val,-1);

val = giá trị mới

id = id của block quản lí vị trí update

while(id/=2) updateBIT(id,val,1);

Độ phức tạp O(log(sqrt(n))*log(10000)) với m = sqrt(n);

//Get:

Viết hàm get như segment tree bình thường (lưu ý xử lí chia căn)

Độ phức tạp O(log(sqrt(n))*log(10000)) với m = sqrt(n);

Phần updateBIT và getBIT tham khảo bài viết Binary Indexed Tree của vnoi

//Code tham khảo: (Hãy AC bài trước khi tham khảo)

https://ideone.com/l8Y2Xb

Vậy là sẽ làm được bài này

Happy coding!

15

LA_NHVKhang đã bình luận lúc 12, Tháng 11, 2024, 1:19

Cảm ơn bạn 🥰

-14

ti21_phnam đã bình luận lúc 24, Tháng 11, 2022, 3:44

Nếu bài này truy vấn i = 0 là dạng tăng mỗi phần tử trên đoạn [l,r] lên x thì làm như thê nào vậy ạ.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-18

ti20_ntson đã bình luận lúc 24, Tháng 11, 2022, 5:10

Bạn có thể xử lí bài này bằng chia căn

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-8

2211khanhdh đã bình luận lúc 13, Tháng 7, 2023, 9:35

mình cũng xử lí chia căn nhưng mà bị time test cuối thì xử lí như nào h:v

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-17

ti21_phnam đã bình luận lúc 24, Tháng 11, 2022, 8:09

Bạn có thể giảng chi tiết hơn được không ạ. Mình cảm ơn ạ.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-38

khanhtuanitk20 đã bình luận lúc 25, Tháng 12, 2021, 16:11

ST i think

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-70

chicken_hand đã bình luận lúc 2, Tháng 9, 2021, 3:13 ← chỉnh sửa →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.