# Gợi ý segtri 22/08/2023

## [Cuộc đua](https://marisaoj.com/problem/363)
- Mảng $P$ đáp án phải có tính chất số lượng $P_j > P_i$ mà $j < i$ là $A_i$.
- Hãy thứ khôi phục mảng $P$ bằng cách tìm lần lượt xem, các thí sinh $i$ từ $1$ đến $n$ về đích thứ bao nhiêu.
- Tối ưu từ $n^2 \log n$ về $n \log n$ bằng kĩ thuật Segment Tree Walk.

Code
:::spoiler

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1e6 + 5;

int n;
int a[maxn];
int ans[maxn];
int lmao[maxn];

struct SegmentTree{
    vector<int> node;
    SegmentTree(int n): node(4 * n + 2){}

    void build(int v, int l, int r){
        if(l == r){
            node[v] = 1;
            return;
        }
        int m = (l + r) >> 1;
        build(v * 2, l, m);
        build(v * 2 + 1, m + 1, r);
        node[v] = node[v * 2] + node[v * 2 + 1];
    }

    void update(int v, int l, int r, int pos, int val){
        if(r < pos || l > pos) return;
        if(l == r && pos == r){
            node[v] += val;
            return;
        }
        int m = (l + r) >> 1;
        update(v * 2, l, m, pos, val);
        update(v * 2 + 1, m + 1, r, pos, val);
        node[v] = node[v * 2] + node[v * 2 + 1];
    }

    int search(int v, int l, int r, int val){
        if(l == r) return l ;
        int m = (l + r) >> 1;
        if(node[v * 2] >= val)
            return search(v * 2, l, m, val);
        else return search(v * 2 + 1, m + 1, r, val - node[v * 2]);
    }
};


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

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    SegmentTree t(n); t.build(1, 1, n);
    for(int i = 1; i <= n; i++){
        int p = t.search(1, 1, n, a[i] + 1);
        ans[p] = i;
        t.update(1, 1, n, p, -1);
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
}

:::

## [XOR mảng con](https://marisaoj.com/problem/362)
- Hãy thử xử lí với trường hợp $A_i,x = 0/1$
- Ví dụ với mảng $\{0, 1, 1, 0, 0, 1\}$, hãy tìm cách tính tổng XOR của toàn bộ các đoạn con.

Cách tính:
:::spoiler
Với $P$ là mảng tiền tố XOR: $\{0, 0, 1, 0, 0, 0, 1\}$ (thêm một số $0$ ở đầu). Đáp án chính là số lượng số $0$ nhân với số lượng số $1$ = $10$.
:::
- Khi biết cách làm với giá trị $0/1$, hãy tạo ra $\log n$ cây Segment Tree để, xử lí mỗi bit riêng biệt.
**Các bài liên quan đến XOR có rất nhiều khả năng xử lí các bit riêng biệt.**

Code
:::spoiler

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1e5 + 5;

int n, q;
int a[maxn];
int pre[maxn][31];

struct Node{
    int odd, even, lazy;
    Node operator + (const Node &a){
        return {a.odd + odd, a.even + even};
    }
};

struct SegmentTree{
    vector<Node> node;
    SegmentTree(int n): node(n * 8 + 1){}
    
    void push(int v){
        if(node[v].lazy){
            swap(node[v * 2].even, node[v * 2].odd);
            swap(node[v * 2 + 1].even, node[v * 2 + 1].odd);
            node[v * 2].lazy ^= 1;
            node[v * 2 + 1].lazy ^= 1;
            node[v].lazy = 0;
        }
    }

    void build(int v, int l, int r, int pos, int val){
        if(r < pos || l > pos) return;
        if(pos == l && l == r){
            node[v].even = (val % 2 == 0);
            node[v].odd = val % 2;
            return;
        }
        int m = (l + r) >> 1;
        build(v * 2, l, m, pos, val);
        build(v * 2 + 1, m + 1, r, pos, val);
        node[v] = node[v * 2] + node[v * 2 + 1];
    }

    void update(int v, int l, int r, int tl, int tr){
        if(r < tl || l > tr) return;
        if(tl <= l && r <= tr){
            swap(node[v].odd, node[v].even);
            node[v].lazy ^= 1;
            return;
        }
        push(v);
        int m = (l + r) >> 1;
        update(v * 2, l, m, tl, tr);
        update(v * 2 + 1, m + 1, r, tl, tr);
        node[v] = node[v * 2] + node[v * 2 + 1];
    }

    Node get(int v, int l, int r, int tl, int tr){
        if(r < tl || l > tr) return Node{0, 0};
        else if(tl <= l && r <= tr) return node[v];
        push(v);
        int m = (l + r) >> 1;
        return get(v * 2, l, m, tl, tr) + get(v * 2 + 1, m + 1, r, tl, tr);
    }
};

vector<SegmentTree> d(31, SegmentTree(maxn));

void build(int x, int idx){
    int pos = 0;
    for(int i = 0; i < 31; i++) pre[idx][i] = pre[idx - 1][i];
    while(x){
       // cout << (x & 1) << ' ' << x << ' ' << idx << endl;
        pre[idx][pos] += x & 1;
       // cout << pos << ' ' << idx << ' ' << pre[idx][pos] << endl;
        x >>= 1;
        pos++;
    }
}

void modify(int x, int i){
  //  cout << "mod " << x << endl;
    int pos = 0;
    while(x){
        Node t = d[pos].get(1, 0, n, i, i);
        bool old = t.odd;
       // cout << pos << ' '<< old << ' ' << (x & 1) << endl;
        if((x & 1)) d[pos].update(1, 0, n, i, n);
        x >>= 1;
        pos++;
    }
}

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

    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i], build(a[i], i);

    for(int i = 0; i < 31; i++)
        for(int j = 0; j <= n; j++)
            d[i].build(1, 0, n, j, pre[j][i]);//, cout << j << ' ' << i << ' ' << pre[j][i] << endl;

    while(q--){
        int t, a, b;
        cin >> t >> a >> b;
        if(t == 1){
            modify(b ^ ::a[a], a);
            ::a[a] = b;
        }else{
            // for(int i = 1; i <= n; i++){
            //     cout << ::a[i] << ' ';
            // }
            // cout << endl;
            Node ans;
            long long int qans = 0;
            for(int i = 0; i < 31; i++){
                ans = d[i].get(1, 0, n, a - 1, b);
               // cout << i << ' '<< ans.odd << ' ' << ans.even << endl;
                qans += (1 << i) * (long long)ans.odd * (long long)ans.even;
            }
            cout << qans << '\n';
        }
    }
}

:::

## [Radio](https://marisaoj.com/problem/365)
- $dp_i$ là thời gian nhỏ nhất để truyền tín hiệu đến radar $i$.
- Có một cây segtri, với vị trí $v$ là $dp_v$.
- Để tính được $dp_i$, ta có thể query min trên segtri từ $l_1$ đến $r_1$, nhưng như thế có thể query nhầm vào các radar không thể truyền đến $i$. Nghĩa là radar đó có $l_2$, $r_2$ mà $i < l_2$ hoặc $r_2 < i$.
- Ta xử lí bằng cách, khi tính đến $dp_i$, các radar $v$ có $l_2$ bằng $i$ thì ta cập nhật $dp_v$ vào segtri, khi tính đến $dp_i$ mà $v$ có $r_2+1$ bằng $i$ thì xóa khỏi segtri. Khi đó luôn đảm bảo các radar trong segtri có $l_2 \le i \le r_2$.

Code
:::spoiler

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1e5 + 5;

int n, dp[maxn], val[maxn];
vector<int> add[maxn], del[maxn];

struct SegmentTree{
    vector<int> node;
    SegmentTree(int n): node(4 * n + 69){
        build(1, 1, n);
    }

    void build(int v, int l, int r){
        node[v] = inf64;
        if(l == r){
            return;
        }
        int m = (l + r) >> 1;
        build(v << 1, l, m);
        build(v << 1 | 1, m + 1, r);
    }

    void update(int v, int l, int r, int pos, int val){
        if(r < pos || l > pos) return;
        if(l == r && pos == l){
            node[v] = val;
            return;
        }
        int m = (l + r) >> 1;
        update(v * 2, l, m, pos, val);
        update(v * 2 + 1, m + 1, r, pos, val);
        node[v] = min(node[v * 2], node[v * 2 + 1]);
    }

    int get(int v, int l, int r, int tl, int tr){
        if(r < tl || l > tr) return inf64;
        if(tl <= l && r <= tr) return node[v];
        int m = (l + r) >> 1;
        return min(get(v * 2, l, m, tl, tr), get(v * 2 + 1, m + 1, r, tl, tr));
    }  
};

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

    cin >> n;
    
    SegmentTree d(n);
    setinf(dp);
    dp[1] = 0;

    for(int i = 1; i <= n; i++){
        int t, l1, r1, l2, r2;
        cin >> t >> l1 >> r1 >> l2 >> r2; val[i] = t;
		assert(t);
		assert(l1);
		assert(r1);
		assert(l2);
		assert(r2);
        add[max(i + 1, l2)].push_back(i);
        del[r2 + 1].push_back(i);
        for(int &v : add[i]){
           // cout << "add " << v << ' ' << i << ' ' << dp[v] - v + val[t] << endl;
            d.update(1, 1, n, v, dp[v] - v + val[v]);
        }
        for(int &v : del[i]){
            d.update(1, 1, n, v, inf64);
        }
        if(i != 1){
            dp[i] = d.get(1, 1, n, l1, r1) + t + i;
            
        }
        ////d.update(1, 1, n, i, dp[i] - i + t);
    }

    for(int i = 2; i <= n; i++)
        if(dp[i] <  inf64 / 2)
        cout << dp[i] << ' ';
        else cout << -1 << ' ';
}

:::