我喜欢打线段树。

特别是动态开点线段树。每一次与线段树相见，我总觉得是受了上天的眷顾与恩惠。

那些动态开点线段树，114、514年地活在世上，那要经历多少、怎样的时光？

打线段树，线段树当然不会改变，但看打得久了，打线段树的人不由自主地有了变化——把自己看成了一棵线段树。

线段树不再是“他”，而在不知不觉中变成了“你”。

线段树已经成为独特的具体，有他的前世今生，成了相对于我的“你”。线段树也有自我意识吧，那样，我也可以妄想成为线段树的“你”，我和你！我用眼睛听你，用耳朵看你，用“心”换意念，去揣摩你。

想当年，不知是何人栽下了你，或者只是IOer遗落了一粒灵感、无心长成了你？1e114514199810谔谔年来，你经历了太多的朝代更迭，多少TLE、MLE，那都不算什么。

多少WA、TLE、OLE、MLE、UKE，你是怎么活下来的？此处在Luogu，古代应该人迹罕至、人为破坏不易。TLE因旁有n<=1e8，T掉你的机会减少；扎根处在宽阔的Luogu，MLE不能把你卡。

“高坡OJ上，尽是毒瘤翁。人人尽怀卡常意，不见AC映屏幕绿”，你是怎样幸运地一次次躲过了UKE之灾？

根仍在汲取，叶仍在吐纳，题面和数据一定是永不停歇地和你进行着交流互动。

“南方水阔，北地风多”，一年又一年风的OLE，都未能拿你奈何。

四周山峦逶迤，线段树木葱茏，long long 来过，线段树声哼吼，贯通肺腑。懂线段树的朋友说，这里一定有充足的评测资源，你四处探路的根须早已与CPU接通，至少1e114514199810谔谔年来从未枯竭。

古线段树从来不是孤独的，你一定不是单个的存在。

这里的线段树活得长，有风气、有遗传。在树状树祖直线距离不到两公里的地方还有一棵年龄相仿的线段树。大慨是在历史上受了unsigned long long，那棵线段树只有半个部分还活着，活着的半个部分倒也是生机盎然。

时间虽然已经过去了1e114514199810谔谔年，这样的情形似乎以后也不会改变。想象你们的未来，我有担忧，居然也有信心。

主要参考：lxl 课件

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

其实硬要把线段树和扫描线分开是不可能的，这就是「我中有你，你中有我」。

因此这里例题放那边实际上是重点偏向哪边，并不是不用另一方的。

线段树#

标记信息的设计#

本节参考：

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

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

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

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

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

例：小白

单点加

区间查最大子段和

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

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

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

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

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

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

15
struct Seg {
16
  //信息
17
  inline friend Seg operator + (Seg ls , Seg rs){
18
    //标记作用标记
19
  }
20
  inline void operator += (Tag t){
21
    //标记作用信息
22
  }
23
}tr[400005];
24

25
inline void pushdown(int p){
26
  if(){ //判断标记非空
27
    tr[p << 1] += tag[p]; tr[p << 1 | 1] += tag[p];
28
    tag[p << 1] += tag[p]; tag[p << 1 | 1] += tag[p];
29
    tag[p] = Tag();
30
  }
31
}
32

33
void init(int p , int l , int r){
34
  if(l == r){ return ; }
35
  int mid = (l + r) >> 1;
36
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
37
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
38
}
39

40
void upd(int p , int l , int r , int x , int y , Tag k){
41
  if(l > y || r < x) return ;
42
  if(l >= x && r <= y){ tr[p] += k; tag[p] += k; return ; }
43
  int mid = (l + r) >> 1;
44
  pushdown(p);
45
  upd(p << 1 , l , mid , x , y , k);
46
  upd(p << 1 | 1 , mid + 1 , r , x , y , k);
47
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
48
}
49

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

从扫描线到历史版本和#

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

一般的这种题，可以考虑将 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$ 的值。

？？？赋值怎么测回。

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

8
int T , n , a[250005] , b[250005];
9
int la[250005] , ra[250005] , lb[250005] , rb[250005];
10
ll ans[250005];
11

12
struct Seg { ll s , xy , x , y; }tr[1000005];
13

14
struct Tag { ll tx , ty , adx , ady , adxy , adc; }tag[1000005];
15

16
inline void pushup(int p){ //信息+信息
17
  tr[p].s = tr[p << 1].s + tr[p << 1 | 1].s;
18
  tr[p].xy = tr[p << 1].xy + tr[p << 1 | 1].xy;
19
  tr[p].x = tr[p << 1].x + tr[p << 1 | 1].x;
20
  tr[p].y = tr[p << 1].y + tr[p << 1 | 1].y;
21
}
22

23
inline void tag_info(Seg &ret , Tag t , int le){ //标记作用信息
24
  ret.s += ret.xy * t.adxy + ret.x * t.adx + ret.y * t.ady + le * t.adc;
25
  if(t.tx && t.ty){
26
    ret.xy = le * t.tx * t.ty;
27
    ret.x = le * t.tx;
28
    ret.y = le * t.ty;
29
  }
30
  else if(t.tx){
31
    ret.xy = ret.y * t.tx;
32
    ret.x = le * t.tx;
33
  }
34
  else if(t.ty){
35
    ret.xy = ret.x * t.ty;
36
    ret.y = le * t.ty;
37
  }
38
}
39

40
inline void tag_tag(Tag &ret , Tag t){ //标记作用标记
41
  if(ret.tx && ret.ty){
42

43
  }
44
  else if(ret.tx){
45

46
  }
47
  else if(ret.ty){
48

49
  }
50
  else{
51
    ret.adx += t.adx;
52
    ret.ady += t.ady;
53
    ret.adxy += t.adxy;
54
    ret.adc += t.adc;
55
  }
56
  if(t.tx) ret.tx = t.tx;
57
  if(t.ty) ret.ty = t.ty;
58
}
59

60
struct Line {
61
  int x , y1 , y2 , k , id;
62
  bool operator < (const Line &b) const {
63
    if(x == b.x){
64
      if(id < 0 && b.id < 0) return k < b.k;
65
      else return id > b.id;
66
    }
67
    return x < b.x;
68
  }
69
}qwq[1000005]; int cnt;
70

71
inline void init(){
72
  stack <pair <int , int> > tmp;
73
  scanf("%d%d" , &T , &n);
74
  for(int i = 1;i <= n;i++){
75
    scanf("%d" , &a[i]);
76
    while(!tmp.empty() && tmp.top().first < a[i]) tmp.pop();
77
    if(!tmp.empty()) la[i] = tmp.top().second;
78
    tmp.push(make_pair(a[i] , i));
79
  }
80
  while(!tmp.empty()) tmp.pop();
81
  for(int i = 1;i <= n;i++){
82
    scanf("%d" , &b[i]);
83
    while(!tmp.empty() && tmp.top().first < b[i]) tmp.pop();
84
    if(!tmp.empty()) lb[i] = tmp.top().second;
85
    tmp.push(make_pair(b[i] , i));
86
  }
87
  for(int i = 1;i <= n;i++){
88
    qwq[++cnt] = (Line){i , la[i] + 1 , i , a[i] , -1};
89
    qwq[++cnt] = (Line){i , lb[i] + 1 , i , b[i] , -2};
90
  }
91
  scanf("%d" , &T);
92
  for(int i = 1 , l , r;i <= T;i++){
93
    scanf("%d%d" , &l , &r);
94
    qwq[++cnt] = (Line){l , l , r , -1 , i};
95
    qwq[++cnt] = (Line){r + 1 , l , r , 1 , i};
96
  }
97
}
98

99
int main(void){
100
  init();
101
//  printf("qw%llu\n" , (ll)(-1) * query(1 , 1 , n , 1 , 2));
102
//  tr[1].updad(1);
103
//  upd2(1 , 1 , n , 1 , 1 , 1);
104
//  upd1(1 , 1 , n , 1 , 1 , 2);
105
//  tr[1].updad(1);
106
//  printf("qw%llu\n" , query(1 , 1 , n , 1 , 2));
107
//  upd2(1 , 1 , n , 1 , 2 , 2);
108
//  upd1(1 , 1 , n , 2 , 2 , 1);
109
//  tr[1].updad(1);
110
//  printf("qw%llu\n" , (ll)(1) * query(1 , 1 , n , 1 , 2));
111
//  return 0;
112
  sort(qwq + 1 , qwq + 1 + cnt);
113
  for(int i = 1;i <= cnt;i++){
114
    printf("%d %d %d %d %d\n" , qwq[i].x , qwq[i].k , qwq[i].y1 , qwq[i].y2 , qwq[i].id);
115
    if(qwq[i].x != qwq[i - 1].x) tr[1].updad(qwq[i].x - qwq[i - 1].x);
116
    if(qwq[i].id < 0){
117
      if(qwq[i].id == -1) upd1(1 , 1 , n , qwq[i].y1 , qwq[i].y2 , qwq[i].k);
118
      if(qwq[i].id == -2) upd2(1 , 1 , n , qwq[i].y1 , qwq[i].y2 , qwq[i].k);
119
    }
120
    else{
121
      ans[qwq[i].id] += (ll)qwq[i].k * query(1 , 1 , n , qwq[i].y1 , qwq[i].y2);
122
      printf("%llu\n" , (ll)qwq[i].k * query(1 , 1 , n , qwq[i].y1 , qwq[i].y2));
123
    }
124

125
  }
126
  for(int i = 1;i <= T;i++) printf("%llu\n" , ans[i]);
127
}

我已从 CPU 大成归来。

冯sir 说不需要撤回，于是问题变成：

$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
//void print(int p , int l , int r){
93
//  printf("(%d %d %d)%llu %llu\n" , p , l , r , tr[p].xy , tr[p].s);
94
//  if(l == r) return ;
95
//  int mid = (l + r) >> 1;
96
//  pushdown(p);
97
//  print(p << 1 , l , mid); print(p << 1 | 1 , mid + 1 , r);
98
//  tr[p] = tr[p << 1] + tr[p << 1 | 1];
99
//}
100

101
int T , n , a[250005] , b[250005] , la[250005] , lb[250005];
102

103
struct QWQ { int l , r , k , op; };
104
vector <QWQ> chm[250005] , qqq[250005];
105

106
ll ans[250005];
107

108

109

110
int main(void){
111
  scanf("%d%d" , &T , &n);
112
  init(1 , 1 , n);
113
  stack <pair <int , int> > tmp;
114
  for(int i = 1;i <= n;i++){
115
    scanf("%d" , &a[i]);
116
    while(!tmp.empty() && tmp.top().first < a[i]) tmp.pop();
117
    if(!tmp.empty()) la[i] = tmp.top().second;
118
    tmp.push(make_pair(a[i] , i));
119
  }
120
  while(!tmp.empty()) tmp.pop();
121
  for(int i = 1;i <= n;i++){
122
    scanf("%d" , &b[i]);
123
    while(!tmp.empty() && tmp.top().first < b[i]) tmp.pop();
124
    if(!tmp.empty()) lb[i] = tmp.top().second;
125
    tmp.push(make_pair(b[i] , i));
126
  }
127
  for(int i = 1;i <= n;i++){
128
    chm[i].push_back((QWQ){la[i] + 1 , i , a[i] , 0});
129
    chm[i].push_back((QWQ){lb[i] + 1 , i , b[i] , 1});
130
  }
131
  scanf("%d" , &T);
132
  for(int i = 1 , l , r;i <= T;i++){
133
    scanf("%d%d" , &l , &r);
134
    qqq[l - 1].push_back((QWQ){l , r , -1 , i});
135
    qqq[r].push_back((QWQ){l , r , 1 , i});
136
  }
137
  for(int i = 1;i <= n;i++){
138
    for(QWQ j : chm[i]){
139
      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));
140
      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));
141
    }
142
//    printf("%llu %llu\n" , tr[1].xy , tr[1].s);
143
    upd(1 , 1 , n , 1 , n , Tag(1 , 0 , 0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0));
144
//    printf("%llu %llu\n" , tr[1].xy , tr[1].s);
145
//    print(1 , 1 , n);
146
    for(QWQ j : qqq[i])
147
      ans[j.op] += j.k * query(1 , 1 , n , j.l , j.r).s;
148
  }
149
  for(int i = 1;i <= T;i++) printf("%llu\n" , ans[i]);
150
}
151

152
//inline Tag(ll a1 , ll a2 , ll a4 , ll a5 , ll a7 , ll a8): k11(a1) , k12(a2) , k21(a4) , k22(a5) , k31(a7) , k32(a8

P3246 序列#

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

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

比如有 $5,2,4,1 ,3$ ，那么：

5 2 4 1 3 5 2 2 1 1

2 4 1 3 2 2 1 1

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

3
     1 3                          1 1
4

5
        3                             3

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

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

设 $pre,nxt$ 意思显然

因此每个矩形就是 $[pre + 1 , i , i , nxt - 1]$ ，

由于是直接覆盖的，nxt 不需要考虑

pre 用单调栈即可，后面的用扫描线离线做。

于是问题变成：

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
//  inline void operator += (Tag x){
34
//    mi += x.ad;
35
//    ans += 1LL * cntmi * x.tg;
36
//  }
37
}tr[480005];
38

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

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

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

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

76
void init(int p , int l , int r){
77
  if(l == r){ tr[p].cntmi = 1; return ; }
78
  int mid = (l + r) >> 1;
79
  init(p << 1 , l , mid); init(p << 1 | 1 , mid + 1 , r);
80
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
81
}
82

83
int n , m , p[120005];
84
int lx[120005] , rx[120005] , li[120005] , ri[120005];
85

86
struct QWQ { int l , r , k , id; };
87
vector <QWQ> u[120005] , q[120005];
88

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

104
long long ans[120005];
105

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

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)$ 。

然后如果加上区间加的操作，实现类似，复杂度变为 $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
}

盟誓的文艺复兴#

this

区间取最值，区间求有几个子区间的最大值等于大区间的最大值。

我之前出的，很水，其实重点在三操作，不过三操作也简单。不说。

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

6
int id , T;
7
int a[100005];
8
int n , m;
9
const int inf = 0x7fffffff;
10

11
struct Tree {
12
  int maxn , maxsum , secondmax;
13
  int minn , secondmin;
14
  pair <int , int > mintag , maxtag;
15
  ll twt;
16
  int maxl , maxr;
17
  inline void min_upd(pair <int , int> t){
18
    if(t.first < maxn){
19
      if(secondmin == maxn)
20
        secondmin = t.first;
21
      maxn = t.first;
22
      if(secondmax == -inf)
23
        minn = t.first;
24
      mintag = t;
25
    }
26
  }
27
  inline void max_upd(pair <int , int> t){
28
    if(t.first > minn){
29
      if(secondmax == minn)
30
        secondmax = t.first;
31
      minn = t.first;
32
      if(secondmin == inf)
33
        maxn = t.first;
34
      maxtag = t;
35
    }
36
  }
37
}qwq[400005];
38

39
inline ll square(int x){ return 1LL * x * x; }
40

41
inline Tree merge(int l , int r , int mid , Tree ls , Tree rs){
42
  Tree ret;
43
  ret.maxtag = ret.mintag = {-inf , 0};
44
  if(ls.maxn > rs.maxn){
45
    ret.maxn = ls.maxn;
46
    ret.maxsum = ls.maxsum;
47
    ret.secondmax = max(ls.secondmax , rs.maxn);
48
    ret.maxl = ls.maxl;
49
    ret.maxr = ls.maxr;
50
    ret.twt = (
51
      ls.twt - square(mid - ls.maxr) +
52
      square(r - ls.maxr)
53
    );
54
  }
55
  if(ls.maxn < rs.maxn){
56
    ret.maxn = rs.maxn;
57
    ret.maxsum = rs.maxsum;
58
    ret.secondmax = max(rs.secondmax , ls.maxn);
59
    ret.maxl = rs.maxl;
60
    ret.maxr = rs.maxr;
61
    ret.twt = (
62
      rs.twt - square(rs.maxl - mid - 1) +
63
      square(rs.maxl - l)
64
    );
65
  }
66
  if(ls.maxn == rs.maxn){
67
    ret.maxn = ls.maxn;
68
    ret.maxsum = ls.maxsum + rs.maxsum;
69
    ret.secondmax = max(ls.secondmax , rs.secondmax);
70
    ret.maxl = ls.maxl;
71
    ret.maxr = rs.maxr;
72
    ret.twt = (
73
      (ls.twt - square(mid - ls.maxr)) +
74
      (rs.twt - square(rs.maxl - mid - 1)) +
75
      square(rs.maxl - ls.maxr - 1)
76
    );
77
  }
78

79
  if(ls.minn < rs.minn){
80
    ret.minn = ls.minn;
81
    ret.secondmin = min(ls.secondmin , rs.minn);
82
  }
83
  if(ls.minn > rs.minn){
84
    ret.minn = rs.minn;
85
    ret.secondmin = min(rs.secondmin , ls.minn);
86
  }
87
  if(ls.minn == rs.minn){
88
    ret.minn = ls.minn;
89
    ret.secondmin = min(ls.secondmin , rs.secondmin);
90
  }
91
  return ret;
92
}
93

94
inline void pushdown(int p){
95
  if(qwq[p].mintag.first != -inf && qwq[p].maxtag.first != -inf){
96
    if(qwq[p].mintag.second < qwq[p].maxtag.second){
97
      qwq[p << 1].max_upd(qwq[p].maxtag);
98
      qwq[p << 1 | 1].max_upd(qwq[p].maxtag);
99
      qwq[p].maxtag = {-inf , 0};
100
      qwq[p << 1].min_upd(qwq[p].mintag);
101
      qwq[p << 1 | 1].min_upd(qwq[p].mintag);
102
      qwq[p].mintag = {-inf , 0};
103
    }
104
    else{
105
      qwq[p << 1].min_upd(qwq[p].mintag);
106
      qwq[p << 1 | 1].min_upd(qwq[p].mintag);
107
      qwq[p].mintag = {-inf , 0};
108
      qwq[p << 1].max_upd(qwq[p].maxtag);
109
      qwq[p << 1 | 1].max_upd(qwq[p].maxtag);
110
      qwq[p].maxtag = {-inf , 0};
111
    }
112
    return ;
113
  }
114
  if(qwq[p].mintag.first != -inf){
115
    qwq[p << 1].min_upd(qwq[p].mintag);
116
    qwq[p << 1 | 1].min_upd(qwq[p].mintag);
117
    qwq[p].mintag = {-inf , 0};
118
  }
119
  if(qwq[p].maxtag.first != -inf){
120
    qwq[p << 1].max_upd(qwq[p].maxtag);
121
    qwq[p << 1 | 1].max_upd(qwq[p].maxtag);
122
    qwq[p].maxtag = {-inf , 0};
123
  }
124
}
125

126
void init(int p , int l , int r){
127
  if(l == r){
128
    qwq[p].maxtag = qwq[p].mintag = {-inf , 0};
129
    qwq[p].maxn = qwq[p].minn = a[l];
130
    qwq[p].maxsum = 1;
131
    qwq[p].secondmax = -inf;
132
    qwq[p].secondmin = inf;
133
    qwq[p].maxl = qwq[p].maxr = l;
134
    qwq[p].twt = 0;
135
    return ;
136
  }
137
  int mid = (l + r) >> 1;
138
  init(p << 1 , l , mid);
139
  init(p << 1 | 1 , mid + 1 , r);
140
  qwq[p] = merge(l , r , mid , qwq[p << 1] , qwq[p << 1 | 1]);
141
}
142

143
void minupd(int p , int l , int r , int x , int y , int k){
144
  if(l > y || r < x)
145
    return ;
146
  if(k >= qwq[p].maxn)
147
    return ;
148
  if(l >= x && r <= y && k > qwq[p].secondmax){ //只改最�?
149
    if(qwq[p].maxn == qwq[p].secondmin)
150
      qwq[p].secondmin = k;
151
    qwq[p].maxn = k;
152
    if(qwq[p].secondmax == -inf)
153
      qwq[p].minn = k;
154
    qwq[p].mintag = {k , m};
155
    return ;
156
  }
157
  pushdown(p);
158
  int mid = (l + r) >> 1;
159
  minupd(p << 1 , l , mid , x , y , k);
160
  minupd(p << 1 | 1 , mid + 1 , r , x , y , k);
161
  qwq[p] = merge(l , r , mid , qwq[p << 1] , qwq[p << 1 | 1]);
162
}
163

164
void maxupd(int p , int l , int r , int x , int y , int k){
165
  if(l > y || r < x)
166
    return ;
167
  if(k <= qwq[p].minn)
168
    return ;
169
  if(l >= x && r <= y && k < qwq[p].secondmin){
170
    if(qwq[p].minn == qwq[p].secondmax)
171
      qwq[p].secondmax = k;
172
    qwq[p].minn = k;
173
    if(qwq[p].secondmin == inf)
174
      qwq[p].maxn = k;
175
    qwq[p].maxtag = {k , m};
176
    return ;
177
  }
178
  pushdown(p);
179
  int mid = (l + r) >> 1;
180
  maxupd(p << 1 , l , mid , x , y , k);
181
  maxupd(p << 1 | 1 , mid + 1 , r , x , y , k);
182
  qwq[p] = merge(l , r , mid , qwq[p << 1] , qwq[p << 1 | 1]);
183
}
184

185
Tree solve3(int p , int l , int r , int x , int y){
186
  if(l > y || r < x)
187
    return (Tree){0 , 0 , 0 , 0 , 0 , {0 , 0} , {0 , 0} , 0 , 0 , 0};
188
  // printf("twt%lld %d %d\n" , qwq[p].twt , l , r);
189
  if(l >= x && r <= y)
190
    return qwq[p];
191
  int mid = (l + r) >> 1;
192
  pushdown(p);
193
  Tree ls = solve3(p << 1 , l , mid , x , y);
194
  Tree rs = solve3(p << 1 | 1 , mid + 1 , r , x , y);
195
  if(ls.maxsum == 0)
196
    return rs;
197
  if(rs.maxsum == 0)
198
    return ls;
199
  return merge(max(x , l) , min(y , r) , mid , ls , rs); //
200
}
201

202
void DEBUG(int p , int l , int r){
203
  if(l == r){
204
    printf("%d " , qwq[p].maxn);
205
    return ;
206
  }
207
  pushdown(p);
208
  int mid = (l + r) >> 1;
209
  DEBUG(p << 1 , l , mid);
210
  DEBUG(p << 1 | 1 , mid + 1 , r);
211
}
212

213
inline int read() {
214
  int x = 0;
215
  bool f = false;
216
  char ch = getchar();
217
  while(ch > '9' || ch < '0'){
218
        if(ch == '-')
219
            f = true;
220
        ch = getchar();
221
  }
222
  while(ch >= '0' && ch <= '9'){
223
    x = (x << 1) + (x << 3) + (ch ^ 48);
224
    ch = getchar();
225
  }
226
  return f? -x : x;
227
}
228

229
int main(void){
230
  id = read(); T = read();
231
  while(T--){
232
    ll kkk = 0;
233
    n = read(); m = read();
234
    for(int i = 1;i <= n;i++) a[i] = read();
235
    init(1 , 1 , n);
236
    while(m--){
237
      int op , l , r , x , y;
238
      op = read(); l = read(); r = read();
239
      if(id & 1){
240
        l = ((1LL * l * l) ^ kkk) % n * 2333 % n + 1;
241
        r = ((1LL * r * r) ^ kkk) % n * 2024 % n + 1;
242
        if(l > r) swap(l , r);
243
      }
244
      if(op == 1){
245
        x = read();
246
        minupd(1 , 1 , n , l , r , x);
247
      }
248
      if(op == 2){
249
        x = read();
250
        maxupd(1 , 1 , n , l , r , x);
251
      }
252
      if(op == 3){
253
        Tree ret = solve3(1 , 1 , n , l , r);
254
        ll ans = 1LL * (r - l + 1) * (r - l + 2);
255
        ans -= ret.twt + (r - l + 1 - ret.maxsum);
256
        ans >>= 1;
257
        printf("%lld\n" , ans);
258
        kkk = ans;
259
      }
260
    }
261
  }
262
}

历史最值问题#

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

一般这种可以用 $(\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
//    printf("q%d %d %d\n" , l , r , tr[p].a);
75
    return ;
76
  }
77
  int mid = (l + r) >> 1;
78
  pushdown(p);
79
  add(p << 1 , l , mid , x , y , k);
80
  add(p << 1 | 1 , mid + 1 , r , x , y , k);
81
  tr[p] = tr[p << 1] + tr[p << 1 | 1];
82
}
83

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

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

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

122
int n , m;
123

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

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
//    if(l.k11 == 0 && l.k12 == -inf && l.k21 == -inf && l.k22 == -inf) return r;
19
    Tag ret;
20
    ret.k11 = Add(l.k11 , r.k11);
21
    ret.k12 = max(l.k12 , Add(l.k11 , r.k12));
22
    ret.k21 = max(Add(l.k21 , r.k11) , r.k21);
23
    ret.k22 = max(Add(l.k21 , r.k12) , max(l.k22 , r.k22));
24
    return ret;
25
  }
26
  inline void operator += (Tag x){ (*this) = (*this) + x; }
27
}lazy[400005];
28

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

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

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

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

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

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

SP1557 GSS2#

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

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

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

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

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

zkw 线段树#

这里仅提供模板。

1
int N;  //区间加，区间和。常数小。
2
ll qwq[400005] , lazy[400005];
3
inline void init(){
4
    N = 1;
5
    while(N < n + 2) N <<= 2;
6
    for(int i = 1;i <= n;i++) qwq[i + N] = a[i];
7
    for(int i = N - 1;i > 0;i--){
8
        qwq[i] = qwq[i << 1] + qwq[i << 1 | 1];
9
        lazy[i] = 0;
10
    }
11
}
12
inline ll query(int l , int r){
13
    int L , R , len , ln = 0 , rn = 0;
14
    ll ret = 0;
15
    for(L = N + l - 1 , R = N + r + 1 , len = 1;L ^ R ^ 1;L >>= 1 , R >>= 1 , len <<= 1){
16
        if(lazy[L]) ret += lazy[L] * ln;
17
        if(lazy[R]) ret += lazy[R] * rn;
18
        if(~L & 1) ret += qwq[L ^ 1] , ln += len;
19
        if( R & 1) ret += qwq[R ^ 1] , rn += len;
20
    }
21
    for(;L;L >>= 1 , R >>= 1){
22
        ret += lazy[L] * ln;
23
        ret += lazy[R] * rn;
24
    }
25
    return ret;
26
}
27
inline void add(int l , int r , ll x){
28
    int L , R , len , ln = 0 , rn = 0;
29
    for(L = N + l - 1 , R = N + r + 1 , len = 1;L ^ R ^ 1;L >>= 1 , R >>= 1 , len <<= 1){
30
        qwq[L] += x * ln;  qwq[R] += x * rn;
31
        if(~L & 1) lazy[L ^ 1] += x , qwq[L ^ 1] += x * len , ln += len;
32
        if( R & 1) lazy[R ^ 1] += x , qwq[R ^ 1] += x * len , rn += len;
33
    }
34
    for(;L;L >>= 1 , R >>= 1){
35
        qwq[L] += x * ln;
36
        qwq[R] += x * rn;
37
    }
38
}

选讲#

HDU6315（势能线段树）#

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

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

$n,m\le 10^5$

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

Ynoi P5354 由乃的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
}

P11334#

显然可以线段树，因为是可合并信息。

考虑每段区间维护最长等差数列长度，于是为了合并它，就需要再维护区间前缀最长等差数列长度，和后缀最长。而且合并时也需要判断是否能合并，所以还需要维护前缀等差数列和后缀等差数列的首尾项。（可以类比线段树维护最大子段和）

综上，需要维护五个值，区间内的答案，区间前缀最大，后缀最大，前缀等差数列，后缀等差数列。

代码特别难写。。考虑情况特别多。

long long 没开全，1打成2，推平应先下放，merge情况考虑少了，洛谷评测太慢了。

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(-10)#

假如 $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$ ，所以时间复杂度不会增加。

-1：没写完，交一发看看。
-2：调RE的问题，树状数组 $0$ 的会RE。。
-3~-6：加 $a_i\not =0$ 的情况，调。
-7&-8：数组开小。
-9&-10：long long&快读。

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
}

致谢&参考文献#

浅谈扫描线 Larry76

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

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

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

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

lxl 的课件。

oi-wki 等

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

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

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

QWQ_SenLin

线段树#

标记信息的设计#

从扫描线到历史版本和#

NOIP2022比赛#

P3246 序列#

CF997E & 猫猫贴贴#

P9990 Ynoi Easy Round 2023 TEST_90 & P10822#

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

区间最值操作#

最佳女选手#

盟誓的文艺复兴#

历史最值问题#

线段树3#

CPU监控#

SP1557 GSS2#

zkw 线段树#

选讲#

HDU6315（势能线段树）#

Ynoi P5354 由乃的OJ#

P11334#

P9631#

P5524 Ynoi 2012 NOIP2015充满了希望#

扫描线#

答案贡献类#

例题#

CF522D Closest Equals#

CF1000F One Occurrence#

CF453E Little Pony and Lord Tirek(-10)#

时间扫描类#

例题#

P3863 序列#

致谢&参考文献#