hdu 6356 反向ST表/线段树剪枝

(Updated: )
(3 mins to read)

给出m次区间取max的操作(l,r,v)，问你最后数组的状态(初始均为0)，操作通过随机的方式给出。

区间取max，可以用sgbt来做，不过注意到本题操作随机(既然是随机给出的，必然有它的用意)，所以可以用剪枝的方式：维护区间最大值和最小值，当前最大值比v还小就是区间覆盖，最小值比v还大就直接reutrn。

此外还有一种反向ST表的操作，我们可以先得到高层ST表的状态，然后再从高到低递推出底层的状态即可。当然这种方式有很大的限制，感觉只适用于区间取最值，只有最后一次询问的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
using uint = uint32_t;
using ll = long long;
const int N = 1e5 + 5;
int n, m;
uint x, y, z, w;
uint rng61() {
  x = x^(x<<11);
  x = x^(x>>4);
  x = x^(x<<5);
  x = x^(x>>14);
  w = x^(y^z);
  x = y;
  y = z;
  z = w;
  return z;
}
inline void Max(int &x, int y) { if(x<y) x = y; }
int st[N][18];
void solve() {
  scanf("%d%d%u%u%u", &n, &m, &x, &y, &z);
  for(int i=1; i<=n; i++)
    for(int j=0; i+(1<<j)-1<=n; j++) st[i][j] = 0;
  for(int i=1; i<=m; i++) {
    uint f0 = rng61(), f1 = rng61(), f2 = rng61();
    int l = min(f0%n+1, f1%n+1);
    int r = max(f0%n+1, f1%n+1);
    int v = f2%(1<<30);
    int k = 31 - __builtin_clz(r-l+1);
    Max(st[l][k], v);
    Max(st[r-(1<<k)+1][k], v);
  }
  for(int j=16; j>=0; j--)
    for(int i=1; i+(1<<(j+1))-1<=n; i++) {
      Max(st[i][j], st[i][j+1]);
      Max(st[i+(1<<j)][j], st[i][j+1]);
    }
  ll ans = 0;
  for(int i=1; i<=n; i++) ans ^= 1ll*i*st[i][0];
  printf("%lld\n", ans);
}
int main() {
  int _; scanf("%d", &_);
  while(_--) solve();
  return 0;
}