HDU 6356 Glad You Came (RMQ)

题目链接 用给定方法生成区间[l,r]和一个数v，每次将[l,r]中小于v的数变为v，最后求每个位置上i*ai的异或和。

将区间中小于v的数变为v，实质上就是需要维护并修改区间最大值。区间最大值可以用线段树实现，也可以用RMQ倍增来实现。

对于一个待处理的区间[l,r]，考虑，这样就将[l,r]拆成了两个可重叠的，长度均为1<<tmp的子区间。dp[i][j]表示从i开始长度为1<<j的子区间的最大值，对于这两个子区间分别有dp[l][tmp],dp[r-1<<tmp+1][tmp]=max(dp[][],v)。

然后在向下维护最大值的时候就是一个ST表的逆操作，

dp[i][j-1] = max(dp[i][j-1] , dp[i][j])，dp[i+1<<(j-1)][j-1] = max( dp[i+1<<(j-1)][j-1] , dp[i][j])。

RMQ解法：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
typedef unsigned int ul;
const int maxn = 100005;
typedef long long ll;
const ll mod = (1LL << 30);int kase, m, n;
ll dp[25][maxn], ans, v;
int Log[maxn], mi[25];
int l, r;ul RNG61(ul &x, ul &y, ul &z)
{x = x ^ (x << 11);x = x ^ (x >> 4);x = x ^ (x << 5);x = x ^ (x >> 14);ul w = x ^ (y ^ z);x = y;y = z;z = w;return z;
}void init()
{mi[0] = 1;for(int i = 1;i <= 21;i++)mi[i] = mi[i - 1]*2;for(int i = 2;i <= 100000;i++)Log[i] = Log[i >> 1] + 1;
}int main()
{init();scanf("%d", &kase);while(kase--){ul x, y, z;memset(dp, 0, sizeof(dp));scanf("%d%d%u%u%u", &n, &m, &x, &y, &z);for(int i = 0;i < m;i++){ul ans1 = RNG61(x, y, z), ans2 = RNG61(x, y, z), ans3 = RNG61(x, y, z);l = (int)min((ans1 % n) + 1, (ans2 % n) + 1);r = (int)max((ans1 % n) + 1, (ans2 % n) + 1);v = 1LL*((ans3 + mod) % mod);int tmp = Log[r - l + 1];int cnt = r - mi[tmp] + 1;dp[tmp][l] = max(dp[tmp][l], v);dp[tmp][cnt] = max(dp[tmp][cnt], v);}for(int i = 19;i > 0;i--){for(int j = 1;j + mi[i] - 1 <= n;j++){int tmp = j + mi[i - 1];dp[i - 1][j] = max(dp[i - 1][j], dp[i][j]);dp[i - 1][tmp] = max(dp[i - 1][tmp], dp[i][j]);}}ans = 0;for(int i = 1;i <= n;i++)ans ^= (i*dp[0][i]);printf("%lld\n", ans);}return 0;
}

线段树解法：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
typedef unsigned int ul;
const int maxn = 100005;
typedef long long ll;
const ll mod = pow(2, 30);int kase;
ll ans;
ll tree[maxn<<2], lazy[maxn<<2];unsigned int RNG61(unsigned int &x, unsigned int &y, unsigned int &z)
{x = x^(x<<11);x = x^(x>>4);x = x^(x<<5);x = x^(x>>14);unsigned int w = x^(y^z);x = y;y = z;z = w;return z;
}void pushdown(int root)
{/*if(lazy[root] != 0){lazy[root*2] = max(lazy[root], lazy[root*2]);lazy[root*2 + 1] = max(lazy[root], lazy[root*2 + 1]);tree[root*2] = max(tree[root*2], lazy[root]);tree[root*2 + 1] = max(tree[root*2 + 1], lazy[root]);lazy[root] = 0;}*/tree[root*2] = max(tree[root*2], tree[root]);tree[root*2 + 1] = max(tree[root*2 + 1], tree[root]);
}void update(int root, int l ,int r, int aiml, int aimr, ll w)
{if(l > aimr || r < aiml) return;if(tree[root] > w) return;if(l >= aiml && r <= aimr){tree[root] = max(tree[root], w);lazy[root] = max(lazy[root], w);return;}pushdown(root);int mid = (l + r) >> 1;update(root*2, l, mid, aiml, aimr, w);update(root*2 + 1, mid + 1, r, aiml, aimr, w);//tree[root] = max(tree[root*2], tree[root*2 + 1]);
}void query(int root, int l, int r)
{if(l == r){ans ^= (l*tree[root]);return;}pushdown(root);int mid = (l + r) >> 1;query(root*2, l, mid);query(root*2 + 1, mid + 1, r);
}int main()
{scanf("%d", &kase);while(kase--){ul x, y, z, l, r, v, n;int m;scanf("%u%d%u%u%u", &n, &m, &x, &y, &z);memset(tree, 0, sizeof(tree));memset(lazy, 0, sizeof(lazy));for(int i = 0;i < m;i++){ul ans1 = RNG61(x, y, z), ans2 = RNG61(x, y, z), ans3 = RNG61(x, y, z);l = min((ans1 % n) + 1, (ans2 % n) + 1);r = max((ans1 % n) + 1, (ans2 % n) + 1);v = (ans3 + mod) % mod;update(1, 1, n, l, r, v);}ans = 0;query(1, 1, n);printf("%lld\n", ans);}return 0;
}