（线段）树学是怎样炼成的

17 分钟阅读更新于 2026-08-295739 字世界式

本文所讲的线段树题，仅包括思路重点在线段树的题，而不是用线段树优化什么。

线段树只是一种武器，而扫描线是思想。只有同时有了武器和思想，才能有最大的力量。

因此这里例题被分哪边，实际上取决于重点偏向，作为武器的线段树还是作为思想的扫描线，并不指完全不需要用到另一方的。

本文是写给已经学过线段树和扫描线的，相信看完后能对线段树和扫描线有不少新认识。

线段树

标记信息的设计

概述

本节参考：

https://www.luogu.me/article/rqmfqvmu

https://www.cnblogs.com/Meatherm/p/17925813.html#:~

线段树基本原则（信息&标记）：

信息+信息->信息（区间合并pushup）
标记+标记->标记（tag合并）
标记+信息->信息（tag可对信息作用pushdown）

可以从维护信息出发，推出其他信息和标记。

例：小白

单点加

区间查最大子段和

由于查询，显然信息要维护最大子段和，于是考虑第一点。

一个大区间显然是由左右小区间合并上了，于是为了合并它，就需要再维护前缀最大值和后缀最大值。

由于是单点修改，并不需要标记。

以上可以写成模板，不同的线段树只有三个函数有差别。

1
struct Tag { //标记
2
  Tag(){}
3
  inline friend Tag operator + (Tag l , Tag r){
4
    //信息合并（相当于pushup）
5
  }
6
  inline void operator += (Tag t){ (*this) = (*this) + t; }
7
}tag[400005];
8

9
struct Seg { //信息
10
  inline friend Seg operator + (Seg ls , Seg rs){
11
    //标记作用标记
12
  }
13
  inline void operator += (Tag t){
14
    //标记作用信息
15
  }
16
}tr[400005];
17

18
inline void pushdown(int p){
19
  if(){ //判断标记非空
20
    tr[p << 1] += tag[p]; tr[p << 1 | 1] += tag[p];
21
    tag[p << 1] += tag[p]; tag[p << 1 | 1] += tag[p];
22
    tag[p] = Tag();
23
  }
24
}
25

26
void init(int p , int l , int r){
27
  if(l == r){ return ; }
28
  int mid = (l + r) >> 1;
29
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
30
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
31
}
32

33
void upd(int p , int l , int r , int x , int y , Tag k){
34
  if(l > y || r < x) return ;
35
  if(l >= x && r <= y){ tr[p] += k; tag[p] += k; return ; }
36
  int mid = (l + r) >> 1;
37
  pushdown(p);
38
  upd(p << 1 , l , mid , x , y , k);
39
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
40
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
41
}
42

43
Seg query(int p , int l , int r , int x , int y){
44
  if(l >= x && r <= y) return tr[p];
45
  int mid = (l + r) >> 1;
46
  pushdown(p);
47
  if(y <= mid) return query(p << 1 , l , mid , x , y);
48
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
49
  return (
50
    query(p << 1 , l , mid , x , y) +
51
    query(p << 1 | 1 , mid + 1 , r , x , y)
52
  );
53
}

特殊维护

比如线段树维护矩阵，维护并查集，这边以这道例题为例。

P3300 [SDOI2013] 城市规划

题意：https://www.luogu.com.cn/discuss/764108。原题描述的太烂了。。

因为是连通性，所以我们直接用线段树维护并查集。这个并查集有 $2m$ 个节点，代表最上面 $m$ 个节点和最下面 $m$ 个节点。并查集中再维护一个 $b$ ，表示这个连通块是否存在建筑。合并时把两个并查集暴力合并成大小为 $4m$ 的并查集，然后去掉中间的节点，留下 $2m$ 的并查集即可。

没有什么思维含量，喜欢写大魔女的可以尝试实现。相似题目：CF811E、P4121。

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5

6
int n , m , m2; char s[100005][8];
7

8
struct Chm { short fa; bool b; };
9

10
int find(Chm dsu[] , short x){
11
  if(dsu[x].fa == x) return x;
12
  int f = find(dsu , dsu[x].fa);
13
  dsu[f].b |= dsu[x].b;
14
  return dsu[x].fa = f;
15
}
16
inline int fa_merge(Chm dsu[] , short x , short y){
17
  short xx = find(dsu , x) , yy = find(dsu , y);
18
  if(xx == yy) return 0;
19
  dsu[xx].fa = yy; dsu[yy].b |= dsu[xx].b;
20
  return 1;
21
}
22

23
struct Seg {
24
  Chm d[12]; int ans;
25
}tr[400005];
26

27
Chm qwq[24]; short tmp[24];
28
inline Seg pushup(Seg ls , Seg rs , int mid){
29
  Seg ret; ret.ans = ls.ans + rs.ans;
30
  for(int i = 0;i < m2;i++){
31
    qwq[i] = ls.d[i]; qwq[i + m2] = rs.d[i];
32
    qwq[i + m2].fa += m2;
33
  }
34
  for(int i = 0;i < m;i++) if(s[mid][i] != '.' && s[mid + 1][i] != '.')
35
    if(s[mid][i] != '-' && s[mid + 1][i] != '-'){
36
      bool zbj = qwq[find(qwq , i + m)].b && qwq[find(qwq , i + m2)].b;
37
      bool lcj = fa_merge(qwq , i + m , i + m2);
38
      ret.ans -= (lcj && zbj);
39
    }
40
  for(int i = 0;i < m2;i++) ret.d[i].fa = i , ret.d[i].b = 0;
41
  for(int i = 0 , _ = (m2 << 1);i < _;i++) tmp[i] = 1145;
42
  for(int i = 0;i < m2;i++){
43
    short x = find(qwq , i < m? i : i + m2);
44
    ret.d[find(ret.d , i)].b |= qwq[x].b;
45
    if(tmp[x] < 1145) fa_merge(ret.d , i , tmp[x]);
46
    tmp[x] = i;
47
  }
48
  return ret;
49
}
50

51
void init(int p , int l , int r){
52
  if(l == r){
53
    tr[p].ans = 0;
54
    for(int i = 0;i < m;i++){
55
      tr[p].d[i].fa = tr[p].d[i + m].fa = i;
56
      tr[p].d[i].b = tr[p].d[i + m].b = 0;
57
      if(s[l][i] == 'O')
58
        tr[p].d[i].b = tr[p].d[i + m].b = 1;
59
    }
60
    for(int i = 1;i < m;i++) if(s[l][i - 1] != '.' && s[l][i] != '.')
61
      if(s[l][i - 1] != '|' && s[l][i] != '|') fa_merge(tr[p].d , i - 1 , i);
62
    for(int i = 0;i < m2;i++) if(tr[p].d[i].fa == i && tr[p].d[i].b)
63
      tr[p].ans++;
64
    return ;
65
  }
66
  int mid = (l + r) >> 1;
67
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
68
  tr[p] = pushup(tr[p << 1] , tr[p << 1 | 1] , mid);
69
}
70

71
void upd(int p , int l , int r , int x){
72
  if(l > x || r < x) return ;
73
  if(l == r){
74
    tr[p].ans = 0;
75
    for(int i = 0;i < m;i++){
76
      tr[p].d[i].fa = tr[p].d[i + m].fa = i;
77
      tr[p].d[i].b = tr[p].d[i + m].b = 0;
78
      if(s[l][i] == 'O')
79
        tr[p].d[i].b = tr[p].d[i + m].b = 1;
80
    }
81
    for(int i = 1;i < m;i++) if(s[l][i - 1] != '.' && s[l][i] != '.')
82
      if(s[l][i - 1] != '|' && s[l][i] != '|') fa_merge(tr[p].d , i - 1 , i);
83
    for(int i = 0;i < m2;i++) if(tr[p].d[i].fa == i && tr[p].d[i].b)
84
      tr[p].ans++;
85
    return ;
86
  }
87
  int mid = (l + r) >> 1;
88
  upd(p << 1 , l , mid , x); upd(p << 1 | 1 , mid + 1 , r , x);
89
  tr[p] = pushup(tr[p << 1] , tr[p << 1 | 1] , mid);
90
}
91

92
Seg query(int p , int l , int r , int x , int y){
93
  if(l >= x && r <= y) return tr[p];
94
  int mid = (l + r) >> 1;
95
  if(y <= mid) return query(p << 1 , l , mid , x , y);
96
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
97
  return pushup(
98
    query(p << 1 , l , mid , x , y) ,
99
    query(p << 1 | 1 , mid + 1 , r , x , y) ,
100
    mid
101
  );
102
}
103

104
int main(void){
105
  scanf("%d%d" , &n , &m); m2 = (m << 1);
106
  for(int i = 1;i <= n;i++) scanf("%s" , s[i]);
107
  init(1 , 1 , n);
108
  int q; scanf("%d" , &q);
109
  while(q--){
110
    char op[2]; scanf("%s" , op);
111
    if(op[0] == 'C'){
112
      int i , j; scanf("%d%d%s" , &i , &j , op);
113
      s[i][j - 1] = op[0];
114
      upd(1 , 1 , n , i);
115
    }
116
    else if(op[0] == 'Q'){
117
      int l , r; scanf("%d%d" , &l , &r);
118
      printf("%d\n" , query(1 , 1 , n , l , r).ans);
119
    }
120
  }
121
}

P7497 四方喝彩 & T490354 ZRZ之以太战线问题

这类问题，可以考虑维护与答案无关的标记来辅助维护答案。

比如第一道例题，维护上锁，并且这个标记是不下传的。

比如 =7 大佬出的第二题，可以多维护一个区间最小值。

这里附上第一题的代码，第二题就不给了，因为没过。这里代码的写法，是符合前面给的模板的。可以学习参考一下，应该比大部分题解来得好写，代码也短。

1
#include <cstdio>
2
#include <algorithm>
3
#include <vector>
4
using namespace std;
5

6
const int MOD = 1e9 + 7;
7

8
int n , m , a[200005];
9
int nw;
10

11
struct Tag {
12
  int ad , mul;
13
  inline Tag(int _ = 0 , int __ = 1){ ad = _; mul = __; }
14
  inline friend Tag operator + (const Tag x , const Tag y) {
15
    return Tag( (1LL * x.ad * y.mul % MOD + y.ad) % MOD , 1LL * x.mul * y.mul % MOD );
16
  }
17
  inline void operator += (const Tag y) { (*this) = (*this) + y; }
18
}tg[800005];
19

20
struct Seg {
21
  int s , s2 , num , lock; //s答案，s2未锁
22
  inline friend Seg operator + (const Seg &ls , const Seg &rs){
23
    Seg ret;
24
    ret.s = (ls.s + rs.s) % MOD;
25
    ret.s2 = (ls.s2 + rs.s2) % MOD;
26
    ret.num = ls.num + rs.num;
27
    return ret;
28
  }
29
  inline void upd(const Tag &x , int le){
30
    if((s += MOD - s2) >= MOD) s -= MOD;
31
    s2 = 1LL * s2 * x.mul % MOD;
32
    if((s2 += 1LL * num * x.ad % MOD) >= MOD) s2 -= MOD;
33
    if((s += s2) >= MOD) s -= MOD;
34
  }
35
}tr[800005];
36

37
inline void pushdown(int p , int l , int r){
38
  if(tg[p].ad != 0 || tg[p].mul != 1){
39
    int mid = (l + r) >> 1;
40
    if(!tr[p << 1].lock){
41
      tg[p << 1] += tg[p];
42
      tr[p << 1].upd(tg[p] , mid - l + 1);
43
    }
44
    if(!tr[p << 1 | 1].lock){
45
      tg[p << 1 | 1] += tg[p];
46
      tr[p << 1 | 1].upd(tg[p] , r - mid);
47
    }
48
    tg[p] = Tag();
49
  }
50
}
51

52
void init(int p , int l , int r){
53
  if(l == r){
54
    tr[p].s = tr[p].s2 = a[l];
55
    tr[p].num = 1;
56
    return ;
57
  }
58
  int mid = (l + r) >> 1;
59
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
60
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
61
}
62

63
void upd(int p , int l , int r , int x , int y , Tag k){
64
  if(l > y || r < x || tr[p].lock) return ;
65
  if(l >= x && r <= y){ tg[p] += k; tr[p].upd(k , r - l + 1); return ; }
66
  int mid = (l + r) >> 1;
67
  pushdown(p , l , r);
68
  upd(p << 1 , l , mid , x , y , k); upd(p << 1 | 1 , mid + 1 , r , x , y , k);
69
  if(!tr[p].lock) tr[p] = tr[p << 1] + tr[p << 1 | 1];
70
}
71

72
void chm(int p , int l , int r , int x , int y , int k){
73
  if(l > y || r < x) return ;
74
  if(l >= x && r <= y){
75
    if(l != r) pushdown(p , l , r);
76
    if(k > 0 && tr[p].lock == 0){ //上锁
77
      tr[p].num = 0 , tr[p].s2 = 0;
78
      tr[p].lock++;
79
    }
80
    else if(k < 0 && tr[p].lock == 1){ //解锁
81
      if(l == r) tr[p].num = 1 , tr[p].s2 = tr[p].s;
82
      else tr[p] = tr[p << 1] + tr[p << 1 | 1];
83
      tr[p].lock = 0;
84
    }
85
    else tr[p].lock += k;
86
    return ;
87
  }
88
  int mid = (l + r) >> 1;
89
  pushdown(p , l , r);
90
  chm(p << 1 , l , mid , x , y , k); chm(p << 1 | 1 , mid + 1 , r , x , y , k);
91
  if(!tr[p].lock) tr[p] = tr[p << 1] + tr[p << 1 | 1];
92
}
93

94
Seg query(int p , int l , int r , int x , int y){
95
  if(l >= x && r <= y) return tr[p];
96
  int mid = (l + r) >> 1;
97
  pushdown(p , l , r);
98
  if(y <= mid) return query(p << 1 , l , mid , x , y);
99
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
100
  return query(p << 1 , l , mid , x , y) + query(p << 1 | 1 , mid + 1 , r , x , y);
101
}
102

103
vector <pair <int , int> > del[200005];
104

105
int main(void){
106
  scanf("%d%d" , &n , &m);
107
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
108
  init(1 , 1 , n);
109
  for(int i = 1;i <= m;i++){
110
    for(pair <int , int> k : del[i])
111
      chm(1 , 1 , n , k.first , k.second , -1);
112
    int op , l , r , x; scanf("%d%d%d" , &op , &l , &r);
113
    if(op <= 3) scanf("%d" , &x);
114
    if(op == 1) upd(1 , 1 , n , l , r , Tag(x , 1));
115
    if(op == 2) upd(1 , 1 , n , l , r , Tag(0 , x));
116
    if(op == 3){
117
      chm(1 , 1 , n , l , r , 1);
118
      if(i + x + 1 <= m) del[i + x + 1].push_back(make_pair(l , r));
119
    }
120
    if(op == 4)
121
      printf("%d\n" , query(1 , 1 , n , l , r).s);
122
  }
123
}

从扫描线到历史版本和

其实这边都是关于历史的。

一般的这种题，可以考虑将 l 做横轴，r 做纵轴，这样就成了矩形查询，区间修改，这玩意一般需要用到历史版本和。

我们很容易可以设计出信息和标记，但是问题就在于如何合并。

有的可能要考虑很多种情况，这里给出一种比较好用的方法：矩阵。

实际上可以把信息标记都放在矩阵上，那么就变成矩阵乘法。写出矩阵后，一般大多项都是固定没用的，于是可以把变的提出来，暴力解出转移，这样便有了标记的转移方式，这还可以尝试合并相同的值，大多数情况下这样跑出来的转移是和按照实际意义推的转移是相同的。

以下是暴力转移的代码（待办：用python写一个功能更完整的）：

1
#include <cstdio>
2
#include <algorithm>
3
#include <cstring>
4
using namespace std;
5

6
int n;
7
struct QWQ{ char a[105][105][10]; QWQ(){ memset(a , 0 , sizeof(a)); } }A , B;
8

9
inline void mul_max(QWQ x , QWQ y){ //M为负无穷
10
  for(int i = 1;i <= n;i++)
11
    for(int j = 1;j <= n;j++){
12
      int flag = 0;
13
      for(int k = n;k >= 1;k--)
14
        if(x.a[i][k][1] != 'M' && y.a[k][j][1] != 'M'){ flag = k; break; }
15
      if(!flag) continue;
16
      printf("(%d %d)=max(" , i , j);
17
      for(int k = 1;k <= n;k++){
18
        if(x.a[i][k][1] == 'M' || y.a[k][j][1] == 'M') continue;
19
        printf("%s+%s" , x.a[i][k] + 1 , y.a[k][j] + 1);
20
        if(k != flag) putchar(',');
21
      }
22
      putchar(')'); putchar('\n');
23
    }
24
}
25

26
inline void mul_(QWQ x , QWQ y){
27
  for(int i = 1;i <= n;i++)
28
    for(int j = 1;j <= n;j++){
29
      int flag = 0;
30
      for(int k = n;k >= 1;k--)
31
        if(x.a[i][k][1] != '0' && y.a[k][j][1] != '0'){ flag = k; break; }
32
      if(!flag) continue;
33
      printf("ret.k[1] = ");
34
      for(int k = 1;k <= n;k++){
35
        if(x.a[i][k][1] == '0' || y.a[k][j][1] == '0') continue;
36
        printf(" %s * %s" , x.a[i][k] + 1 , y.a[k][j] + 1);
37
        if(k != flag) printf(" +");
38
      }
39
      printf(";\n");
40
    }
41
}
42

43
int main(void){
44
  scanf("%d" , &n);
45
  for(int i = 1;i <= n;i++)
46
    for(int j = 1;j <= n;j++)
47
      scanf("%s" , A.a[i][j] + 1);
48
  for(int i = 1;i <= n;i++)
49
    for(int j = 1;j <= n;j++)
50
      scanf("%s" , B.a[i][j] + 1);
51
  mul_(A , B);
52
}

然后操作如果有涉及到 max 等的东西，可以考虑使用 $(\max,+)$ 矩阵，就是把矩乘的 $\times$ 改成 $+$ ， $+$ 改成 $\max$ 。

不过如果题目的操作过于复杂，其实没必要使用暴力转移找不变，可以直接矩乘，只是常数较大。

NOIP2022比赛

考虑第 $i$ 个点什么时候能对答案有贡献，显然，当且仅当区间包含 $i$ ，且满足 $l > L_i,r < R_i$ ，其中 $L_i$ 表示第 $i$ 个点左边第一个大于 $a_i$ 的位置， $R_i$ 同理。于是这样，每个点都变成一个矩形： $[L_i+1,i,i,R_i-1]$ 。

这样处理完，就有两个二维平面 $a,b$ ，答案就是 $[l,r,l,r]$ 矩形内 $a \times b$ 的和。

扫描线要维护：

矩形 $a$ 赋值。
矩形 $b$ 赋值。
求矩形 $a \times b$ 的值。

？？？赋值怎么测回。冯sir 说不需要撤回。看：

1
[3,5,2,6,1,4]  ->  [3,5,5,6,6,6]
2
  [5,2,6,1,4]  ->    [5,5,6,6,6]
3
    [2,6,1,4]  ->      [2,6,6,6]
4
      [6,1,4]  ->        [6,6,6]
5
        [1,4]  ->          [1,4]
6
          [4]  ->            [4]

于是问题变成： $a$ 或 $b$ 区间推平，求 $\sum a_ib_i$ 的历史和。

去掉历史和是平凡的，这里信息很容易看出来： $a$ 的和， $b$ 的和， $ab$ 的和，历史和（答案），区间长度。以上四个量分别记为 $x,y,xy,s,le$ 。

直接暴力矩阵转移！！！！！！！！！！！！！！！！！！

$\begin{bmatrix}x\y\xy\s\le \end{bmatrix} \begin{bmatrix}0&0&0&0&0\0&1&k&0&0\0&0&0&0&0\0&0&0&1&0\k&0&0&0&1 \end{bmatrix}=\begin{bmatrix}kle\y\ky\s\le \end{bmatrix}$

另外一个推平同理。

$\begin{bmatrix}x\y\xy\s\le \end{bmatrix} \begin{bmatrix}1&0&0&0&0\0&1&0&0&0\0&0&1&1&0\0&0&0&1&0\0&0&0&0&1 \end{bmatrix}=\begin{bmatrix}xle\y\xy\s+xy\le \end{bmatrix}$

然后这个是把答案加到历史和里的。

然后用上面的暴力程序多乘几次，发现除去 $1,0$ 就只有 $12$ 种可能的值，我们维护它，然后再用暴力程序跑一遍，暴力跑出转移式子，直接复制上去即可。

1
#include <cstdio>
2
#include <algorithm>
3
#include <vector>
4
#include <stack>
5
using namespace std;
6
typedef unsigned long long ll;
7

8
struct Tag {
9
  ll k[12];
10
  inline Tag(){ k[0]=k[3]=k[6]=1;k[1]=k[2]=k[4]=k[5]=k[7]=k[8]=k[9]=k[10]=k[11]=0; }
11

12
  inline Tag(int a0 , int a1 , int a2 , int a3 , int a4 , int a5 , int a6 , int a7 , int a8 , int a9 , int a10 , int a11){k[0]=a0;k[1]=a1;k[2]=a2;k[3]=a3;k[4]=a4;k[5]=a5;k[6]=a6;k[7]=a7;k[8]=a8;k[9]=a9;k[10]=a10;k[11]=a11;}
13

14
  inline Tag friend operator + (Tag l , Tag r) {
15
    Tag ret;
16
    ret.k[0] =  l.k[0] * r.k[0];
17
    ret.k[1] =  l.k[0] * r.k[1] + l.k[1] * r.k[6];
18
    ret.k[2] =  l.k[0] * r.k[2] + l.k[1] * r.k[7] + l.k[2];
19
    ret.k[3] =  l.k[3] * r.k[3];
20
    ret.k[4] =  l.k[3] * r.k[4] + l.k[4] * r.k[6];
21
    ret.k[5] =  l.k[3] * r.k[5] + l.k[4] * r.k[7] + l.k[5];
22
    ret.k[6] =  l.k[6] * r.k[6];
23
    ret.k[7] =  l.k[6] * r.k[7] + l.k[7];
24
    ret.k[8] =  l.k[8] * r.k[0] + r.k[8];
25
    ret.k[9] =  l.k[9] * r.k[3] + r.k[9];
26
    ret.k[10] =  l.k[8] * r.k[1] + l.k[9] * r.k[4] + l.k[10] * r.k[6] + r.k[10];
27
    ret.k[11] =  l.k[8] * r.k[2] + l.k[9] * r.k[5] + l.k[10] * r.k[7] + l.k[11] + r.k[11];
28
    return ret;
29
  }
30

31
  inline void operator += (Tag x) { (*this) = (*this) + x; }
32

33
  inline bool zbj(){ return k[0]!=1||k[3]!=1||k[6]!=1||k[1]||k[2]||k[4]||k[5]||k[7]||k[8]||k[9]||k[10]||k[11]; }
34
}lazy[1000005];
35

36
struct Seg {
37
  ll x , y , xy , s , le;
38
  inline Seg friend operator + (Seg l , Seg r){
39
    return (Seg){
40
      l.x + r.x , l.y + r.y , l.xy + r.xy ,
41
      l.s + r.s , l.le + r.le
42
    };
43
  }
44
  inline void operator += (Tag p){
45
    (*this) = (Seg){
46
      x * p.k[0] + le * p.k[8] ,
47
      y * p.k[3] + le * p.k[9] ,
48
      x * p.k[1] + y * p.k[4] + xy * p.k[6] + le * p.k[10] ,
49
      x * p.k[2] + y * p.k[5] + xy * p.k[7] + le * p.k[11] + s ,
50
      le
51
    };
52
  }
53
}tr[1000005];
54

55
void init(int p , int l , int r){
56
  tr[p].le = r - l + 1;
57
  if(l == r) return ;
58
  int mid = (l + r) >> 1;
59
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
60
}
61

62
inline void pushdown(int p){
63
  if(lazy[p].zbj()){
64
    tr[p << 1] += lazy[p]; tr[p << 1 | 1] += lazy[p];
65
    lazy[p << 1] += lazy[p]; lazy[p << 1 | 1] += lazy[p];
66
    lazy[p] = Tag();
67
  }
68
}
69

70
void upd(int p , int l , int r , int x , int y , Tag k){
71
  if(l > y || r < x) return ;
72
  if(l >= x && r <= y){ tr[p] += k; lazy[p] += k; return ; }
73
  int mid = (l + r) >> 1;
74
  pushdown(p);
75
  upd(p << 1 , l , mid , x , y , k);
76
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
77
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
78
}
79

80
Seg query(int p , int l , int r , int x , int y){
81
  if(l >= x && r <= y) return tr[p];
82
  int mid = (l + r) >> 1;
83
  pushdown(p);
84
  if(y <= mid) return query(p << 1 , l , mid , x , y);
85
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
86
  return (
87
    query(p << 1 , l , mid , x , y) +
88
    query(p << 1 | 1 , mid + 1 , r , x , y)
89
  );
90
}
91

92
int T , n , a[250005] , b[250005] , la[250005] , lb[250005];
93

94
struct QWQ { int l , r , k , op; };
95
vector <QWQ> chm[250005] , qqq[250005];
96

97
ll ans[250005];
98

99
int main(void){
100
  scanf("%d%d" , &T , &n);
101
  init(1 , 1 , n);
102
  stack <pair <int , int> > tmp;
103
  for(int i = 1;i <= n;i++){
104
    scanf("%d" , &a[i]);
105
    while(!tmp.empty() && tmp.top().first < a[i]) tmp.pop();
106
    if(!tmp.empty()) la[i] = tmp.top().second;
107
    tmp.push(make_pair(a[i] , i));
108
  }
109
  while(!tmp.empty()) tmp.pop();
110
  for(int i = 1;i <= n;i++){
111
    scanf("%d" , &b[i]);
112
    while(!tmp.empty() && tmp.top().first < b[i]) tmp.pop();
113
    if(!tmp.empty()) lb[i] = tmp.top().second;
114
    tmp.push(make_pair(b[i] , i));
115
  }
116
  for(int i = 1;i <= n;i++){
117
    chm[i].push_back((QWQ){la[i] + 1 , i , a[i] , 0});
118
    chm[i].push_back((QWQ){lb[i] + 1 , i , b[i] , 1});
119
  }
120
  scanf("%d" , &T);
121
  for(int i = 1 , l , r;i <= T;i++){
122
    scanf("%d%d" , &l , &r);
123
    qqq[l - 1].push_back((QWQ){l , r , -1 , i});
124
    qqq[r].push_back((QWQ){l , r , 1 , i});
125
  }
126
  for(int i = 1;i <= n;i++){
127
    for(QWQ j : chm[i]){
128
      if(j.op) upd(1 , 1 , n , j.l , j.r , Tag(1 , j.k , 0 , 0 , 0 , 0 , 0 , 0 , 0 , j.k , 0 , 0));
129
      if(!j.op)upd(1 , 1 , n , j.l , j.r , Tag(0 , 0 , 0 , 1 , j.k , 0 , 0 , 0 , j.k , 0 , 0 , 0));
130
    }
131
    upd(1 , 1 , n , 1 , n , Tag(1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0));
132
    for(QWQ j : qqq[i])
133
      ans[j.op] += j.k * query(1 , 1 , n , j.l , j.r).s;
134
  }
135
  for(int i = 1;i <= T;i++) printf("%llu\n" , ans[i]);
136
}

P3246 序列

求区间内所有子区间的最小值的和

我发现类似这种子区间的最值可以按如下思路思考：

比如有 $a=\{5,2,4,1 ,3\}$ ，那么：

1
5 2 4 1 3           5 2 2 1 1
2
  2 4 1 3             2 2 1 1
3
    4 1 3   ----->      4 1 1
4
      1 3                 1 1
5
        3                   3

可以发现是一个矩形，扫描线，且不需要撤回，后边的矩形会直接覆盖前面的。

然后就可以考虑每个点在对什么区间是有贡献的。

设 $pre_i$ 表示前一个比 $a_i$ 小的位置，不存在时值为 $0$ ； $nxt_i$ 表示后一个比 $a_i$ 小的位置，不存在时值为 $n+1$ 。这个可以用单调栈轻松计算

因此值为 $a_i$ 的矩形就是 $[pre_i + 1 , i , i , nxt_i - 1]$ ，由于新的会直接覆盖旧的的，所以 nxt 不需要考虑。这个可以用扫描线离线做。

于是问题变成：

a区间推平，求历史区间的和

历史和只会用矩阵。信息很容易知道，就是区间和 $s$ ，区间历史和 $b$ ，于是：

$\begin{bmatrix}s\b \ le\end{bmatrix}\begin{bmatrix}0&0&0\0&1&0 \ k&0&1\end{bmatrix}=\begin{bmatrix}k\times le\b \ le\end{bmatrix}$

$\begin{bmatrix}s\b \ le\end{bmatrix}\begin{bmatrix}1&1&0\0&1&0 \ 0&0&1\end{bmatrix}=\begin{bmatrix}s\b+s \ le\end{bmatrix}$

用暴力矩乘得出只有四个位置是有值的。直接再跑一次得转移即可。

1
#include <cstdio>
2
#include <algorithm>
3
#include <stack>
4
#include <vector>
5
using namespace std;
6
typedef long long ll;
7

8
struct Tag {
9
  ll k1 , k2 , k3 , k4;
10
  inline Tag(){k1 = 1; k2 = k3 = k4 = 0; }
11
  inline Tag(int _ , int __ , int ___ , int ____): k1(_) , k2(__) , k3(___) , k4(____) {}
12
  inline friend Tag operator + (Tag l , Tag r){
13
    Tag ret;
14
    ret.k1 = l.k1 * r.k1;
15
    ret.k2 = l.k1 * r.k2 + l.k2;
16
    ret.k3 = l.k3 * r.k1 + r.k3;
17
    ret.k4 = l.k3 * r.k2 + l.k4 + r.k4;
18
    return ret;
19
  }
20
  inline void operator += (Tag x){
21
    (*this) = (*this) + x;
22
  }
23
}lz[400005];
24

25
struct Seg {
26
  ll s , b; int le;
27
  inline Seg(){ s = b = le = 0; }
28
  inline friend Seg operator + (Seg l , Seg r){
29
    Seg ret;
30
    ret.s = l.s + r.s;
31
    ret.b = l.b + r.b;
32
    ret.le = l.le + r.le;
33
    return ret;
34
  }
35
  inline void operator += (Tag x){
36
    b += x.k2 * s + x.k4 * le;
37
    s = x.k1 * s + x.k3 * le;
38
  }
39
}tr[400005];
40

41
inline void upd(int p , Tag x){ tr[p] += x; lz[p] += x; }
42

43
inline void pushdown(int p){
44
  if(lz[p].k1 == 1 && lz[p].k2 == 0 && lz[p].k3 == 0 && lz[p].k4 == 0) return ;
45
  upd(p << 1 ,  lz[p]);
46
  upd(p << 1 | 1 , lz[p]);
47
  lz[p] = (Tag){1 , 0 , 0 , 0};
48
}
49

50
void upd(int p , int l , int r , int x , int y , Tag k){
51
  if(l > y || r < x) return ;
52
  if(l >= x && r <= y) { upd(p , k); return ; }
53
  int mid = (l + r) >> 1;
54
  pushdown(p);
55
  upd(p << 1 , l , mid , x , y , k);
56
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
57
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
58
}
59

60
Seg query(int p , int l , int r , int x , int y){
61
  if(l >= x && r <= y) return tr[p];
62
  int mid = (l + r) >> 1;
63
  pushdown(p);
64
  if(y <= mid) return query(p << 1 , l , mid , x , y);
65
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
66
  return (
67
    query(p << 1 , l , mid , x , y) +
68
    query(p << 1 | 1 , mid + 1 , r , x , y)
69
  );
70
}
71

72
void init(int p , int l , int r){
73
  if(l == r){ tr[p].s = tr[p].b = 0; tr[p].le = 1; return ;}
74
  int mid = (l + r) >> 1;
75
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
76
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
77
}
78

79
int n , q , a[100005] , pre[100005];
80

81
struct QWQ { int l , r , k , op; };
82
vector <QWQ> uuu[200005] , qqq[100005];
83

84
ll ans[100005];
85

86
void solve(){
87
  init(1 , 1 , n);
88
  stack <pair <int , int> > tmp;
89
  for(int i = 1;i <= n;i++){
90
    while(!tmp.empty() && tmp.top().first > a[i]) tmp.pop();
91
    if(!tmp.empty()) pre[i] = tmp.top().second;
92
    tmp.push({a[i] , i});
93
  }
94
  for(int i = 1;i <= n;i++)
95
    uuu[i].push_back((QWQ){pre[i] + 1 , i , a[i] , 0});
96
  for(int i = 1;i <= q;i++){
97
    int l , r; scanf("%d%d" , &l , &r);
98
    qqq[l - 1].push_back((QWQ){l , r , -1 , i});
99
    qqq[r].push_back((QWQ){l , r , 1 , i});
100
  }
101
  for(int i = 1;i <= n;i++){
102
    for(QWQ j : uuu[i]) upd(1 , 1 , n , j.l , j.r , Tag(0 , 0 , j.k , 0));
103
    upd(1 , Tag(1 , 1 , 0 , 0));
104
    for(QWQ j : qqq[i])
105
      ans[j.op] += 1LL * j.k * query(1 , 1 , n , j.l , j.r).b;
106
  }
107
  for(int i = 1;i <= q;i++) printf("%lld\n" , ans[i]);
108
}
109

110
int main(void){
111
  scanf("%d%d" , &n , &q);
112
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
113
  solve();
114
}

CF997E & 猫猫贴贴

给定一个排列，多次询问，求区间内子区间有多少是取值连续的 $n,q\le 1.2 \times 10^5$

毒瘤题，十年河东十年河西，莫欺少年穷。

首先排列很重要，意味着取值不重复，于是取值连续的区间需要满足 $\max-\min=r-l$ ，即 $\max-\min-r+l=0$ 。

按照扫描线的思路，放到二维平面上，横 l，纵 r，先把每个点权值改为 $l-r$ ，这个是简单的，可以转换成区间加。

然后考虑更新 $\min$ 和 $\max$ ，如果可以，问题就变成矩形求 $0$ 的个数，因为 $0\le \max-\min-r+l$ ，所以这玩意可以用最小值和最小值的个数维护。

1
#include <cstdio>
2
#include <vector>
3
#include <algorithm>
4
#include <stack>
5
using namespace std;
6

7
struct Tag {
8
  int ad , tg;
9
  inline Tag(){ ad = tg = 0; }
10
  inline Tag(int _ , int __): ad(_) , tg(__) {}
11
  inline void operator += (Tag b){ ad += b.ad; tg += b.tg; }
12
}lz[480005];
13

14
struct Seg {
15
  int mi , cntmi; long long ans;
16
  inline friend Seg operator + (Seg ls , Seg rs){
17
    Seg ret;
18
    if(ls.mi < rs.mi){
19
      ret.mi = ls.mi;
20
      ret.cntmi = ls.cntmi;
21
    }
22
    else if(ls.mi > rs.mi){
23
      ret.mi = rs.mi;
24
      ret.cntmi = rs.cntmi;
25
    }
26
    else{
27
      ret.mi = ls.mi;
28
      ret.cntmi = ls.cntmi + rs.cntmi;
29
    }
30
    ret.ans = ls.ans + rs.ans;
31
    return ret;
32
  }
33
}tr[480005];
34

35
inline void upd(int p , Tag x , int tmp){
36
  lz[p].ad += x.ad;
37
  if((tr[p].mi += x.ad) == tmp){
38
    tr[p].ans += 1LL * x.tg * tr[p].cntmi;
39
    lz[p].tg += x.tg;
40
  }
41
}
42

43
inline void pushdown(int p){
44
  if(lz[p].ad == 0 && lz[p].tg == 0) return ;
45
  upd(p << 1 , lz[p] , tr[p].mi);
46
  upd(p << 1 | 1 , lz[p] , tr[p].mi);
47
  lz[p] = Tag(0 , 0);
48
}
49

50
void upd(int p , int l , int r , int x , int y , Tag k){
51
  if(l > y || r < x) return ;
52
  if(l >= x && r <= y){ upd(p , k , 0); return ; }
53
  int mid = (l + r) >> 1;
54
  pushdown(p);
55
  upd(p << 1 , l , mid , x , y , k);
56
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
57
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
58
}
59

60
Seg query(int p , int l , int r , int x , int y){
61
  if(l >= x && r <= y) return tr[p];
62
  int mid = (l + r) >> 1;
63
  pushdown(p);
64
  if(y <= mid) return query(p << 1, l , mid , x , y);
65
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
66
  return (
67
    query(p << 1 , l , mid , x , y) +
68
    query(p << 1 | 1 , mid + 1 , r , x , y)
69
  );
70
}
71

72
void init(int p , int l , int r){
73
  if(l == r){ tr[p].cntmi = 1; return ; }
74
  int mid = (l + r) >> 1;
75
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
76
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
77
}
78

79
int n , m , p[120005];
80
int lx[120005] , rx[120005] , li[120005] , ri[120005];
81

82
struct QWQ { int l , r , k , id; };
83
vector <QWQ> u[120005] , q[120005];
84

85
inline void solve(int retl[120005] , int retr[120005] , bool (*cmp)(int , int)){
86
  stack <pair <int , int> > st;
87
  for(int i = 1;i <= n;i++){
88
    while(!st.empty() && cmp(st.top().first , p[i])) st.pop();
89
    retl[i] = st.empty()? 0 : st.top().second;
90
    st.push({p[i] , i});
91
  }
92
  while(!st.empty()) st.pop();
93
  for(int i = n;i >= 1;i--){
94
    while(!st.empty() && cmp(st.top().first , p[i])) st.pop();
95
    retr[i] = st.empty()? n + 1 : st.top().second;
96
    st.push({p[i] , i});
97
  }
98
}
99

100
long long ans[120005];
101

102
int main(void){
103
  scanf("%d" , &n);
104
  for(int i = 1;i <= n;i++) scanf("%d" , &p[i]);
105
  scanf("%d" , &m);
106
  for(int i = 1;i <= m;i++){
107
    int l , r; scanf("%d%d" , &l , &r);
108
    q[l - 1].push_back((QWQ){l , r , -1 , i});
109
    q[r].push_back((QWQ){l , r , 1 , i});
110
  }
111
  solve(lx , rx , [](int x , int y) -> bool {return x < y; });
112
  solve(li , ri , [](int x , int y) -> bool {return x > y; });
113
  for(int i = 1;i <= n;i++){
114
    u[lx[i] + 1].push_back((QWQ){i , rx[i] - 1 , p[i] , 0});
115
    u[i + 1].push_back((QWQ){i , rx[i] - 1 , -p[i] , 0});
116
    u[li[i] + 1].push_back((QWQ){i , ri[i] - 1 , -p[i] , 0});
117
    u[i + 1].push_back((QWQ){i , ri[i] - 1 , p[i] , 0});
118
  }
119
  for(int i = 1;i <= n;i++){
120
    u[i].push_back((QWQ){1 , n , 1 , 0});
121
    u[1].push_back((QWQ){i , i , -i , 0});
122
  }
123
  init(1 , 1 , n);
124
  for(int i = 1;i <= n;i++){
125
    for(QWQ j : u[i]) upd(1 , 1 , n , j.l , j.r , Tag(j.k , 0));
126
    upd(1 , Tag(0 , 1) , 0);
127
    for(QWQ j : q[i]) ans[j.id] += 1LL * j.k * query(1 , 1 , n , j.l , j.r).ans;
128
  }
129
  for(int i = 1;i <= m;i++) printf("%lld\n" , ans[i]);
130
}

P9990 Ynoi Easy Round 2023 TEST_90 & P10822

多次询问区间的所有子区间有多少满足出现数字种类个数是奇数

首先可以转换成区间内所有子区间的数字个数对 2 取模的和。

一般的，区间出现个数可以用 $\sum [pre_i < l]$ 来计算，根据这个我们很容易写出矩形： $[pre_i+1,i,i,n]$

发现区间增加 1 实际上就是异或 1，于是需要线段树实现区间异或，求历史区间和。

有点困难，考虑用矩阵代替大脑思考下。

维护的显然就是区间 1 的数量 $a$ ，历史区间和 $b$ 。于是：

$\begin{bmatrix}a\b \ le\end{bmatrix}\begin{bmatrix}-1&0&0\0&1&0 \ 1&0&1\end{bmatrix}=\begin{bmatrix}le-a\b \ le\end{bmatrix}$

$\begin{bmatrix}a\b \ le\end{bmatrix}\begin{bmatrix}1&1&0\0&1&0 \ 0&0&1\end{bmatrix}=\begin{bmatrix}a\a+b \ le\end{bmatrix}$

又到了暴力转移的时候。

这方法常数有点大。。。。要卡常（最好不用vector）

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4

5
char buf[1 << 21] , *p1 , *p2;
6
#define GC p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2) ? EOF : *p1++
7
inline int read() {
8
  int x = 0; char ch = GC;
9
  while(ch > '9' || ch < '0') ch = GC;
10
  while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ 48); ch = GC; }
11
  return x;
12
}
13

14
struct Tag {
15
  int k1 , k3 , k2 , k4;
16
  inline Tag(){ k1 = 1; k2 = k3 = k4 = 0; }
17
  inline Tag(int _ , int __ , int ___ , int ____): k1(_) , k2(__) , k3(___) , k4(____) {}
18
  inline friend Tag operator + (Tag l , Tag r){
19
    return Tag(
20
      l.k1 * r.k1 ,
21
      l.k1 * r.k2 + l.k2 ,
22
      l.k3 * r.k1 + r.k3 ,
23
      l.k3 * r.k2 + l.k4 + r.k4
24
    );
25
  }
26
  inline void operator += (Tag x){ (*this) = (*this) + x; }
27
}lz[4000005];
28

29
struct Seg {
30
  int a , le; long long b;
31
  inline Seg(){ a = b = le = 0; }
32
  inline Seg(int _ , long long __ , int ___): a(_) , b(__) , le(___) {}
33
  inline friend Seg operator + (Seg ls , Seg rs){
34
    return Seg(ls.a + rs.a , ls.b + rs.b , ls.le + rs.le);
35
  }
36
  inline void operator += (Tag x){
37
    (*this) = Seg(x.k1 * a + x.k3 * le , 1LL * x.k2 * a + b + 1LL * x.k4 * le , le);
38
  }
39
}tr[4000004];
40

41
inline void pushdown(int p){
42
  if(lz[p].k1 == 1 && lz[p].k2 == 0 && lz[p].k3 == 0 && lz[p].k4 == 0) return ;
43
  tr[p << 1] += lz[p]; lz[p << 1] += lz[p];
44
  tr[p << 1 | 1] += lz[p]; lz[p << 1 | 1] += lz[p];
45
  lz[p] = Tag();
46
}
47

48
void upd(int p , int l , int r , int x , int y , Tag k){
49
  if(l > y || r < x) return ;
50
  if(l >= x && r <= y){
51
    tr[p] += k; lz[p] += k;
52
    return ;
53
  }
54
  int mid = (l + r) >> 1;
55
  pushdown(p);
56
  upd(p << 1 , l , mid , x , y , k);
57
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
58
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
59
}
60

61
Seg query(int p , int l , int r , int x , int y){
62
  if(l >= x && r <= y) return tr[p];
63
  int mid = (l + r) >> 1;
64
  pushdown(p);
65
  if(y <= mid) return query(p << 1 , l , mid , x , y);
66
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
67
  return (
68
    query(p << 1 , l , mid , x , y) +
69
    query(p << 1 | 1 , mid + 1 , r , x , y)
70
  );
71
}
72

73
void init(int p , int l , int r){ //
74
  if(l == r){ tr[p].le = 1; return ; }
75
  int mid = (l + r) >> 1;
76
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
77
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
78
}
79

80
int n , m , pre[1000005];
81
struct QWQ {
82
  int x , l , r , k , id;
83
  inline bool operator < (QWQ b) {
84
    if(x == b.x) return id < b.id;
85
    return x < b.x;
86
  }
87
}qqq[4000005]; int qn;
88
long long ans[1000005];
89

90
int main(void){
91
  n = read();
92
  for(int i = 1 , a;i <= n;i++){
93
    a = read();
94
    qqq[i] = (QWQ){pre[a] + 1 , i , n , 0 , 0};
95
    qqq[i + n] = (QWQ){i + 1 , i , n , 0 , 0};
96
    pre[a] = i;
97
  }
98
  m = read();
99
  qn = (n << 1);
100
  for(int i = 1;i <= m;i++){
101
    int l , r; l = read(); r = read();
102
    qqq[++qn] = (QWQ){l - 1 , l , r , 0 , i};
103
    qqq[++qn] = (QWQ){r , l , r , 1 , i};
104
  }
105
  sort(qqq + 1 , qqq + 1 + qn);
106
  init(1 , 1 , n);
107
  int i = 1;
108
  while(i <= qn){
109
    int st = qqq[i].x;
110
    while(i <= qn && qqq[i].x == st && qqq[i].id == 0)
111
      upd(1 , 1 , n , qqq[i].l , qqq[i].r , Tag(-1 , 0 , 1 , 0)) , i++;
112
    tr[1] += Tag(1 , 1 , 0 , 0); lz[1] += Tag(1 , 1 , 0 , 0);
113
    while(i <= qn && qqq[i].x == st)
114
      ans[qqq[i].id] += qqq[i].k? query(1 , 1 , n , qqq[i].l , qqq[i].r).b : -query(1 , 1 , n , qqq[i].l , qqq[i].r).b , i++;
115
  }
116
  for(int i = 1;i <= m;i++) printf("%lld\n" , ans[i]);
117
}

区间最值操作与历史最值问题

本节参考：

论文《区间最值操作与历史最值问题》——吉如一

区间最值操作与区间历史最值详解灵梦

oi-wki

区间最值操作

实现区间取最值的一种方法。（下以取最小值为例）

区间维护区间最大值（mx），严格次大值（mx2），最大值的个数（cnt）。

然后区间操作（ $a_i=\min(x,a_i)$ ）有如下情况：

$mx \le x$ ：直接退出
$mx2 < x \le mx$ ：仅修改最大值，打标记。
$x\le mx2$ ：递归下去。

论文证明复杂度为 $O(\log n)$ 。关于复杂度，还可以看看 Segment tree beats 的时间复杂度下限为 2log。

然后如果加上区间加的操作，实现类似，复杂度变为 $O(\log^2 n)$ 。

深挖上面那种方法的本质，实际上就是分类。

将点分成两类：最大值和非最大值。

于是另一种实现区间取最值的方法呼吁而出。

仅修改最大值，那么就是推平操作，可以转换成加操作。

标记需要两套：最大的加标记，非最大值的加标记。

于是这种方法便实现了：区间取最值->区间加

这种思路很有启发性。

最佳女选手

区间加，区间取最大值，区间取最小值，求区间和，求区间最大最小

类比：如果同时有取最大和取最小的操作，那么可以分三类。最大，最小，其他。

按照上面方法维护即可，注意合并函数里的细节。

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4
typedef long long ll;
5

6
const ll inf = 1e17;
7

8
char buf[1 << 21] , *p1 , *p2;
9
#define GC p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2) ? EOF : *p1++
10
inline int read() {
11
  int x = 0;
12
    bool f = false;
13
  char ch = GC;
14
  while(ch > '9' || ch < '0'){
15
        if(ch == '-')
16
            f = true;
17
        ch = GC;
18
    }
19
  while(ch >= '0' && ch <= '9'){
20
    x = (x << 1) + (x << 3) + (ch ^ 48);
21
    ch = GC;
22
  }
23
  return f? -x : x;
24
}
25

26
struct Tag {
27
  ll admx , admi , ad;
28
  inline void operator += (Tag b){ admx += b.admx; admi += b.admi; ad += b.ad; }
29
}tg[2000005];
30

31
struct Seg {
32
  ll mx , mx2; int cntmx;
33
  ll mi , mi2; int cntmi;
34
  ll sum; int le;
35

36
  inline friend Seg operator + (Seg ls , Seg rs){
37
    Seg ret;
38
    if(ls.mx > rs.mx){
39
      ret.mx = ls.mx; ret.cntmx = ls.cntmx;
40
      ret.mx2 = max(ls.mx2 , rs.mx);
41
    }
42
    else if(ls.mx < rs.mx){
43
      ret.mx = rs.mx; ret.cntmx = rs.cntmx;
44
      ret.mx2 = max(ls.mx , rs.mx2);
45
    }
46
    else{
47
      ret.mx = ls.mx; ret.cntmx = ls.cntmx + rs.cntmx;
48
      ret.mx2 = max(ls.mx2 , rs.mx2);
49
    }
50
    if(ls.mi < rs.mi){
51
      ret.mi = ls.mi; ret.cntmi = ls.cntmi;
52
      ret.mi2 = min(ls.mi2 , rs.mi);
53
    }
54
    else if(ls.mi > rs.mi){
55
      ret.mi = rs.mi; ret.cntmi = rs.cntmi;
56
      ret.mi2 = min(ls.mi , rs.mi2);
57
    }
58
    else {
59
      ret.mi = ls.mi; ret.cntmi = ls.cntmi + rs.cntmi;
60
      ret.mi2 = min(ls.mi2 , rs.mi2);
61
    }
62
    ret.sum = ls.sum + rs.sum;
63
    ret.le = ls.le + rs.le;
64
    return ret;
65
  }
66

67
  inline void operator += (Tag x){
68
    if(mx == mi) sum += x.admx * cntmx;
69
    else sum += x.admx * cntmx + x.admi * cntmi + x.ad * (le - cntmx - cntmi);
70
    if(mi2 == mx) mi2 += x.admx;
71
    else if(mi2 !=  inf) mi2 += x.ad;
72
    if(mx2 == mi) mx2 += x.admi;
73
    else if(mx2 != -inf) mx2 += x.ad;
74
    mx += x.admx; mi += x.admi;
75
  }
76
}tr[2000005];
77

78
inline void upd(int p , Tag x){
79
  if(tr[p].mx == tr[p].mi){
80
    if(x.admi == x.ad) x.admi = x.admx;
81
    else x.admx = x.admi;
82
  }
83
  tr[p] += x; tg[p] += x;
84
}
85

86
inline void pushdown(int p){
87
  if(tg[p].ad == 0 && tg[p].admx == 0 && tg[p].admi == 0) return ;
88
  ll mx = max(tr[p << 1].mx , tr[p << 1 | 1].mx);
89
  ll mi = min(tr[p << 1].mi , tr[p << 1 | 1].mi);
90
  upd(p << 1 , (Tag){
91
    tr[p << 1].mx == mx? tg[p].admx : tg[p].ad ,
92
    tr[p << 1].mi == mi? tg[p].admi : tg[p].ad ,
93
    tg[p].ad
94
  });
95
  upd(p << 1 | 1 , (Tag){
96
    tr[p << 1 | 1].mx == mx? tg[p].admx : tg[p].ad ,
97
    tr[p << 1 | 1].mi == mi? tg[p].admi : tg[p].ad ,
98
    tg[p].ad
99
  });
100
  tg[p] = (Tag){0 , 0 , 0};
101
}
102

103
int a[500005];
104
void init(int p , int l , int r){
105
  if(l == r){
106
    tr[p].mx2 = -inf; tr[p].mi2 = inf;
107
    tr[p].sum = tr[p].mx = tr[p].mi = a[l];
108
    tr[p].cntmx = tr[p].cntmi = 1;
109
    tr[p].le = 1;
110
    return ;
111
  }
112
  int mid = (l + r) >> 1;
113
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
114
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
115
}
116

117
void upd1(int p , int l , int r , int x , int y , Tag k){
118
  if(l > y || r < x) return ;
119
  if(l >= x && r <= y){ upd(p , k); return ; }
120
  pushdown(p);
121
  int mid = (l + r) >> 1;
122
  upd1(p << 1 , l , mid , x , y , k);
123
  upd1(p << 1 | 1 , mid + 1 , r , x , y , k);
124
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
125
}
126

127
void upd_max(int p , int l , int r , int x , int y , int k){
128
  if(l > y || r < x || tr[p].mi >= k) return ;
129
  if(l >= x && r <= y && k < tr[p].mi2){
130
    upd(p , (Tag){0 , k - tr[p].mi , 0});
131
    return ;
132
  }
133
  pushdown(p);
134
  int mid = (l + r) >> 1;
135
  upd_max(p << 1 , l , mid , x , y , k);
136
  upd_max(p << 1 | 1 , mid + 1 , r , x , y , k);
137
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
138
}
139

140
void upd_min(int p , int l , int r , int x , int y , int k){
141
  if(l > y || r < x || tr[p].mx <= k) return ;
142
  if(l >= x && r <= y && k > tr[p].mx2){
143
    upd(p , (Tag){k - tr[p].mx , 0 , 0});
144
    return ;
145
  }
146
  pushdown(p);
147
  int mid = (l + r) >> 1;
148
  upd_min(p << 1 , l , mid , x , y , k);
149
  upd_min(p << 1 | 1 , mid + 1 , r , x , y , k);
150
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
151
}
152

153
Seg query(int p , int l , int r , int x , int y){
154
  if(l >= x && r <= y) return tr[p];
155
  pushdown(p);
156
  int mid = (l + r) >> 1;
157
  if(y <= mid) return query(p << 1 , l , mid , x , y);
158
  if(x > mid ) return query(p << 1 | 1 , mid + 1 , r , x , y);
159
  return (
160
    query(p << 1 , l , mid , x , y) +
161
    query(p << 1 | 1 , mid + 1 , r , x , y)
162
  );
163
}
164

165
int n , m;
166

167
int main(void){
168
  n = read();
169
  for(int i = 1;i <= n;i++) a[i] = read();
170
  init(1 , 1 , n);
171
  m = read();
172
  while(m--){
173
    int op , l , r;
174
    op = read(); l = read(); r = read();
175
    if(op == 1){
176
      int x = read();
177
      upd1(1 , 1 , n , l , r , (Tag){x , x , x});
178
    }
179
    if(op == 2){
180
      int x = read();
181
      upd_max(1 , 1 , n , l , r , x);
182
    }
183
    if(op == 3){
184
      int x = read();
185
      upd_min(1 , 1 , n , l , r , x);
186
    }
187
    if(op == 4) printf("%lld\n" , query(1 , 1 , n , l , r).sum);
188
    if(op == 5) printf("%lld\n" , query(1 , 1 , n , l , r).mx);
189
    if(op == 6) printf("%lld\n" , query(1 , 1 , n , l , r).mi);
190
  }
191
}

历史最值问题

前置：复杂标记信息合并。

一般这种可以用 $(\max,+)$ 矩阵来设计标记，如果再加上区间最值操作呢？直接看模板把。

线段树3

区间加，区间取 min，求区间和，区间最大值，历史区间最大值

还是按照上面思路分两类：最大，非最大。上面说了可以转换成加法，于是考虑如何维护。

这里还是使用矩阵（~~由于不会直接推~~）。

显然信息就是区间最大值 a，历史最大 b（这里历史最值和区间和无关，分别维护）。这样。

$\begin{bmatrix} a\b \end{bmatrix}\begin{bmatrix} x & x\-\infty& 0 \end{bmatrix}=\begin{bmatrix} a+x\\max{b,a+x} \end{bmatrix}$

让我们暴力拆拆拆。

暴力程序跑出来，显然只需要维护矩阵的第一行两项即可，然后再跑矩阵转移即可。

然后就写完了。

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4
typedef long long ll;
5

6
const int inf = 2e9;
7

8
struct Tag {
9
  int k1 , k2; //最大值
10
  int k3 , k4; //非最大
11
  inline Tag(){ k1 = k2 = k3 = k4 = 0; }
12
  inline Tag(ll _ , ll __ , ll ___ , ll ____): k1(_) , k2(__) , k3(___) , k4(____) {}
13
  inline void operator += (Tag x){
14
    (*this) = Tag(
15
      k1 + x.k1 , max(k1 + x.k2 , k2) ,
16
      k3 + x.k3 , max(k3 + x.k4 , k4)
17
    );
18
  }
19
}lz[2000005];
20

21
struct Seg {
22
  int a , b , mx2 , cntmx , le; ll s;
23
  inline Seg(){ a = b = mx2 = -inf; cntmx = le = 0; }
24
  inline Seg(ll _ , ll __ , ll ___): a(_) , b(__) , s(___) {}
25
  inline friend Seg operator + (Seg ls , Seg rs){
26
    Seg ret;
27
    ret.b = max(ls.b , rs.b);
28
    ret.s = ls.s + rs.s;
29
    ret.le = ls.le + rs.le;
30
    if(ls.a < rs.a){
31
      ret.a = rs.a; ret.cntmx = rs.cntmx;
32
      ret.mx2 = max(ls.a , rs.mx2);
33
    }
34
    else if(ls.a > rs.a){
35
      ret.a = ls.a; ret.cntmx = ls.cntmx;
36
      ret.mx2 = max(ls.mx2 , rs.a);
37
    }
38
    else{
39
      ret.a = ls.a; ret.cntmx = ls.cntmx + rs.cntmx;
40
      ret.mx2 = max(ls.mx2 , rs.mx2);
41
    }
42
    return ret;
43
  }
44
  inline void operator += (Tag x){
45
    b = max(b , a + x.k2); a += x.k1;
46
    s += 1LL * x.k1 * cntmx + 1LL * x.k3 * (le - cntmx);
47
    if(mx2 != -inf){
48
      b = max(b , mx2 + x.k4);
49
      mx2 += x.k3;
50
    }
51
  }
52
}tr[2000005];
53

54
inline void upd(int p , Tag x){ tr[p] += x; lz[p] += x; }
55

56
inline void pushdown(int p){
57
  if(lz[p].k1 == 0 && lz[p].k2 == 0 && lz[p].k3 == 0 && lz[p].k4 == 0) return ;
58
  int mx = max(tr[p << 1].a , tr[p << 1 | 1].a);
59
  if(tr[p << 1].a == mx)
60
    upd(p << 1 , lz[p]);
61
  else
62
    upd(p << 1 , Tag(lz[p].k3 , lz[p].k4 , lz[p].k3 , lz[p].k4));
63
  if(tr[p << 1 | 1].a == mx)
64
    upd(p << 1 | 1 , lz[p]);
65
  else
66
    upd(p << 1 | 1 , Tag(lz[p].k3 , lz[p].k4 , lz[p].k3 , lz[p].k4));
67
  lz[p] = Tag(0 , 0 , 0 , 0);
68
}
69

70
void add(int p , int l , int r , int x , int y , int k){
71
  if(l > y || r < x) return ;
72
  if(l >= x && r <= y){
73
    upd(p , Tag(k , k , k , k));
74
    return ;
75
  }
76
  int mid = (l + r) >> 1;
77
  pushdown(p);
78
  add(p << 1 , l , mid , x , y , k);
79
  add(p << 1 | 1 , mid + 1 , r , x , y , k);
80
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
81
}
82

83
void upd_min(int p , int l , int r , int x , int y , int k){
84
  if(l > y || r < x || tr[p].a <= k) return ;
85
  if(l >= x && r <= y && k > tr[p].mx2){
86
    upd(p , Tag(k - tr[p].a , k - tr[p].a , 0 , 0));
87
    return ;
88
  }
89
  int mid = (l + r) >> 1;
90
  pushdown(p);
91
  upd_min(p << 1 , l , mid , x , y , k);
92
  upd_min(p << 1 | 1 , mid + 1 , r , x , y , k);
93
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
94
}
95

96
Seg query(int p , int l , int r , int x , int y){
97
  if(l >= x && r <= y) return tr[p];
98
  int mid = (l + r) >> 1;
99
  pushdown(p);
100
  if(y <= mid) return query(p << 1 , l , mid , x , y);
101
  if(x > mid ) return query(p << 1 | 1 , mid + 1 , r , x , y);
102
  return (
103
    query(p << 1 , l , mid , x , y) +
104
    query(p << 1 | 1 , mid + 1 , r , x , y)
105
  );
106
}
107

108
int a[500005];
109
void init(int p , int l , int r){
110
  if(l == r){
111
    tr[p].a = tr[p].b = tr[p].s = a[l];
112
    tr[p].cntmx = tr[p].le = 1;
113
    tr[p].mx2 = -inf;
114
    return ;
115
  }
116
  int mid = (l + r) >> 1;
117
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
118
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
119
}
120

121
int n , m;
122

123
int main(void){
124
  scanf("%d%d" , &n , &m);
125
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
126
  init(1 , 1 , n);
127
  while(m--){
128
    int op , l , r; scanf("%d%d%d" , &op , &l , &r);
129
    if(op == 1){
130
      int x; scanf("%d" , &x);
131
      add(1 , 1 , n , l , r , x);
132
    }
133
    if(op == 2){
134
      int x; scanf("%d" , &x);
135
      upd_min(1 , 1 , n , l , r , x);
136
    }
137
    if(op == 3) printf("%lld\n" , query(1 , 1 , n , l , r).s);
138
    if(op == 4) printf("%d\n" , query(1 , 1 , n , l , r).a);
139
    if(op == 5) printf("%d\n" , query(1 , 1 , n , l , r).b);
140
  }
141
}

CPU监控

这题就可以用 $(\max,+)$ 矩阵。

很容易想到维护当前最大值 $a$ ，和历史最大值 $b$ 。

$\begin{bmatrix}a\b\ \end{bmatrix}\begin{bmatrix}k&k\-\infty&0\ \end{bmatrix}=\begin{bmatrix}a+k\\max{a+k,b}\ \end{bmatrix}$

如果再加上推平，就需要再多加一个 $0$ 。

$\begin{bmatrix}a\b\0\ \end{bmatrix}\begin{bmatrix}-\infty&-\infty&-\infty\-\infty&0&-\infty\k&k&0\ \end{bmatrix}=\begin{bmatrix}k\\max{b,k}\0\ \end{bmatrix}$

不难发现只要第一行第一二个和第三行第一二个会变，于是维护这些，然后跑上面的暴力转移代码即可。

1
#include <cstdio>
2
#include <algorithm>
3
using namespace std;
4

5
const int inf = 2147480000;
6
int n , m , a[100005];
7

8
inline int Add(int x , int y){
9
  if(x <= -inf || y <= -inf) return -inf;
10
  return x + y;
11
}
12

13
struct Tag {
14
  int k11 , k12 , k21 , k22;
15
  inline Tag(){ k11 = 0; k12 = k21 = k22 = -inf; }
16
  inline Tag(int _ , int __): k11(_) , k12(_) , k21(__) , k22(__) {}
17
  inline friend Tag operator + (Tag l , Tag r){
18
    Tag ret;
19
    ret.k11 = Add(l.k11 , r.k11);
20
    ret.k12 = max(l.k12 , Add(l.k11 , r.k12));
21
    ret.k21 = max(Add(l.k21 , r.k11) , r.k21);
22
    ret.k22 = max(Add(l.k21 , r.k12) , max(l.k22 , r.k22));
23
    return ret;
24
  }
25
  inline void operator += (Tag x){ (*this) = (*this) + x; }
26
}lazy[400005];
27

28
struct Seg {
29
  int maxn , ans;
30
  inline Seg(){ maxn = ans = -inf; }
31
  inline Seg(int _ , int __): maxn(_) , ans(__) {}
32
  inline friend Seg operator + (Seg ls , Seg rs){
33
    return Seg(
34
      max(ls.maxn , rs.maxn) ,
35
      max(ls.ans , rs.ans)
36
    );
37
  }
38
  inline void operator += (Tag rs){
39
    ans = max(ans , max(Add(maxn , rs.k12) , rs.k22));
40
    maxn = max(Add(maxn , rs.k11) , rs.k21);
41
    ans = max(ans , maxn);
42
  }
43
}tr[400005];
44

45
inline void pushdown(int p){
46
  if(lazy[p].k11 != 0 || lazy[p].k12 != -inf || lazy[p].k21 > -inf || lazy[p].k22 > -inf){
47
    tr[p << 1] += lazy[p];
48
    tr[p << 1 | 1] += lazy[p];
49
    lazy[p << 1] += lazy[p];
50
    lazy[p << 1 | 1] += lazy[p];
51
    lazy[p] = Tag();
52
  }
53
}
54

55
void init(int p , int l , int r){
56
  if(l == r){
57
    tr[p].maxn = tr[p].ans = a[l];
58
    return ;
59
  }
60
  int mid = (l + r) >> 1;
61
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
62
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
63
}
64

65
void upd(int p , int l , int r , int x , int y , Tag k){
66
  if(l > y || r < x) return ;
67
  if(l >= x && r <= y){ tr[p] += k; lazy[p] += k; return ; }
68
  int mid = (l + r) >> 1;
69
  pushdown(p);
70
  upd(p << 1 , l , mid , x , y , k);
71
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
72
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
73
}
74

75
Seg query(int p , int l , int r , int x , int y){
76
  if(l >= x && r <= y) { return tr[p];
77
  }
78
  int mid = (l + r) >> 1;
79
  pushdown(p);
80
  if(y <= mid) return query(p << 1 , l , mid , x , y);
81
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
82
  return (
83
    query(p << 1 , l , mid , x , y) +
84
    query(p << 1 | 1 , mid + 1 , r , x , y)
85
  );
86
}
87

88
int main(void){
89
  scanf("%d" , &n);
90
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
91
  init(1 , 1 , n);
92
  scanf("%d" , &m);
93
  while(m--){
94
    char s[5]; scanf("%s" , s + 1);
95
    if(s[1] == 'Q'){
96
      int l , r; scanf("%d%d" , &l , &r);
97
      printf("%d\n" , query(1 , 1 , n , l , r).maxn);
98
    }
99
    if(s[1] == 'A'){
100
      int l , r; scanf("%d%d" , &l , &r);
101
      printf("%d\n" , query(1 , 1 , n , l , r).ans);
102
    }
103
    if(s[1] == 'P'){
104
      int l , r , x; scanf("%d%d%d" , &l , &r , &x);
105
      upd(1 , 1 , n , l , r , Tag(x , -inf));
106
    }
107
    if(s[1] == 'C'){
108
      int l , r , x; scanf("%d%d%d" , &l , &r , &x);
109
      upd(1 , 1 , n , l , r , Tag(-inf , x));
110
    }
111
  }
112
}

SP1557 GSS2

区间最大子段和，相同数贡献仅算一次。

可以考虑离线，按照 r 排序，然后依次加入。

每个点维护当前加入 i 的和，于是比较显然，加一个点就相当于 $(pre,i]$ 的区间加。

显然答案需要历史最大值，于是只需要实现区间加，区间查历史最大值就做完了。

由于 SPOJ 我交不了，就没写代码。

选讲

HDU6315（势能线段树）

$a_i=0$ ， $b$ 为 $n$ 的排列。

$a$ 区间加。

求区间 $\sum \lfloor a_i/b_i \rfloor$ 。

$m,n\le 10^5$

注意到答案最大为 $n/1+...n/n$ ，大约是 1e6，于是维护每个数还要加几次才会更新答案，如果区间最小为 $1$ ，则 $log n$ 找到这个点，改答案，总时间复杂度为 $O(n\log^2 n)$ 。

P5354 Ynoi 由乃的OJ

比较显然，先树剖转链。

然后可以建 $64$ 棵线段树，然后每颗树维护这段区间传入 $0/1$ 出来的值，然后贪心地选 $1$ 即可。 $O(mk\log n)$ 很可惜过不了。

其实因为运算符一样，可以一起计算：线段树维护传如 $000.../1111...$ 出来的值，然后考虑如何合并左右子树。

这样即可：

1
tr[p][0] = ((tr[p << 1 | 1][0] & (~tr[p << 1][0])) | (tr[p << 1 | 1][1] & tr[p << 1][0]));
2
tr[p][1] = ((tr[p << 1 | 1][0] & (~tr[p << 1][1])) | (tr[p << 1 | 1][1] & tr[p << 1][1]));

做完了。

1
#include <cstdio>
2
#include <algorithm>
3
#include <vector>
4
using namespace std;
5
typedef unsigned long long ll;
6

7
int n , m , k; pair <int , ll> a[100005];
8
vector <int> g[100005];
9

10
int dep[100005] , son[100005] , fa[100005] , siz[100005];
11
void dfs1(int x , int f , int d){
12
  siz[x] = 1; fa[x] = f; dep[x] = d;
13
  int maxn = -1;
14
  for(int nxt : g[x]){
15
    if(nxt == f) continue;
16
    dfs1(nxt , x , d + 1);
17
    siz[x] += siz[nxt];
18
    if(siz[nxt] > maxn){
19
      maxn = siz[nxt];
20
      son[x] = nxt;
21
    }
22
  }
23
}
24

25
int tp[100005] , id[100005] , cnt; pair <int , ll> w[100005];
26
void dfs2(int x , int top){
27
  tp[x] = top;
28
  w[id[x] = ++cnt] = a[x];
29
  if(son[x]) dfs2(son[x] , top);
30
  for(int nxt : g[x]){
31
    if(nxt == fa[x] || nxt == son[x]) continue;
32
    dfs2(nxt , nxt);
33
  }
34
}
35

36
ll tr[400005][4];
37

38
inline void pushup(int p){
39
  tr[p][0] = ((tr[p << 1 | 1][0] & (~tr[p << 1][0])) | (tr[p << 1 | 1][1] & tr[p << 1][0]));
40
  tr[p][1] = ((tr[p << 1 | 1][0] & (~tr[p << 1][1])) | (tr[p << 1 | 1][1] & tr[p << 1][1]));
41
  tr[p][2] = ((tr[p << 1][2] & (~tr[p << 1 | 1][2])) | (tr[p << 1][3] & tr[p << 1 | 1][2]));
42
  tr[p][3] = ((tr[p << 1][2] & (~tr[p << 1 | 1][3])) | (tr[p << 1][3] & tr[p << 1 | 1][3]));
43
}
44

45
inline pair <ll , ll> merge(pair <ll , ll> ls , pair <ll , ll> rs , bool t = 0){
46
  pair <ll , ll> ret;
47
  if(t) swap(ls , rs);
48
  ret.first  = ((rs.first & (~ls.first )) | (rs.second & ls.first ));
49
  ret.second = ((rs.first & (~ls.second)) | (rs.second & ls.second));
50
  return ret;
51
}
52

53
void init(int p , int l , int r){
54
  if(l == r){
55
    tr[p][0] = 0; tr[p][1] = ~(ll)0;
56
    if(w[l].first == 1) tr[p][0] &= w[l].second , tr[p][1] &= w[l].second;
57
    if(w[l].first == 2) tr[p][0] |= w[l].second , tr[p][1] |= w[l].second;
58
    if(w[l].first == 3) tr[p][0] ^= w[l].second , tr[p][1] ^= w[l].second;
59
    tr[p][2] = tr[p][0]; tr[p][3] = tr[p][1];
60
    return ;
61
  }
62
  int mid = (l + r) >> 1;
63
  init(p << 1 , l , mid);
64
  init(p << 1 | 1 , mid + 1 , r);
65
  pushup(p);
66
}
67

68
void upd(int p , int l , int r , int x , pair <int , ll> y){
69
  if(l > x || r < x) return ;
70
  if(l == r){
71
    tr[p][0] = 0; tr[p][1] = ~(ll)0;
72
    if(y.first == 1) tr[p][0] &= y.second , tr[p][1] &= y.second;
73
    if(y.first == 2) tr[p][0] |= y.second , tr[p][1] |= y.second;
74
    if(y.first == 3) tr[p][0] ^= y.second , tr[p][1] ^= y.second;
75
    tr[p][2] = tr[p][0]; tr[p][3] = tr[p][1];
76
    return ;
77
  }
78
  int mid = (l + r) >> 1;
79
  upd(p << 1 , l , mid , x , y);
80
  upd(p << 1 | 1 , mid + 1 , r , x , y);
81
  pushup(p);
82
}
83

84
pair <ll , ll> query(int p , int l , int r , int x , int y,  int k = 0){
85
  if(l >= x && r <= y) return {tr[p][k] , tr[p][1 + k]};
86
  int mid = (l + r) >> 1;
87
  if(y <= mid) return query(p << 1 , l , mid , x , y , k);
88
  if(x >  mid) return query(p << 1 | 1 , mid + 1 , r , x , y , k);
89
  return merge(
90
    query(p << 1 , l , mid , x , y , k) ,
91
    query(p << 1 | 1 , mid + 1 , r , x , y , k) ,
92
    (k > 0)
93
  );
94
}
95

96
inline pair <ll , ll> getans(int x , int y){
97
  pair <ll , ll> ret1 , ret2 , ret3;
98
  bool f1 = 1 , f2 = 1;
99
  while(tp[x] != tp[y]){
100
    if(dep[tp[x]] >= dep[tp[y]]){
101
      if(f1) ret1 = query(1 , 1 , n , id[tp[x]] , id[x] , 2) , f1 = 0;
102
      else ret1 = merge(ret1 , query(1 , 1 , n , id[tp[x]] , id[x] , 2));
103
      x = fa[tp[x]];
104
    }
105
    else{
106
      if(f2) ret2 = query(1 , 1 , n , id[tp[y]] , id[y]) , f2 = 0;
107
      else ret2 = merge(query(1 , 1 , n , id[tp[y]] , id[y]) , ret2);
108
      y = fa[tp[y]];
109
    }
110
  }
111
  if(dep[x] < dep[y]) ret3 = query(1 , 1 , n , id[x] , id[y]);
112
  else ret3 = query(1 , 1 , n , id[y] , id[x] , 2);
113
  if(f1 && f2) return ret3;
114
  if(f1) return merge(ret3 , ret2);
115
  if(f2) return merge(ret1 , ret3);
116
  return merge(merge(ret1 , ret3) , ret2);
117
}
118

119
int main(void){
120
  scanf("%d%d%d" , &n , &m , &k);
121
  for(int i = 1;i <= n;i++) scanf("%d%llu" , &a[i].first , &a[i].second);
122
  for(int i = 1 , u , v;i < n;i++){
123
    scanf("%d%d" , &u , &v);
124
    g[u].push_back(v);
125
    g[v].push_back(u);
126
  }
127
  dfs1(1 , 0 , 1); dfs2(1 , 1);
128
  init(1 , 1 , n);
129
  while(m--){
130
    int op , x , y; ll z;
131
    scanf("%d%d%d%llu" , &op , &x , &y , &z);
132
    if(op == 1){
133
      pair <ll , ll> ret = getans(x , y);
134
      ll ans = 0 , nw = 0;
135
      for(int i = k - 1;i >= 0;i--){
136
        bool a0 = (ret.first  >> i & 1ull);
137
        bool a1 = (ret.second >> i & 1ull);
138
        if(a0) ans |= ((ll)1 << i);
139
        else if(a1 && (nw | ((ll)1 << i)) <= z){
140
          ans |= ((ll)1 << i);
141
          nw |= ((ll)1 << i);
142
        }
143
      }
144
      printf("%llu\n" , ans);
145
    }
146
    if(op == 2)
147
      upd(1 , 1 , n , id[x] , {y , z});
148
  }
149
}

P9631

一操作简单区间取最值不说，重点在二操作，有个结论，我不会证，，，就是这种游戏下，如果异或和为 0 则先手必输。

于是可以先维护区间异或和，然后尽量让第二步的人的异或和为 0，这样就是必胜的了。

因为是拿，于是要满足 $a_i\oplus x \le a_i$ 的才可以拿，算这玩意有几个即可。

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5

6
int lz[800005];
7

8
struct Seg {
9
  int mi , cntmi , mi2 , ans;
10
  int tot[31];
11
  inline Seg(){ memset(tot , 0 , sizeof(tot)); }
12
  inline friend Seg operator + (Seg ls , Seg rs){
13
    Seg ret;
14
    ret.ans = (ls.ans ^ rs.ans);
15
    if(ls.mi < rs.mi){
16
      ret.mi = ls.mi; ret.cntmi = ls.cntmi;
17
      ret.mi2 = min(ls.mi2 , rs.mi);
18
    }
19
    else if(ls.mi > rs.mi){
20
      ret.mi = rs.mi; ret.cntmi = rs.cntmi;
21
      ret.mi2 = min(ls.mi , rs.mi2);
22
    }
23
    else{
24
      ret.mi = ls.mi; ret.cntmi = ls.cntmi + rs.cntmi;
25
      ret.mi2 = min(ls.mi2 , rs.mi2);
26
    }
27
    for(int i = 0;i <= 30;i++) ret.tot[i] = ls.tot[i] + rs.tot[i];
28
    return ret;
29
  }
30
  inline void operator += (int x){
31
    if(cntmi & 1) ans ^= mi ^ x;
32
    for(int i = 0;i <= 30;i++) if(mi >> i & 1)
33
      tot[i] -= cntmi;
34
    mi = x;
35
    for(int i = 0;i <= 30;i++) if(mi >> i & 1)
36
      tot[i] += cntmi;
37
  }
38
}tr[800005];
39

40
inline void upd(int p , int x){ tr[p] += x; lz[p] = x; }
41

42
inline void pushdown(int p){
43
  if(!lz[p]) return ;
44
  int mi = min(tr[p << 1].mi , tr[p << 1 | 1].mi);
45
  if(tr[p << 1].mi == mi) upd(p << 1 , lz[p]);
46
  if(tr[p << 1 | 1].mi == mi) upd(p << 1 | 1 , lz[p]);
47
  lz[p] = 0;
48
}
49

50
void upd_max(int p , int l , int r , int x , int y , int k){
51
  if(l > y || r < x || tr[p].mi >= k) return ;
52
  if(l >= x && r <= y && tr[p].mi2 > k){
53
    upd(p , k);
54
    return ;
55
  }
56
  int mid = (l + r) >> 1;
57
  pushdown(p);
58
  upd_max(p << 1 , l , mid , x , y , k);
59
  upd_max(p << 1 | 1 , mid + 1 , r , x , y , k);
60
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
61
}
62

63
Seg query(int p , int l , int r , int x , int y){
64
  if(l >= x && r <= y) return tr[p];
65
  int mid = (l + r) >> 1;
66
  pushdown(p);
67
  if(y <= mid) return query(p << 1 , l , mid , x , y);
68
  if(x > mid) return query(p << 1 | 1 , mid + 1 , r , x , y);
69
  return (
70
    query(p << 1 , l , mid , x , y) +
71
    query(p << 1 | 1 , mid + 1 , r , x , y)
72
  );
73
}
74

75
int a[200005];
76
void init(int p , int l , int r){
77
  if(l == r){
78
    tr[p].mi = tr[p].ans = a[l];
79
    tr[p].cntmi = 1; tr[p].mi2 = (1 << 30);
80
    for(int i = 0;i <= 30;i++) if(a[l] >> i & 1)
81
      tr[p].tot[i]++;
82
    return ;
83
  }
84
  int mid = (l + r) >> 1;
85
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
86
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
87
}
88

89
int n , q;
90

91
int main(void){
92
  scanf("%d%d" , &n , &q);
93
  for(int i = 1;i <= n;i++) scanf("%d" , &a[i]);
94
  init(1 , 1 , n);
95
  while(q--){
96
    int op , l , r , x;
97
    scanf("%d%d%d%d" , &op , &l , &r , &x);
98
    if(op == 1) upd_max(1 , 1 , n , l , r , x);
99
    if(op == 2){
100
      Seg ans = query(1 , 1 , n , l , r);
101
      ans.ans ^= x;
102
//      printf("w%d\n" , ans.ans);
103
      int t = -1;
104
      for(int i = 30;i >= 0;i--) if(ans.ans >> i & 1){ t = i; break; }
105
      if(t == -1) puts("0");
106
      else printf("%d\n" , ans.tot[t] + (x >> t & 1));
107
    }
108
  }
109
}

P5524 Ynoi 2012 NOIP2015充满了希望

交换

推平

查询

给你操作，问顺序执行 $[l,r]$ 的操作后所有查询操作的和。

$n,m,q\le 10^6$ 。

我们用线段树记录每个点最后一次执行的二操作的序号。

对于一操作，也是交换。

对于二操作，还是区间推平。

对于三操作，贡献即为 $v_{t_i}$ 。

那么将询问离线。枚举 $r$ ，维护 $s_i$ 表示 $[i,r]$ 之间的答案，移动方法如上，需要单点查询，区间加，可以用树状数组。于是做完了。

代码还没写。

扫描线

参考：https://www.luogu.com.cn/article/9vwv8pe7

答案贡献类

可以考虑每个点要区间满足什么要求使得这个点可以对答案做贡献

常用技巧：

lxl《树套堆》

区间取min，撤销第 i 次操作，求单点值。

如题，树套堆。线段树每个节点维护一个堆，然后标记永久化。

$O(\log^2 n)$ 。

1
#include <cstdio>
2
#include <queue>
3
#include <algorithm>
4
using namespace std;
5

6
const int inf = 1e9;
7

8
struct Zbojin_Queue {
9
  priority_queue <int , vector <int> , greater <int> > q , death;
10
  inline void push(int x){ q.push(x); }
11
  inline void erase(int x){ death.push(x); }
12
  inline int top(){
13
    while(!death.empty() && q.top() == death.top())
14
      q.pop() , death.pop();
15
    return q.empty()? inf : q.top();
16
  }
17
}qwq[2000005];
18

19
void upd(int p , int l , int r , int x , int y , int k){
20
  if(r < x || l > y) return ;
21
  if(l >= x && r <= y){
22
    if(k > 0) qwq[p].push(k);
23
    else    qwq[p].erase(-k);
24
    return ;
25
  }
26
  int mid = (l + r) >> 1;
27
  upd(p << 1 , l , mid , x , y , k);
28
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
29
}
30

31
int getmin(int p , int l , int r , int x){
32
  if(l > x || r < x) return inf;
33
  int ret = qwq[p].top();
34
  if(l == r) return ret;
35
  int mid = (l + r) >> 1;
36
  return min(ret , min(
37
    getmin(p << 1 , l , mid , x) ,
38
    getmin(p << 1 | 1 , mid + 1 , r , x)
39
  ));
40
}
41

42
int main(void){
43
}

这个方法也可以用在：

区间推平，区间撤销推平

只需要把值变成 pair，第一个值是操作时间，第二个是推平的值。

然后因为是 pair，所以堆（大根堆）顶的值一定是时间最大的，也就是最近推平的。删除同理。

其实因为插入是按时间顺序的，因此可以用栈来代替。时间复杂度少个 log。

如果用栈，建议用手写的，由于不知名原因，用 STL 的 stack 空间太大了。。。。

例题

CF522D Closest Equals

注意到，显然只有最近的两个相同的点才能对答案做贡献，并且答案区间要包含这两个点，即 $l\le i, j \le r$ ，用上面的树套堆维护扫描线即可。

code

CF1000F One Occurrence

记 $pre_i,nxt_i$ ，为 $i$ 前一个相同和后一个相同的。假如要点 $x$ 有贡献，那么区间必须满足 $l>pre_x,r<nxt_x$ ，扫描线维护即可。

code

CF453E Little Pony and Lord Tirek

假如 $a_i$ 均为 $0$ ，可以算出这个点最小需要几时才能到最大值，记为 $f_i$ ，那么容易想到用珂朵莉树维护修改的时间，于是就有多个连续块。

令 $t$ 为每个块的时间差，然后每个点分两种情况：

$t>f_i$ ：这个点为 $m_i$ 。
$t \le f_i$ ：这个点为 $tr_i$ 。

可以预先把每个点放到两个二维平面上， $x$ 轴代表 $i$ ， $y$ 轴代表 $f$ ，坐标则为 $(i,f_i)$ ，权值为 $m_i$ 或 $r_i$ 。

那么每次询问相当于求第一个二维平面 $[l,t+1,r,MAX]$ 矩形的和，加上第二个二维平面 $[l,1,r,t]$ 矩形的和。于是离线下来扫描线，扫描线可以用树状数组比较快。

然后是 $a_i\not = 0$ 时，只需要在第一次修改时暴力处理，由于修改一次后都为 $0$ ，所以时间复杂度不会增加。

code

题解

时间扫描类

常用技巧：时光倒流。

例题

P3863 序列

区间加，求 i 点之前有几个时刻的值大于 y

实现以时间和下标建系，修改是区间加，查询是区间排名，分块。

1
#include <cstdio>
2
#include <vector>
3
#include <algorithm>
4
using namespace std;
5
typedef long long ll;
6

7
int n , m; ll a[100005];
8

9
char buf[1 << 21] , *p1 , *p2;
10
#define GC p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 1 << 21 , stdin) , p1 == p2) ? EOF : *p1++
11
inline int read() {
12
  int x = 0;
13
    bool f = false;
14
  char ch = GC;
15
  while(ch > '9' || ch < '0'){
16
        if(ch == '-')
17
            f = true;
18
        ch = GC;
19
    }
20
  while(ch >= '0' && ch <= '9'){
21
    x = (x << 1) + (x << 3) + (ch ^ 48);
22
    ch = GC;
23
  }
24
  return f? -x : x;
25
}
26

27
namespace LOVE {
28
  const int kuai = 220;
29
  int L[(100005 / kuai) + 5] , R[(100005 / kuai) + 5] , id[100005];
30
  ll b[100005] , lz[(100005 / kuai) + 5];
31

32
  inline void add(int l , int r , int x){
33
    const int st = id[l] , ed = id[r];
34
    if(st == ed){
35
      for(int i = l;i <= r;i++) a[i] += x;
36
      for(int i = L[st];i <= R[st];i++) b[i] = a[i];
37
      sort(b + L[st] , b + R[st] + 1);
38
      return ;
39
    }
40
    for(int i = l;i <= R[st];i++) a[i] += x;
41
    for(int i = L[st];i <= R[st];i++) b[i] = a[i];
42
    sort(b + L[st] , b + R[st] + 1);
43
    for(int i = st + 1;i < ed;i++) lz[i] += x;
44
    for(int i = L[ed];i <= r;i++) a[i] += x;
45
    for(int i = L[ed];i <= R[ed];i++) b[i] = a[i];
46
    sort(b + L[ed] , b + R[ed] + 1);
47
  }
48

49
  inline int query(int l , int r , ll x){
50
    const int st = id[l] , ed = id[r];
51
    int ret = 0;
52
    if(st == ed){
53
      for(int i = l;i <= r;i++) ret += (a[i] + lz[st] >= x);
54
      return ret;
55
    }
56
    for(int i = l;i <= R[st];i++) ret += (a[i] + lz[st] >= x);
57
    for(int i = st + 1;i < ed;i++)
58
      ret += (R[i] + b + 1 - lower_bound(b + L[i] , b + R[i] + 1 , x - lz[i]));
59
    for(int i = L[ed];i <= r;i++) ret += (a[i] + lz[ed] >= x);
60
    return ret;
61
  }
62

63
  inline void init(){
64
    const int N = m / kuai + 1;
65
    for(int i = 1;i <= N;i++){
66
      L[i] = R[i - 1] + 1;
67
      R[i] = min(R[i - 1] + kuai , m + 1);
68
      for(int j = L[i];j <= R[i];j++) id[j] = i;
69
    }
70
  }
71
}
72

73
struct QWQ { int l , r , k , id; };
74
vector <QWQ> u[100005] , q[100005];
75
int ans[100005];
76

77
int main(void){
78
  n = read(); m = read();
79
  for(int i = 1 , x , lt = 0;i <= n;i++){
80
    x = read();
81
    u[i].push_back((QWQ){0 , m , x - lt , 0});
82
    lt = x;
83
  }
84
  LOVE::init();
85
  int nw = 0;
86
  for(int i = 1;i <= m;i++){
87
    int op , l , r; op = read(); l = read(); r = read();
88
    if(op == 1){
89
      int x; x = read();
90
      u[l].push_back((QWQ){i , m , x , 0});
91
      u[r + 1].push_back((QWQ){i , m , -x , 0});
92
    }
93
    if(op == 2){
94
      q[l].push_back((QWQ){0 , i - 1 , r , ++nw});
95
    }
96
  }
97
  for(int i = 0;i <= n;i++){
98
    for(QWQ j : u[i]) LOVE::add(j.l + 1 , j.r + 1 , j.k);
99
    for(QWQ j : q[i]) ans[j.id] = LOVE::query(j.l + 1 , j.r + 1 , j.k);
100
  }
101
  for(int i = 1;i <= nw;i++) printf("%d\n" , ans[i]);
102
}

常用转换

通过前两节的转换后，查询/修改操作经常可能在二维平面上显示出阶梯状的图像，如三角形、平行四边形。这个是很头疼的。以下有几种解决方法，但是一般都要根据题目特殊设计，所以我们通过例题来讲解

P15133 [ROIR 2026] 最后的滑动窗口问题

1. 无三角

考虑每个数何时可以成为最小值，放到 l r 的平面直角坐标系中，就是一块矩形，这时，题目的查询就是一条斜率为 1 的直线，这是不好的。所以换个坐标系，纵轴是 k，横轴是 l。那么每个数的贡献区域是平行四边形，查询是平行于 x 轴的直线，如图：

首先可以做一次差分：平行四边（粉）= 绿-蓝-红-红蓝重叠部分。

因为这四个部分都有相似的形状，于是只需要求这个形状的东西（红色部分）：

为了便于求解，我们再做一次差分，蓝色部分是易求的，问题变成求红+蓝色部分。此时显然又要转换坐标系了，有一个重要的观察：由于查询是平行于 x 轴的直线，所以原坐标系同一行的点在新坐标系中仍连续并在同一行；原坐标系唯一不好处理的是左边的倒三角。综上考虑，我们可以构建出如下新坐标系：

灰色代表原始坐标系合法点的范围，橙色平行四边形是新坐标系。浅绿色区域是要求的部分，深绿区域则是在新坐标系中浅绿的对应部分。不难发现，橙色以外的区域是不合法的，即使加了，也不会影响答案，所以我们利用这些区域，给深绿色部分补全成一个矩形，如图紫色部分所示。

然后扫描线，开两个树状数组（要实现区间加、区间查询），分别维护这两个坐标系 y=i 时，x 轴的值，其中 i 是从下往上枚举的。从图形理解，就是一条线从下往上扫。

2. 直角三角形

这个方法的拆分会涉及到直角三角形。下面我直接一图流，方法和上文是类似的，就当作课后思考题吧！

上面一行是要分平行四边形情况讨论的拆分方法，下一行唯一的一个是无需讨论的。总共有三种拆分方法，右下角我画出了两种直角三角形的处理办法。

致谢&参考文献

浅谈扫描线 Larry76

论文《区间最值操作与历史最值问题》——吉如一

区间最值操作与区间历史最值详解灵梦

https://www.luogu.me/article/rqmfqvmu

https://www.cnblogs.com/Meatherm/p/17925813.html#:~

lxl 的课件。

oi-wki 等

感谢 fen sir 对我线段树标题的评论

感谢冯某对我NOIP 2022 比赛解答。

感谢线段树对本文的大力支持。

回波