DataStructure

Posted on | Edited on | In | Views:

DataStructure

树

重心

对于一棵树来说，删去该树的重心后，所有的子树的大小不会超过原树大小的 $\large\frac 1 2$。树的重心还有一个性质，是相对于树上的其他点而言的，就是删去重心后形成的所有子树中最大的一棵节点数最少。换句话说，就是删去重心后生成的多棵子树是最平衡的。一棵树的重心至多有两个。
我们可以很容易的在一次DFS过程中求出所有节点的 $size$，即子树大小。我们每搜索完一个节点 u 的儿子 v，就判断 size[v] 是否大于 $\frac n 2$，然后在搜索完所有儿子后计算出本节点的 $size$，再判断 $n-size[u]$ 是否大于 n/2（ n-siz[u] 是节点 u 上面的连通块大小）即可求出重心，时间复杂度 O(n)。

直径

树上的最长路径，可以有多条。
法一：任取树中的一个节点x，找出距离它最远的点y，那么点y就是这棵树中一条直径的一个端点。我们再从y出发，找出距离y最远的点就找到了一条直径。对于树中的任一个点，距离它最远的点一定是树上一条直径的一个端点。
法二：定义F[i]表示从i出发向远离根节点的方向走的最长路径的长度，G[i]表示从i向远离根节点的方向走的次长路径的长度。注意F[i]和G[i]不能沿着i的同一个儿子走。特别地，如果i只有一个儿子，那么G[i]=0。答案为max(F[i]+G[i])。

最近公共祖先（LCA）

树链剖分

树状数组

lowbit

1
2
3
int lowbit(int x){
	return x&(-x);
}

单点修改，区间查询

1
2
3
4
5
6
7
8
9
ll n,sum[N];
void add(int p,int x){ //a[p]+=x,数组为[1,n]
    while(p<=n)sum[p]+=x,p+=p&-p;
}
ll query(int p){
    ll ans = 0;
    while(p)ans+=sum[p],p-=p&-p;
    return ans;
}

求逆序对

离散化，排序，逆序对数就是下标的逆序对数，逐一加入，加上已加入的大于当前值的数量。

区间极值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lowbit(int x){
	return x&(-x);
}
ll a[N],h[N],n;
void update(int p,int x){
  	a[p]=x;
    int lx;
    while(p<=n){
		h[p]=a[p];
        lx = lowbit(p);
		for (int i=1; i<lx; i<<=1)
			h[p] = max(h[p], h[p-i]);
		p += lowbit(p);
    }
}
int query(int l,int r){
    int ans = 0;
    while(l<=r){
      	ans = max(ans,a[r]);
      	r--;
		for(; l<=r-lowbit(r) ;r-=lowbit(r))ans = max(ans,h[r]);
    }
    return ans;
}

区间修改，单点查询

差分，设数组 $d[i]=a[i]-a[i-1],(a[0]=0)$，则 $a[i]=\sum\limits_{j=1}^id[j]$。

1
2
3
4
5
6
7
8
9
10
11
12
ll n,sum[N];
void add(int p, int x){ //这个函数用来在树状数组中直接修改
    while(p <= n) sum[p] += x, p += p & -p;
}
void range_add(int l, int r, int x){ //给区间[l, r]加上x
    add(l, x), add(r + 1, -x);
}
ll query(int p){ //单点查询
    ll res = 0;
    while(p) res += sum[p], p -= p & -p;
    return res;
}

区间修改，区间查询

$\sum\limits_{i=1}^pa[i]=\sum\limits_{i=1}^p\sum\limits_{j=1}^id[j]=(p+1)\times\sum\limits_{i=1}^pd[i]-\sum\limits_{i=1}^pd[i]\times i$，所以我们需要维护两个数状数组$d[i],d[i]*i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ll sum1[N],sum2[N],n;
void add(int p, ll x){
    while(p<=n)sum1[i] += x, sum2[i] += x * p ,p+=p&-p;
}
void range_add(int l, int r, ll x){
    add(l, x), add(r + 1, -x);
}
ll query(int p){
    ll res = 0;
    while(p)res += (p + 1) * sum1[i] - sum2[i],p-=p&-p;
    return res;
}
ll range_query(int l, int r){
    return query(r) - query(l - 1);
}

二维树状数组

单点修改+区间查询

定义$tree[x][y]$记录的是右下角为(x, y)，高为lowbit(x), 宽为 lowbit(y)的区间的区间和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void add(int x, int y, int z){ //将点(x, y)加上z
    int memo_y = y;
    while(x <= n){
        y = memo_y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void ask(int x, int y){//求左上角为(1,1)右下角为(x,y) 的矩阵和
    int res = 0, memo_y = y;
    while(x){
        y = memo_y;
        while(y)
            res += tree[x][y], y -= y & -y;
        x -= x & -x;
    }
}
区间修改 + 单点查询

差分 $d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void add(int x, int y, int z){ 
    int memo_y = y;
    while(x <= n){
        y = memo_y;
        while(y <= n)
            tree[x][y] += z, y += y & -y;
        x += x & -x;
    }
}
void range_add(int xa, int ya, int xb, int yb, int z){
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}
void ask(int x, int y){
    int res = 0, memo_y = y;
    while(x){
        y = memo_y;
        while(y)
            res += tree[x][y], y -= y & -y;
        x -= x & -x;
    }
}
区间修改 + 区间查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll read(){
    char c; bool op = 0;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') op = 1;
    ll res = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    return op ? -res : res;
}
const int N = 205;
ll n, m, Q;
ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];
void add(ll x, ll y, ll z){
    for(int X = x; X <= n; X += X & -X)
        for(int Y = y; Y <= m; Y += Y & -Y){
            t1[X][Y] += z;
            t2[X][Y] += z * x;
            t3[X][Y] += z * y;
            t4[X][Y] += z * x * y;
        }
}
void range_add(ll xa, ll ya, ll xb, ll yb, ll z){ //(xa, ya) 到 (xb, yb) 的矩形
    add(xa, ya, z);
    add(xa, yb + 1, -z);
    add(xb + 1, ya, -z);
    add(xb + 1, yb + 1, z);
}
ll ask(ll x, ll y){
    ll res = 0;
    for(int i = x; i; i -= i & -i)
        for(int j = y; j; j -= j & -j)
            res += (x + 1) * (y + 1) * t1[i][j]
                - (y + 1) * t2[i][j]
                - (x + 1) * t3[i][j]
                + t4[i][j];
    return res;
}
ll range_ask(ll xa, ll ya, ll xb, ll yb){
    return ask(xb, yb) - ask(xb, ya - 1) - ask(xa - 1, yb) + ask(xa - 1, ya - 1);
}
int main(){
    n = read(), m = read(), Q = read();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            ll z = read();
            range_add(i, j, i, j, z);
        }
    }
    while(Q--){
        ll ya = read(), xa = read(), yb = read(), xb = read(), z = read(), a = read();
        if(range_ask(xa, ya, xb, yb) < z * (xb - xa + 1) * (yb - ya + 1))
            range_add(xa, ya, xb, yb, a);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            printf("%lld ", range_ask(i, j, i, j));
        putchar('\n');
    }
    return 0;
}

线段树

  • 建树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    int A[N],Sum[N<<2],Lazy[N<<2];
    void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}//PushUp函数更新节点信息 ，这里是求和
    void Build(int l,int r,int rt){ //Build函数建树，l,r表示当前节点区间，rt表示当前节点编号
    	if(l==r) {//若到达叶节点
            scanf("%d",&Sum[rt]);
    		//Sum[rt]=A[l];//储存数组值
    		return;
    	}
    	int m=(l+r)>>1;
    	Build(l,m,rt<<1);
    	Build(m+1,r,rt<<1|1);
    	PushUp(rt);//更新信息
    }
    void PushDown(int rt,int ln,int rn){ //ln,rn为左子树，右子树的数字数量。
    	if(Lazy[rt]){
    		//下推标记 
    		Lazy[rt<<1]+=Lazy[rt];
    		Lazy[rt<<1|1]+=Lazy[rt]
    		//修改子节点的Sum使之与对应的Lazy相对应
    		Sum[rt<<1]+=Lazy[rt]*ln;
    		Sum[rt<<1|1]+=Lazy[rt]*rn;
    		Lazy[rt]=0;//清除本节点标记
    	}
    }
    //区间修改
    void Update(int L,int R,int C,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
    	if(L <= l && r <= R){//如果本区间完全在操作区间[L,R]以内
    		Sum[rt]+=C*(r-l+1);//更新数字和，向上保持正确
    		Lazy[rt]+=C;//增加Lazy标记，表示本区间的Sum正确，子区间的Sum仍需要根据Lazy的值来调整
    		return ; 
    	}
    	int m=(l+r)>>1;
    	PushDown(rt,m-l+1,r-m);//下推标记
    	//这里判断左右子树跟[L,R]有无交集，有交集才递归
    	if(L <= m) Update(L,R,C,l,m,rt<<1);
    	if(R >  m) Update(L,R,C,m+1,r,rt<<1|1);
    	PushUp(rt);//更新本节点信息
    }
    //区间查询
    int Query(int L,int R,int l,int r,int rt){//L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号
    	if(L <= l && r <= R){//在区间内，直接返回
    		return Sum[rt];
    	}
    	int m=(l+r)>>1;
    	PushDown(rt,m-l+1,r-m); //下推标记
    	if(R <= m) return Query(L,R,l,m,rt<<1);
    	if(L >  m) return Query(L,R,m+1,r,rt<<1|1);
    	return Query(L,R,l,m,rt<<1)+Query(L,R,m+1,r,rt<<1|1);
    }

平衡二叉树

heap

  • 建堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    int Heap[n],n;
    void node_swap(int x,int y){
        int temp=Heap[x];
        Heap[x]=Heap[y];
        Heap[y]=temp;
    }
    void siftdown(int i){ //i表示操作的结点编号（从1开始）
        while (2*i<=n) {
            int minn=Heap[2*i],temp=2*i;
            if (2*i+1<=n&&Heap[2*i]>Heap[2*i+1]) {
                minn=Heap[2*i+1];
                temp=2*i+1;
            }
            if (Heap[i]>minn) {
                node_swap(i,temp);
                i=temp;
            }else break;
        }
    }
    void siftup(int i){ //i表示操作的结点编号（从1开始）
        while (i!=1) {
            if (Heap[i]<Heap[i/2]) {
                node_swap(i,i/2);
                i/=2;
            }else break;
        }
    }
    void creat(){//建立堆
        for (int i=n/2; i>=1; i--) siftdown(i);
    }

  • 删除-输出最小元素

    1
    2
    3
    4
    5
    6
    7
    int delete_min(){
        int t=Heap[1];
        Heap[1]=Heap[n];
        n--;
        siftdown(1);
        return t;
    }

  • 堆排序(从大到小)

    1
    2
    3
    4
    5
    6
    7
    void heap_sort(){
        while (n>1) {
            node_swap(1, n);
            n--;
            siftdown(1);
        }
    }

top-k

n 个数中，找出最大（最小）的 m 个，建立一个小（大）顶堆维护当前最大（最小）的 m 个数再将剩余的推入。

RMQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ll dp[N][70]
void ST(int n) {
    for (int i = 1; i <= n; i++) dp[i][0] = A[i];
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}
ll RMQ(int l, int r) {
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1) k++;
    return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

主席树

可持久化权值线段树，因为其中的每一颗树都是一颗权值线段树。

dfs序

1
2
3
4
5
6
7
8
9
10
int L[N],R[N],dep[N],tot;
vii node[N];
void dfs(int rt,int fa,int d){
    L[rt]=++tot;
    dep[rt]=d;
    for(int v:node[rt]){
        if(v!=fa)dfs(v,rt,d+1);
    }
    R[rt]=tot;
}

  1. 对某个节点X权值加上一个数W, 查询某个子树X里所有点权的和.

  2. 对节点X到Y的最短路上所有点权都加一个数W, 查询某个点的权值.

    这个操作等价于

    a. 对X到根节点路径上所有点权加W

    b. 对Y到根节点路径上所有点权加W

    c. 对LCA(x, y)到根节点路径上所有点权值减W

    d. 对LCA(x,y)的父节点 fa(LCA(x, y))到根节点路径上所有权值减W

    于是要进行四次这样从一个点到根节点的区间修改.将问题进一步简化, 进行一个点X到根节点的区间修改, 查询其他一点Y时,只有X在Y的子树内, X对Y的值才有贡献且贡献值为W.当单点更新X时,X实现了对X到根的路径上所有点贡献了W.于是只需要更新四个点(单点更新) ,查询一个点的子树内所有点权的和(区间求和)即可.

  3. 对节点X到Y的最短路上所有点权都加一个数W, 查询某个点子树的权值之和.

    同问题2中的修改方法, 转化为修改某点到根节点的权值加/减W
    当修改某个节点A, 查询另一节点B时
    只有A在B的子树内, Y的值会增加
    W (dep[A] - dep[B] + 1) => W (dep [A] + 1) - W dep[B]
    那么我们处理两个数组就可以实现:
    处理出数组Sum1,每次更新W    (dep[A]+1),和数组Sum2,每次更新W.
    每次查询结果为Sum1(R[B]) – Sum1(L[B]-1) - (Sum2(R[B]) – Sum2(L[B]-1)) * dep [B].

  4. 对某个点X权值加上一个数W, 查询X到Y路径上所有点权之和.

    求X到Y路径上所有的点权之和, 和前面X到Y路径上所有点权加一个数相似
    这个问题转化为
    X到根节点的和 + Y到根节点的和 - LCA(x, y)到根节点的和 - fa(LCA(x,y)) 到根节点的和
    更新某个点x的权值时,只会对它的子树产生影响,对x的子树的每个点到根的距离都加了W.
    那么我们用”刷漆”(差分前缀和),更新一个子树的权值.给L[x]加上W,给R[x]+1减去W,那么sum(1~L[k])就是k到根的路径点权和.

  5. 对节点X的子树所有节点加上一个值W, 查询X到Y的路径上所有点的权值和

    同问题4把路径上求和转化为四个点到根节点的和
    X到根节点的和 + Y到根节点的和 - LCA(x, y)到根节点的和 - parent(LCA(x,y)) 到根节点的
    再用刷漆只更新子树.
    修改一点A, 查询某点B到根节点时, 只有B在A的子树内, A对B才有贡献.
    贡献为W (dep[B] - dep[A] + 1) => W (1 - dep[A]) + W dep[B]
    和第三题一样, 用两个sum1,sum2维护 W     (dep[A] + 1),和W.
    最后答案就是sum2*dep[B]-sum1.

  6. 对子树X里所有节点加上一个值W, 查询某个点的值.

    对DFS序来说, 子树内所有节点加W, 就是一段区间加W.
    所以这个问题就是 区间修改, 单点查询.树状数组+刷漆.

  7. 对子树X里所有节点加上一个值W, 查询某个子树的权值和.

    子树所有节点加W, 就是某段区间加W, 查询某个子树的权值和, 就是查询某段区间的和
    区间修改区间求和,用线段树可以很好解决.

欧拉序

从根结点出发，按dfs的顺序在绕回原点所经过所有点的顺序

Others

曼哈顿最小生成树

以每个点为原点，划分八个区域，将每个区域里距离 $S$ 最近的点连边，再跑最小生成树算法。

18161518-76bf4a5ccb434262849bdad165f88256

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
struct point{
    int x,y,id;
    oper(point){
        if(x==obj.x)return y<obj.y;
        else 
        return x<obj.x;
    }
}a[N];
int b[N];
int uni[N];
int find_root(int x){
    if (uni[x]==x) return x;
    else return uni[x]=find_root(uni[x]);
}
struct Edge{
    int u,v,w;
    oper(Edge){
        return w<obj.w;
    }
}edge[2*M];
int cnt;
void addedge(int u,int v,int w){
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt++].w=w;
}
int n;
pii h[N];
void add(int p,int loc,int x,int nn){
    while(p<=nn){
        if(h[p].fi>x)h[p]=pii(x,loc);
        p+=p&-p;
    }
}
pii query(int p){
    pii mi(inf,-1);
    while(p){
        if(h[p].fi<mi.fi)mi=h[p];
        p-=p&-p;
    }
    return mi;
}
bool cmp(int a,int b){
    return a>b;
}
void fun(){
    sort(a,a+n);
    for0(i,n)b[i]=a[i].y-a[i].x;
    sort(b,b+n,cmp);
    int m=unique(b,b+n)-b;//离散化 y-x
    for(int i=1;i<=m;i++)h[i]=pii(inf,-1);
    for(int i=n-1;i>=0;i--){
        int p=upper_bound(b,b+m,a[i].y-a[i].x,cmp)-b;
        pii mi=query(p);
        if(mi.se!=-1)addedge(a[i].id,mi.se,mi.fi-a[i].y-a[i].x);
        add(p,a[i].id,a[i].y+a[i].x,m);
    }
}
int main() {
    int k;
    in(n,k);
    for0(i,n){
        in(a[i].x,a[i].y);
        a[i].id=i;
    }
    fun();
    for0(i,n)swap(a[i].x,a[i].y);
    fun();
    for0(i,n)a[i].x*=-1;
    fun();
    for0(i,n)swap(a[i].x,a[i].y);
    fun();
    sort(edge,edge+cnt);
    for0(i,n)uni[i]=i;
    int ans=0,cc=0;
    for0(i,cnt){
        int u=edge[i].u,v=edge[i].v;
        if(find_root(u)!=find_root(v)){
            cc++;
            uni[find_root(u)]=find_root(v);
            if(cc==n-k){
                ans=edge[i].w;
                break;
            }
        }
    }
    out(ans,1);
    return 0;
}

莫队

对区间询问按左端点排序，将序列分成 $sqrt(n)$ 个长度为 $sqrt(n)$ 的块，若左端点在同一个块内，则按右端点排序。

优化
  • 块的大小为 $\huge\frac n {\sqrt{\frac 2 3 m}}$ 最优

  • 奇偶排序

    • 在块的序号为奇时，对 r 按从小到大排序，反之按从大到小排序

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      struct node {
          int l,r,id;
      }q[N];
      bool cmp(node a,node b){
          return a.l/block==b.l/block?a.l/block&1?a.r<b.r:a.r>b.r:a.l<b.l;
      }
      int main(){
          block=n/sqrt(Q*2/3);
          for(int i=0;i<m;i++){
              while(pl < q[i].l) del(a[pl++]);
              while(pl > q[i].l) add(a[--pl]);
              while(pr < q[i].r) add(a[++pr]);
              while(pr > q[i].r) del(a[pr--]);
              ans[q[i].id] = sum;
          }
      }
带修改

加上一个时间维，表示操作的时间。
即把询问 $[l,r]$ 变为 $[l,r,time]$
这一次我们排序的方式是以 $n^{\frac 2 3}$ 为一块，分成了 $n^{\frac 1 3}$ 块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。

Union Find

1
2
3
4
5
int uni[N];
int find_root(int x){
    if (uni[x]==x) return x;
    else return uni[x]=find_root(uni[x]);
}

主元素问题

找出数组中数量超过一半的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int findMainElement(const int* array, size_t size) {
    int candidate = array[0];
    int counter = 1;
    for (int i = 1; i < size; ++i) {
        if (candidate == array[i]) {
            ++counter;
        }
        else if (counter == 1) {
            candidate == array[i];
        }
        else {
            --counter;
        }
    }
    counter = 0;
    for (int i = 0; i < size; ++i) {
        if (candidate == array[i]) {
            ++counter;
        }
    }
    if (counter * 2 > size) {
        return candidate;
    }
    else {
        return -1;
    }
}

子段和

最大子段和

1
2
3
4
5
6
int b=0,sum=-100000000,l,r;
for(int i=0;i<n;i++){
  	if(b>0) b=b+a[i];
  	else b=a[i];
  	if(b>sum) sum=b;
}

最大环形子段和

思路一：

​ 把环形最大子段和可以看做两部分。第一部分——正常最大子段和，第二部分——跨越a[0] 和 a[n-1]的最大子段和。 第一部分可以用O(n) 求出，第二部分我们从a[0] 开始计算 0~n-2 的最大和，记录结束位置position1。 再从a[n-1] 开始计算 n-1~1的最大和，记录结束位置 position2。

position2 > position1 则第二部分最大和 a[0] + … a[position1] + a[position2] + …a[n-1]

position2 <= position1 则第二部分最大和 a[0] + ……. a[n-1]

思路二： 数组总和 - 最小子段和

最大M个子段和

设F(i, j) 为 在前i个元素中选j个子段的最大和，且包含元素a[j]. 那么对于a[j] , 1) a[j] 自己组成第 j 子段 ； 2) a[j] 包含于第 j 子段中；

长度不超过 m 的最大子段和

dp[i] = sum[i] - min(sum[j] | i- m <= j <= i)

利用单调队列优化.如果来了一个前缀，肯定下标是比在队列里的是靠后的，如果它的值还比队列里的小，那么队列里的元素就没有必要存在了，就把它们踢出去。

这样的话最小值就是队首的元素，当然在用队首元素的时候还要在看一下当前的队首元素还符不符合限制条件，如果不符合就弹出。

1
2
3
4
5
6
7
8
9
10
11
12
ll fun(ll m, ll a[], int len) {  // a的下标从1开始
    list<ll> li;
    li.push_back(0);
    ll ans = 0;
    for1(i, len) {
        while (!li.empty() && a[li.back()] > a[i]) li.pop_back();
        li.push_back(i);
        while (!li.empty() && i - li.front() > m) li.pop_front();
        ans = max(ans, a[i] - a[li.front()]);
    }
    return ans;
}

最大绝对值子段和

要么正的最大，要么负的最小。 所以问题解等于max{abs(最大子段和)， abs(最小子段和)}

最小绝对值字段和

  • 构造数组

  • 对b排序（保留index 信息）

  • 求排序后数组相邻位置差最小

固定长度的区间极值

1
2
3
4
5
6
7
int l=1,r=0,q[N];//q[i]表示从 i 开始长度为 len 的序列中的最小值的下标
for1(i,n){
    while(i-q[l]+1>a&&l<=r)l++;
    while(a[q[r]]>a[i]&&l<=r)r--;
    q[++r]=i;
    minn[i]=a[q[l]];//minn[i]表示以 i 结尾的长度为 len 的序列中的最小值
}