St table, weighted and search set

RMQ

Range Minimunm/Maximum Query

 f[i][j] :    With i As a starting point     The length is     Maximum value of interval / minimum value

Finally, I use 2 Segment interval to piece together into an interval we want to query , There will be interval repetition , So use ST The precondition of the table is the requirement , The interval of repeated calculation will not affect the result , For example, please ：

Maximum 、 minimum value 、 & operation   、| operation 、    gcd

and , The interval is preprocessed   O(nlogn)  , Inquire about O(1)   ,    Therefore, the interval cannot be modified .

Using the segment tree, you can also operate on the interval , And it can maintain more complex information , But if you just make a query , Efficiency is not ST Table high .

// problem :  

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 1e6 + 5;
typedef unsigned int ui;
unsigned int A, B, C, n, q, f[N][22], a[N];
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}

int main(){
    scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        a[i] = rng61();
        f[i][0] = a[i];
    }
    for (int j = 1; j <= 20; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    ui ans = 0;
    for (int i = 1; i <= q; i++) {
        unsigned int l = rng61() % n + 1, r = rng61() % n + 1;
        if (l > r) swap(l, r);
        // int x = log2(r - l + 1);
        int x = __lg(r - l + 1);

        ans ^= max(f[l][x], f[r - (1 <<x) + 1][x]);
    }
    printf("%u\n", ans);
}

Take the right and check the collection

 

// problem :  

#include <bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 2E5 + 5;
int f[N];
ll w[N];
int n, q;
int find(int x) {
    if(f[x] == x) return x;
    int p = f[x];
    find(p); // q
    /*
     old ：       w[x] : a[x] - a[p]
     f[p] = q    w[p] : a[p] - a[q]
 new  f[x] = q    w[x] : a[x] - a[q]    The updated w[x]
    
    w[x] = a[x] - a[q] = a[x] - a[p] + a[p] - a[q]; 
    */
    w[x] = w[x] + w[p];
    return f[x] = f[p];
}
int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
        w[i] = 0;
    }
    ll t = 0;
    for (int i = 1; i <= q; ++i) {
        int ty, l, r;
        scanf("%d %d %d", &ty, &l, &r);
        l = (l + t) % n + 1;
        r = (r + t) % n + 1;
        if(ty == 2) {
            if(find(l) != find(r)) continue;
            printf("%lld\n", w[l] - w[r]);
            t = abs(w[l] - w[r]);
        } else {
            int x; scanf("%d", &x);
            if(find(l) == find(r)) continue;
            w[f[l]] = x - w[l] + w[r];
            f[f[l]] = f[r];
            /*
            w[f[l]] = a[f[l]] - a[f[r]]
            a[l] - a[r] = x
            w[l] = a[l] - a[f[l]],  w[r] = a[r] - a[f[r]]
            ==> w[f[l]] = a[l] - w[l] - (a[r] - w[r])
            */
        }
    }
    

    return 0;
}