Glad You Came hdu-6356（ST表 || 线段树）

第一种用线段树，用两颗数维护区间最大值和区间的最小值，然后更新的时候如果我目前区间内的最大值比我得到的v小，那么我就把这个区间修改成v，如果我的最小值比v大，那么v就是没有用的，直接跳过，然后这样每次更新[l, r]内的最大最小值，查询的时候返回每个位置的最大值，就可以求出答案

线段树：

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

typedef unsigned int ui;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = 1e5;

const int maxm = 2e5+;

const int mod = <<;

const double eps = 1e-;

using namespace std;

int n, m;

int T, tol;

ui X, Y, Z;

int mx[maxn << ];

int mn[maxn << ];

int lazy[maxn << ];

ui RNG61() {

    X = X ^ (X<<);

    X = X ^ (X>>);

    X = X ^ (X<<);

    X = X ^ (X>>);

    ll W = X ^ (Y ^ Z);

    X = Y;

    Y = Z;

    Z = W;

    return Z;

}

void init() {

    memset(mx, , sizeof mx);

    memset(mn, , sizeof mn);

    memset(lazy, , sizeof lazy);

}

void pushup(int root) {

    mx[root] = max(mx[root << ], mx[root <<  | ]);

    mn[root] = min(mn[root << ], mn[root <<  | ]);

}

void pushdown(int root) {

    if(lazy[root]) {

        mx[root << ] = mx[root <<  | ] = lazy[root];

        mn[root << ] = mn[root <<  | ] = lazy[root];

        lazy[root << ] = lazy[root <<  | ] = lazy[root];

        lazy[root] = ;

    }

}

void update(int left, int right, int prel, int prer, int val, int root) {

    if(prel <= left && right <= prer) {

        if(mx[root] < val) {

            mx[root] = mn[root] = val;

            lazy[root] = val;

            return ;

        }

        if(mn[root] > val)    return ;

    }

    if(mn[root] > val)    return ;

    pushdown(root);

    int mid = (left + right) >> ;

    if(prel <= mid)    update(left, mid, prel, prer, val, root << );

    if(prer > mid)    update(mid+, right, prel, prer, val, root <<  | );

    pushup(root);

}

int query(int left, int right, int pos, int root) {

    if(left == right) {

        return mx[root];

    }

    pushdown(root);

    int mid = (left + right) >> ;

    if(pos <= mid)    return query(left, mid, pos, root << );

    else            return query(mid+, right, pos, root <<  | );

}

int main() {

    scanf("%d", &T);

    while(T--) {

        scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z);

        init();

        for(int i=; i<=m; i++) {

            ui f1 = RNG61();

            ui f2 = RNG61();

            ui f3 = RNG61();

            int l = min(f1%n+, f2%n+);

            int r = max(f1%n+, f2%n+);

            int v = f3 % mod;

            update(, n, l, r, v, );

        }

        ll ans = ;

        for(int i=; i<=n; i++) {

            ans ^= (1ll * i * query(, n, i, ));

        }

        printf("%I64d\n", ans);

    }

    return ;

}

原本的RMQ是得到每个位置的点值，然后一步一步更新成区间的最值，用

st[i][j] = max(st[i][j-1]，st[i+(1<<(j-1))][j-1])

然后这里是先得到区间最值，然后往回更新到每个位置的点的最值，所以就是两个

st[i][j-1] = max(st[i][j-1], st[i][j])

st[i+(1<<(j-1))][j-1] = max(st[i+(1<<(j-1))][j-1], st[i][j])

倒着更新

然后题目里面数据很大，所以同样的log(r-l+1)/log(2.0)可能计算很多遍，可以把log(i)/log(2.0)打表出来，可以快一半的时间

ST表：

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

typedef unsigned int ui;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = 1e5;

const int maxm = 2e5+;

const int mod = <<;

const double eps = 1e-;

using namespace std;

int n, m;

int T, tol;

ui X, Y, Z;

int st[maxm][];

int lg[maxn];

ui RNG61() {

    X = X ^ (X<<);

    X = X ^ (X>>);

    X = X ^ (X<<);

    X = X ^ (X>>);

    ll W = X ^ (Y ^ Z);

    X = Y;

    Y = Z;

    Z = W;

    return Z;

}

void init() {

    memset(st, , sizeof st);

}

void handle() {

    lg[] = -;

    for(int i=; i<maxn; i++)    lg[i] = log(i) / log(2.0);

}

int main() {

    handle();

    scanf("%d", &T);

    while(T--) {

        scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z);

        init();

        for(int i=; i<=m; i++) {

            ui f1 = RNG61();

            ui f2 = RNG61();

            ui f3 = RNG61();

            int l = min(f1%n+, f2%n+);

            int r = max(f1%n+, f2%n+);

            int v = f3 % mod;

            int k = lg[r-l+];

            st[l][k] = max(st[l][k], v);

            st[r-(<<k)+][k] = max(st[r-(<<k)+][k], v);

        }

        int len = log(n) / log(2.0);

        for(int j=len; j>=; j--) {

            for(int i=; i<=n; i++) {

                st[i][j-] = max(st[i][j-], st[i][j]);

                st[i+(<<(j-))][j-] = max(st[i+(<<(j-))][j-], st[i][j]);

            }

        }

        ll ans = ;

        for(int i=; i<=n; i++)        ans = ans ^ (1ll * i * st[i][]);

        printf("%I64d\n", ans);

    }

    return ;

}

巴特西

Glad You Came hdu-6356（ST表 || 线段树）

最新文章

热门文章