Offline Query Processing

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Fenwick Tree (Binary Indexed Tree) for point updates and prefix sums
5
struct Fenwick {
6
    int n; vector<int> bit;
7
    Fenwick(int n=0): n(n), bit(n+1, 0) {}
8
    void init(int n_) { n = n_; bit.assign(n+1, 0); }
9
    // add val at index i (1-based)
10
    void add(int i, int val){ for(; i<=n; i += i&-i) bit[i] += val; }
11
    // prefix sum [1..i]
12
    int sumPrefix(int i){ int s=0; for(; i>0; i -= i&-i) s += bit[i]; return s; }
13
    // range sum [l..r]
14
    int sumRange(int l, int r){ if(r<l) return 0; return sumPrefix(r) - sumPrefix(l-1); }
15
};
16
17
struct Query { int l, r, id; }; // 1-based inclusive
18
19
int main(){
20
    ios::sync_with_stdio(false);
21
    cin.tie(nullptr);
22
23
    int n, q; 
24
    if(!(cin >> n >> q)) return 0;
25
    vector<int> a(n+1);
26
    for(int i=1;i<=n;i++) cin >> a[i];
27
28
    // Coordinate compression for values of a[i]
29
    vector<int> vals(a.begin()+1, a.end());
30
    sort(vals.begin(), vals.end());
31
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
32
    for(int i=1;i<=n;i++){
33
        a[i] = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin()) + 1; // compressed to [1..K]
34
    }
35
36
    vector<Query> qs(q);
37
    for(int i=0;i<q;i++){
38
        int l, r; cin >> l >> r;
39
        qs[i] = {l, r, i};
40
    }
41
42
    sort(qs.begin(), qs.end(), [](const Query& A, const Query& B){
43
        if(A.r != B.r) return A.r < B.r; // sort by right endpoint
44
        return A.l < B.l;
45
    });
46
47
    Fenwick fw(n);
48
    vector<int> lastPos(vals.size()+2, 0); // last position of each value
49
    vector<int> ans(q, 0);
50
51
    int curR = 0;
52
    for(const auto& qu : qs){
53
        // advance r to qu.r
54
        while(curR < qu.r){
55
            ++curR;
56
            int v = a[curR];
57
            // if value v occurred before, remove its old contribution
58
            if(lastPos[v] != 0){
59
                fw.add(lastPos[v], -1);
60
            }
61
            // add current occurrence as the unique representative of v
62
            fw.add(curR, +1);
63
            lastPos[v] = curR;
64
        }
65
        // now answer number of distinct in [l..r] = sum of representatives in [l..r]
66
        ans[qu.id] = fw.sumRange(qu.l, qu.r);
67
    }
68
69
    for(int i=0;i<q;i++) cout << ans[i] << '\n';
70
    return 0;
71
}
72

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Query { int l, r, id; int block; };
5
6
int main(){
7
    ios::sync_with_stdio(false);
8
    cin.tie(nullptr);
9
10
    int n, q; 
11
    if(!(cin >> n >> q)) return 0;
12
    vector<int> a(n);
13
    for(int i=0;i<n;i++) cin >> a[i];
14
15
    // Coordinate compression for values
16
    vector<int> vals = a;
17
    sort(vals.begin(), vals.end());
18
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
19
    for(int i=0;i<n;i++) a[i] = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin());
20
21
    int B = max(1, (int)sqrt(n));
22
23
    vector<Query> qs(q);
24
    for(int i=0;i<q;i++){
25
        int l, r; cin >> l >> r; // assume 0-based inclusive input
26
        qs[i] = {l, r, i, l / B};
27
    }
28
29
    sort(qs.begin(), qs.end(), [&](const Query& A, const Query& BQ){
30
        if(A.block != BQ.block) return A.block < BQ.block;
31
        // For better locality, alternate r order by block parity
32
        if(A.block & 1) return A.r > BQ.r;
33
        return A.r < BQ.r;
34
    });
35
36
    vector<int> cnt(vals.size(), 0);
37
    int distinct = 0;
38
39
    auto add = [&](int pos){
40
        int v = a[pos];
41
        if(cnt[v] == 0) distinct++;
42
        cnt[v]++;
43
    };
44
    auto removePos = [&](int pos){
45
        int v = a[pos];
46
        cnt[v]--;
47
        if(cnt[v] == 0) distinct--;
48
    };
49
50
    vector<int> ans(q);
51
    int curL = 0, curR = -1; // current range is empty
52
53
    for(const auto& qu : qs){
54
        int L = qu.l, R = qu.r;
55
        // expand/shrink to [L, R]
56
        while(curL > L) add(--curL);
57
        while(curR < R) add(++curR);
58
        while(curL < L) removePos(curL++);
59
        while(curR > R) removePos(curR--);
60
        ans[qu.id] = distinct;
61
    }
62
63
    for(int i=0;i<q;i++) cout << ans[i] << '\n';
64
    return 0;
65
}
66

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct DSU {
5
    int n; vector<int> p, sz;
6
    DSU(int n=0): n(n), p(n), sz(n,1){ iota(p.begin(), p.end(), 0); }
7
    void init(int n_){ n = n_; p.resize(n); sz.assign(n,1); iota(p.begin(), p.end(), 0); }
8
    int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
9
    bool unite(int a, int b){ a=find(a); b=find(b); if(a==b) return false; if(sz[a]<sz[b]) swap(a,b); p[b]=a; sz[a]+=sz[b]; return true; }
10
    bool same(int a, int b){ return find(a)==find(b); }
11
};
12
13
struct Edge { int u, v; };
14
struct Op { int type; int u, v; }; // type: 0=del, 1=ask
15
16
static inline pair<int,int> normEdge(int u, int v){ if(u>v) swap(u,v); return {u,v}; }
17
18
int main(){
19
    ios::sync_with_stdio(false);
20
    cin.tie(nullptr);
21
22
    int n, m, q; 
23
    if(!(cin >> n >> m >> q)) return 0; // nodes 0..n-1
24
    vector<Edge> edges(m);
25
    for(int i=0;i<m;i++){ cin >> edges[i].u >> edges[i].v; }
26
27
    // Read operations: only deletions and connectivity queries
28
    vector<Op> ops(q);
29
    // Track which edges are deleted (possibly multiple deletions are not allowed)
30
    // We assume deletions refer to existing edges and no duplicate deletions for simplicity.
31
    set<pair<int,int>> initial;
32
    for(auto &e: edges) initial.insert(normEdge(e.u, e.v));
33
34
    vector<pair<int,int>> delList; delList.reserve(q);
35
36
    for(int i=0;i<q;i++){
37
        string t; int u, v; cin >> t >> u >> v; 
38
        if(t == "del"){
39
            ops[i] = {0, u, v};
40
            auto E = normEdge(u,v);
41
            if(initial.count(E)){
42
                initial.erase(E); // will be deleted later; not present in starting DSU
43
            }
44
            delList.push_back(E);
45
        } else { // "ask"
46
            ops[i] = {1, u, v};
47
        }
48
    }
49
50
    // Build DSU with edges that survive all deletions (i.e., still present after all ops)
51
    DSU dsu(n);
52
    for(auto &E : initial){ dsu.unite(E.first, E.second); }
53
54
    // Process operations in reverse: del -> add, ask -> answer now
55
    vector<string> ans; ans.reserve(q);
56
    for(int i=q-1;i>=0;i--){
57
        if(ops[i].type == 1){ // ask in reverse is still ask
58
            ans.push_back(dsu.same(ops[i].u, ops[i].v) ? "YES" : "NO");
59
        } else { // del in forward becomes add in reverse
60
            auto E = normEdge(ops[i].u, ops[i].v);
61
            dsu.unite(E.first, E.second);
62
        }
63
    }
64
65
    // Reverse answers to match input order of asks
66
    reverse(ans.begin(), ans.end());
67
    for(const auto &s : ans) cout << s << '\n';
68
    return 0;
69
}
70