[Nowcoder283J] RMQ (线段树)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://ac.nowcoder.com/acm/contest/283/J

小姐姐想要一种数据结构，支持如下操作：

对于一个整数数组：

\1. 给定L和R，输出[L,R]中元素的和

\2. 给定L，R和X，将[L,R]中每个元素与X进行按位或运算

\3. 数组索引从1开始

按位或在C\C++、Java、Python中为’|’运算符

难点在于如何处理或操作。

做过异或线段树的题，这个或自然会想到拆位处理，针对每一位建一棵线段树，如果或的数字的某一位为1时，则这一位（假设是第$i$位）在区间$[l,r]$对于答案（sum）的贡献为$2^i\times(r-l+1)$.

认真写一下lazy标记的处理就好，蛮好写。注意线段树$sum[rt][i]$的顺序，惨遭卡常。。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
inline bool scan_d(int &num) {
  char in;bool IsN=false;
  in=getchar();
  if(in==EOF) return false;
  while(in!='-'&&(in<'0'||in>'9')) in=getchar();
  if(in=='-'){ IsN=true;num=0;}
  else num=in-'0';
  while(in=getchar(),in>='0'&&in<='9'){
    num*=10,num+=in-'0';
  }
  if(IsN) num=-num;
  return true;
}

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int maxn = 200100;
int sum[maxn<<2][20];
int a[maxn];
int add[maxn<<2][20];
int n, q;

void pushUP(int rt, int i) {
  sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][i];
}

void pushDOWN(int rt, int l, int r, int i) {
  if(add[rt][i]) {
    add[rt<<1][i] |= add[rt][i];
    add[rt<<1|1][i] |= add[rt][i];
    int m = (l + r) >> 1;
    sum[rt<<1][i] = m - l + 1;
    sum[rt<<1|1][i] = r - m;
  }
}

void build(int l, int r, int rt) {
  if(l == r) {
    int i = 0;
    while(a[l]) {
      if(a[l] & 1) sum[rt][i] = 1;
      i++;
      a[l] >>= 1;
    }
    return;
  }
  int m = (l + r) >> 1;
  build(lson);
  build(rson);
  for(int i = 0; i < 20; i++) {
    sum[rt][i] = sum[rt<<1][i] + sum[rt<<1|1][i];
  }
}

void update(int L, int R, int c, int l, int r, int rt, int i) {
  if(L <= l && r <= R) {
    add[rt][i] = 1;
    sum[rt][i] = (r - l + 1);
    return;
  }
  pushDOWN(rt, l, r, i);
  int m = (l + r) >> 1;
  if(L <= m) update(L, R, c, lson, i);
  if(R > m) update(L, R, c, rson, i);
  pushUP(rt, i);
}

LL query(int L, int R, int l, int r, int rt, int i) {
  if(L <= l && r <= R) {
    return (1LL << i) * sum[rt][i];
  }
  pushDOWN(rt, l, r, i);
  int m = (l + r) >> 1;
  LL ret = 0;
  if(L <= m) 
    ret += query(L, R, lson, i);
  if(m < R) 
    ret += query(L, R, rson, i);
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  int a, b, c;
  char cmd[5];
  scan_d(n);
  scan_d(q);
  for(int i = 1; i <= n; i++) {
    scan_d(::a[i]);
  }
  build(1, n, 1);
  while(q--) {
    scanf("%s", cmd);
    if(cmd[0] == 'S') {
      scan_d(a);
      scan_d(b);
      LL ret = 0;
      for(int i = 0; i < 20; i++) {
        ret += query(a, b, 1, n, 1, i);
      }
      printf("%lld\n", ret);
    }
    else {
      scan_d(a); scan_d(b); scan_d(c);
      int i = 0;
      while(c) {
        if(c & 1) update(a, b, 1, 1, n, 1, i);
        i++;
        c >>= 1;
      }
    }
  }
  return 0;
}