Caiwen的博客

势能线段树

2025-02-03 08:29:10

众所周知，线段树通过懒标记来做到优化时间复杂度。但使用懒标记必须满足，维护的值可以通过懒标记更新，以及懒标记之间可以快速合并。但有时候我们的区间操作不能简单地依赖懒标记，比如区间开根号，我们需要知道叶子节点的值才能得到开根号的结果，于是我们引入势能线段树这个概念：如果我们发现进行完一个操作之后，总会使能够接受的继续进行的操作次数越来越少，那么我们就可以先在线段树上暴力修改，然后维护是否还能继续操作，如果不能操作了，就直接返回，这样的话我们就达到了优化时间复杂度的效果。

参考[1][2]

简单的势能线段树

P4145 上帝造题的七分钟 2 / 花神游历各国

https://www.luogu.com.cn/problem/P4145

题目描述

第一行一个整数 nn，代表数列中数的个数。

第二行 nn 个正整数，表示初始状态下数列中的数。

第三行一个整数 mm，表示有 mm 次操作。

接下来 mm 行每行三个整数 k l r。

  • k=0k=0 表示给 [l,r][l,r] 中的每个数开平方（下取整）。

  • k=1k=1 表示询问 [l,r][l,r] 中各个数的和。

数据中有可能 l>rl>r，所以遇到这种情况请交换 ll 和 rr。

数据范围

对于 30%30\% 的数据，1≤n,m≤1031\le n,m\le 10^3，数列中的数不超过 3276732767。

对于 100%100\% 的数据，1≤n,m≤1051\le n,m\le 10^5，1≤l,r≤n1\le l,r\le n，数列中的数大于 00，且不超过 101210^{12}。

笔记

突破点：对一个数反复开根号，并不需要太多的次数，就可以使得这个数变成1，并且在这之后再开根号的话数字仍然不变。

于是我们先暴力遍历到叶子节点开根号，但同时维护某个节点所涵盖的区间是否都变成1，如果都变为1的话，就不需要再暴力遍历该区间开根号了。

D. The Child and Sequence

https://codeforces.com/problemset/problem/438/D

题目描述

给定 nn 个数，三种操作：

  1. 区间询问和
  2. 区间取模
  3. 单点修改

数据范围

1≤n,m≤1051\le n,m \le 10^5 。其他的数字最大不超过 10910^9。

笔记

突破点：让一个数不断对一些数取模，那么这个数应该是越来越小的，至少不会增大。同时如果这个数已经比模数还小了，就不需要再取模了，取模后的结果就是他本身。

于是我们维护区间的最大值，如果这个最大值比模数还小，那么整个的这个区间并不需要取模。反之，我们暴力取模。

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
#define _ 100005
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
int n,m,in[_];
struct Node{int sum,mx;} tree[_<<2];
inline void pushup(int k){
    nt.sum=lt.sum+rt.sum;
    nt.mx=max(lt.mx,rt.mx);
}
void build(int k,int l,int r){
    if(l==r) return nt.mx=in[l],nt.sum=in[l],void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.sum;
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(ls(k),l,mid,x,y);
    if(y>mid) res+=query(rs(k),mid+1,r,x,y);
    return res;
}
void modify(int k,int l,int r,int x,int y,int p){
    if(l==r) return nt.sum%=p,nt.mx%=p,void();
    if(nt.mx<p) return;
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls(k),l,mid,x,y,p);
    if(y>mid) modify(rs(k),mid+1,r,x,y,p);
    pushup(k);
}
void change(int k,int l,int r,int x,int v){
    if(l==r) return nt.sum=nt.mx=v,void();
    int mid=(l+r)>>1;
    if(x<=mid) change(ls(k),l,mid,x,v);
    else change(rs(k),mid+1,r,x,v);
    pushup(k);
}
inline void subtask(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    while(m--){
        int op,x,y,z;cin>>op>>x>>y;
        if(op==1) cout<<query(1,1,n,x,y)<<endl;
        else if(op==2) cin>>z,modify(1,1,n,x,y,z);
        else if(op==3) change(1,1,n,x,y);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

F. SUM and REPLACE

https://codeforces.com/contest/920/problem/F

题目描述

设 f(x)f(x) 为 xx 的因子个数。现在给定 nn 个数，有两种操作：

  1. 区间中所有的数字 xx 都变为 f(x)f(x)
  2. 询问区间和

数据范围

1≤n,m≤3×1051\le n,m \le 3\times 10^5，1≤ai≤1061\le a_i \le 10^6

笔记

突破点：和第一道题目一样的道理，修改操作会让数字不断的减小，直到数字变为 22 或 11，于是修改操作仍然可以暴力处理。

由于数字的值域只有 10610^6 ，可以先预处理一把。

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define _ 1000006
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
int prime[_],cnt,vis[_],f[_],m,n,in[_];
struct Node{int sum,ok;} tree[_<<2];
inline void init(){
    f[1]=1;
    for(int i=2;i<=1000000;i++){
        f[i]=1;
        if(!vis[i]) prime[++cnt]=i,vis[i]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=1000000;j++){
            vis[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        } 
    }
    for(int i=2;i<=1000000;i++){
        int x=i;
        while(x!=1){
            int c=0;
            int nxt=vis[x];
            while(x%nxt==0) x/=nxt,c++;
            f[i]*=(1+c);
        }   
    }
}
void pushup(int k){
    nt.sum=lt.sum+rt.sum;
    nt.ok=lt.ok&rt.ok;
}
void build(int k,int l,int r){
    if(l==r) return nt.sum=in[l],nt.ok=in[l]<=2?1:0,void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.sum;
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(ls(k),l,mid,x,y);
    if(y>mid) res+=query(rs(k),mid+1,r,x,y);
    return res;
}
void modify(int k,int l,int r,int x,int y){
    if(nt.ok) return;
    if(l==r) return nt.ok=f[nt.sum]<=2?1:0,nt.sum=f[nt.sum],void();
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls(k),l,mid,x,y);
    if(y>mid) modify(rs(k),mid+1,r,x,y);
    pushup(k);
}
inline void subtask(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1) modify(1,1,n,l,r);
        else if(op==2) cout<<query(1,1,n,l,r)<<endl;
    }
}
signed main(){
    init();
    // for(int i=1;i<=20;i++){
    //     cout<<i<<' '<<f[i]<<endl;
    // }
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

A. And RMQ

https://codeforces.com/gym/103107/problem/A

题目描述

给定 nn 个数，有三种操作：

  1. 区间按位与
  2. 单点修改
  3. 区间询问最大值

数据范围

1≤n,m≤4×1051\le n,m \le 4\times 10^5

笔记

突破点：按位与其实也是有“单调性”的。对于一个数字，对其不断进行按位与，实际上就是不断将其二进制为 11 的位上变为 00，11 的数量是单调不增的。如果将数字 nn 与某个数字 xx 按位与，xx 二进制为 00 的位置，nn 相同位置上都为 00，那么这个按位与实际上是没有效果的。

对于一个区间中的多个数也有上述的效果。我们令 e=al∣al+1∣...∣ar−1∣are=a_l|a_{l+1}|...|a_{r-1}|a_{r}，即把区间内所有数字都按位或起来。然后如果 e&x=ee\&x=e 那么我们就说这个区间的数字就都没必要再对 xx 按位与了。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define _ 400005
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
#define LOCAL
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

typedef pair<int,int> pii;
int n,m,in[_];
struct Node{int mx,e;} tree[_<<2];
void pushup(int k){
    nt.e=lt.e|rt.e;
    nt.mx=max(lt.mx,rt.mx);
}
void build(int k,int l,int r){
    if(l==r) return nt.e=nt.mx=in[l],void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
void modify(int k,int l,int r,int x,int y,int v){
    if((nt.e&v)==nt.e) return;
    if(l==r) return nt.mx&=v,nt.e&=v,void();
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls(k),l,mid,x,y,v);
    if(y>mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
void change(int k,int l,int r,int x,int v){
    if(l==r) return nt.mx=v,nt.e=v,void();
    int mid=(l+r)>>1;
    if(x<=mid) change(ls(k),l,mid,x,v);
    else change(rs(k),mid+1,r,x,v);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.mx;
    int mid=(l+r)>>1,res=-inf;
    if(x<=mid) res=max(res,query(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query(rs(k),mid+1,r,x,y));
    return res;
}
inline void subtask(){
    read(n,m);
    for(int i=1;i<=n;i++) read(in[i]);
    build(1,1,n);
    while(m--){
        char op[4];int x,y,z;
        read(op,x,y);
        if(op[0]=='A') read(z),modify(1,1,n,x,y,z);
        else if(op[0]=='U') change(1,1,n,x,y);
        else if(op[0]=='Q') put(query(1,1,n,x,y));
    }
}
signed main(){
    //ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}
踩坑

modify 函数那里要写成 if((nt.e&v)==nt.e) return; 而不是 if(nt.e&v==nt.e) return; ！

Counting Stars

https://vjudge.net/problem/HDU-7059

题目描述

给定 nn 个数，三种操作：

  1. 询问区间和
  2. 将区间内所有数的 lowbit 置为 0
  3. 将区间内所有数的 highbit 左移一位

数据范围

1≤∑n,∑q≤4×1051\le \sum n, \sum q \le 4\times 10^5，且 1≤ai≤1091\le a_i \le 10^9

笔记

对于操作 2 和 操作 3 都不会增加数字二进制 1 的个数，且操作 2 还会减少二进制 1 的个数，所以对于操作 2 我们可以考虑暴力。但注意，操作 3 也暴力的话时间复杂度就不对了，因为操作 3 并不会减少二进制 1 的个数。我们考虑能不能通过懒标记来优化。

我们把一个数的最高位和其他位分开，即 x=high+lowx=high+low，然后操作 3 就相当于把区间内所有的 highhigh 都乘 22，这就可以使用懒标记了

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> pii;
#define _ 100005
struct Node{int high,low,tag;} tree[_<<2];
int in[_],pw[_];
inline int lowbit(int x){return x&-x;}
inline void pushup(int k){nt.high=(lt.high+rt.high)%mod;nt.low=(lt.low+rt.low)%mod;}
inline void pushdown(int k){
    if(!nt.tag) return;
    lt.high=lt.high*pw[nt.tag]%mod;
    rt.high=rt.high*pw[nt.tag]%mod;
    lt.tag+=nt.tag;
    rt.tag+=nt.tag;
    nt.tag=0;
}
void build(int k,int l,int r){
    nt.tag=0;
    if(l==r){
        int now=0,x=in[l];
        while(x){
            if(x&1) nt.high=now;
            x>>=1;now++;
        }
        nt.high=pw[nt.high];nt.low=in[l]-nt.high;
        nt.tag=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return (nt.low+nt.high)%mod;
    int mid=(l+r)>>1,res=0;
    pushdown(k);
    if(x<=mid) res+=query(ls(k),l,mid,x,y),res%=mod;
    if(y>mid) res+=query(rs(k),mid+1,r,x,y),res%=mod;
    return res;
}
void modify_lowbit(int k,int l,int r,int x,int y){
    if(!nt.high&&!nt.low) return void();
    if(l==r){
        if(nt.low) nt.low-=lowbit(nt.low);
        else nt.high=0;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) modify_lowbit(ls(k),l,mid,x,y);
    if(y>mid) modify_lowbit(rs(k),mid+1,r,x,y);
    pushup(k);
}
void modify_highbit(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.high=nt.high*2%mod,nt.tag++,void();
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) modify_highbit(ls(k),l,mid,x,y);
    if(y>mid) modify_highbit(rs(k),mid+1,r,x,y);
    pushup(k);
}
inline void subtask(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    int m;cin>>m;
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1) cout<<query(1,1,n,l,r)<<endl;
        if(op==2) modify_lowbit(1,1,n,l,r);
        if(op==3) modify_highbit(1,1,n,l,r);
    }
}
signed main(){
    pw[0]=1;
    for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*2%mod;
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--) subtask();
    return 0;
}
踩坑

一开始 build 函数那里忘记把 tag 清空了，wa了好几次

Lowbit

https://vjudge.net/problem/HDU-7116

题目描述

给定 nn 个数，两种操作：

  1. 区间内每个数都加上自身的 lowbit
  2. 询问区间和

数据范围

1≤n,m≤1051\le n,m \le 10^5

笔记

我们发现，一个数 xx 加上 lowbit(x)lowbit(x) ，那么这个数的二进制 1 数量要么减少要么不变。如果 xx 的二进制 1 数量为 1 了，那么 x+lowbit(x)x+lowbit(x) 就相当于对 xx 乘二了。

那么就有了做法，区间内所有的数的二进制 1 数量都为 1 了，那么就相当于区间乘 2 ，使用懒标记。反之，暴力修改

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> pii;
#define _ 100005
struct Node{int sum,ok,tag;} tree[_<<2];
int in[_],pw[_];
inline int lowbit(int x){return x&-x;}
inline int popcnt(int x,int res=0){for(;x;x>>=1) if(x&1) res++;return res;}
inline void pushup(int k){nt.sum=(lt.sum+rt.sum)%mod;nt.ok=lt.ok&rt.ok;}
inline void pushdown(int k){
    if(!nt.tag) return;
    lt.sum=lt.sum*pw[nt.tag]%mod;
    rt.sum=rt.sum*pw[nt.tag]%mod;
    lt.tag+=nt.tag;
    rt.tag+=nt.tag;
    nt.tag=0;
}
void build(int k,int l,int r){
    nt.tag=0;
    if(l==r) return nt.sum=in[l],nt.ok=popcnt(in[l])==1?1:0,void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.sum;
    pushdown(k);
    int mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(ls(k),l,mid,x,y),res%=mod;
    if(y>mid) res+=query(rs(k),mid+1,r,x,y),res%=mod;
    return res;
}
void modify(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y&&nt.ok) return nt.sum=nt.sum*2%mod,nt.tag++,void();
    if(l==r) return nt.sum+=lowbit(nt.sum),nt.ok=popcnt(nt.sum)==1?1:0,void();
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls(k),l,mid,x,y);
    if(y>mid) modify(rs(k),mid+1,r,x,y);
    pushup(k);
}
inline void subtask(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    int m;cin>>m;
    while(m--){
        int op,l,r;cin>>op>>l>>r;
        if(op==1) modify(1,1,n,l,r);
        if(op==2) cout<<query(1,1,n,l,r)<<endl;
    }
}
signed main(){
    pw[0]=1;
    for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*2%mod;
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--) subtask();
    return 0;
}

吉司机线段树

我们把一类需要划分数域来解决的区间最值、区间历史最值问题，用到的势能线段树称为吉司机线段树

区间最值操作

以一道题举例

Gorgeous Sequence

https://vjudge.net/problem/HDU-5306

题目描述

给出一个长度为 n(n≤106)n(n\le 10^6) 的序列 AA 和 m(m≤106)m(m\le 10^6) 次操作，每次操作为以下三种类型之一：

  1. 区间对数字 kk 取 min
  2. 求区间最大值
  3. 求区间和

笔记

如果没有区间求和的话就很好做了。有区间求和的话我们就不能使用传统的懒标记的方法来做了。

这种题一般是这样考虑的：

维护区间最大值 mxmx 和次大值 sese，以及最大值个数 cntcnt，区间和 sumsum，然后进行区间对 kk 取 minmin 的时候，有如下的情况：

  • k≥mxk\ge mx，此时该操作不会对当前节点产生影响
  • se<k<mxse < k < mx ，此时区间上的最大值都会被修改为 kk，我们借助 cntcnt 和 mxmx 快速更新 sumsum
  • k≤sek\le se 时，我们无法快速更新区间信息，选择直接暴力递归左右子树

时间复杂度是正确的，我们这么考虑，当我们递归左右子树的时候，说明该区间内不同的数字个数一定会减少，而线段树每层节点表示的区间内的不同数字个数一共是 O(n)O(n) 的，一共有 log⁡n\log n 层，因此递归的总时间复杂度是 O(nlog⁡n)O(n\log n)。再加上每次操作的复杂度，总时间复杂度为 O((n+m)log⁡n)O((n+m)\log n)

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 1000006
#define LOCAL
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

struct Node{int sum,mx,se,tag,cnt;} tree[_<<2];
int in[_];
inline void pushup(int k){
    nt.sum=lt.sum+rt.sum;
    nt.mx=max(lt.mx,rt.mx);
    if(lt.mx==rt.mx) nt.se=max(lt.se,rt.se),nt.cnt=lt.cnt+rt.cnt;
    else nt.se=max(min(lt.mx,rt.mx),max(lt.se,rt.se)),nt.cnt=lt.mx>rt.mx?lt.cnt:rt.cnt;
}
inline void update(int k,int x){if(x<nt.mx) nt.sum-=(nt.mx-x)*nt.cnt,nt.mx=nt.tag=x;}
inline void pushdown(int k){if(nt.tag!=-1) update(ls(k),nt.tag),update(rs(k),nt.tag),nt.tag=-1;}
void build(int k,int l,int r){
    nt.tag=-1;
    if(l==r) return nt.sum=nt.mx=in[l],nt.se=-1,nt.cnt=1,void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
void modify(int k,int l,int r,int x,int y,int v){
    if(v>=nt.mx) return;
    if(l>=x&&r<=y&&v>nt.se) return update(k,v),void();
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) modify(ls(k),l,mid,x,y,v);
    if(y>mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query_max(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.mx;
    int mid=(l+r)>>1,res=-inf;
    pushdown(k);
    if(x<=mid) res=max(res,query_max(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query_max(rs(k),mid+1,r,x,y));
    return res;
}
int query_sum(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.sum;
    int mid=(l+r)>>1,res=0;
    pushdown(k);
    if(x<=mid) res+=query_sum(ls(k),l,mid,x,y);
    if(y>mid) res+=query_sum(rs(k),mid+1,r,x,y);
    return res;
}
inline void subtask(){
    int n,m;read(n);read(m);
    for(int i=1;i<=n;i++) read(in[i]);
    build(1,1,n);
    while(m--){
        int op,l,r,x;read(op),read(l),read(r);
        if(op==0) read(x),modify(1,1,n,l,r,x);
        if(op==1) put(query_max(1,1,n,l,r));
        if(op==2) put(query_sum(1,1,n,l,r));
    }
}
signed main(){
    //ios::sync_with_stdio(false);
    int t;read(t);
    while(t--) subtask();
    return 0;
}

支持区间加减

现在既有加减的懒标记，又有取 min 的懒标记，难点在于如何 pushdown 这两个标记

由于取 min 需要依赖原有的值，所以加减的懒标记应该先于 min 懒标记下放

对于加减 xx，下放的时候直接让子节点的加减懒标记和取 min 懒标记也加减 xx 就可以了

对于对 xx 取 min，下放的时候直接将子节点的取 min 懒标记置为 xx。注意这么做的前提是，区间内所有数的最大值是大于 xx 的，这样的话可以保证如果多次下放取 min 懒标记，懒标记的值是单调的，直接置为 xx 是没问题的

但是有了这个操作之后，上述的时间复杂度分析的方法不适用了。论文[3]中给出了另一种分析思路，分析出来的时间复杂度为 O(mlog⁡2n)O(m\log^2n)

取 min 和取 max 同时存在

P10639 BZOJ4695 最佳女选手

https://www.luogu.com.cn/problem/P10639

题目描述

给定一个长度为 nn 的序列，要求支持以下 66 种操作：

  • 给一个区间 [l,r][l,r] 加上一个整数 xx；
  • 把一个区间 [l,r][l,r] 内小于 xx 的数都变成 xx；
  • 把一个区间 [l,r][l,r] 内大于 xx 的数都变成 xx；
  • 求区间 [l,r][l,r] 的和；
  • 求区间 [l,r][l,r] 的最大值；
  • 求区间 [l,r][l,r] 的最小值；

数据范围

数据保证，1≤n,m≤5×1051\leq n,m\leq 5\times 10^5，∣ai∣≤108|a_i|\leq 10^8。

当进行 11 操作时，∣x∣≤1000|x| \leq 1000；

当进行 22 操作时，∣x∣≤108|x| \leq 10^8。

笔记

现在在支持区间加减的基础上，既支持取 min 又支持取 max。我们可以维护区间最大值，区间次大值，区间最大值个数，区间最小值，区间次小值，区间最小值个数，区间和，以及取 min 懒标记，取 max 懒标记，加减懒标记

有三个懒标记，如何下放就成了问题，显然我们还是先下放加减懒标记

  • 对于加减 xx，下放时子节点的加减懒标记，取 min 懒标记，取 max 懒标记都加减 xx

后面先下放取 min 懒标记还是先下放取 max 懒标记就无所谓了，我们先下放取 min 懒标记

  • 对于对 xx 取 min，子节点的取 min 懒标记置为 xx，然后子节点的取 max 懒标记对 xx 取 min，防止先前的取 max 操作影响到本次的取 min 操作
  • 对于对 xx 取 max，同理

同时，当一个区间内数字较少的时候，可能会出现最大值、最小值、次小值、次大值中间有几个是相同的

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 500005
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define LOCAL
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;
int in[_];
struct Node{int max1,max2,min1,min2,cmin,cmax,sum,tmin,tmax,tsum;} tree[_<<2];
inline void pushup(int k){
    nt.sum=lt.sum+rt.sum;
    nt.max1=max(lt.max1,rt.max1);
    if(lt.max1==rt.max1) nt.max2=max(lt.max2,rt.max2),nt.cmax=lt.cmax+rt.cmax;
    else nt.max2=max(min(lt.max1,rt.max1),max(lt.max2,rt.max2)),nt.cmax=lt.max1>rt.max1?lt.cmax:rt.cmax;
    nt.min1=min(lt.min1,rt.min1);
    if(lt.min1==rt.min1) nt.min2=min(lt.min2,rt.min2),nt.cmin=lt.cmin+rt.cmin;
    else nt.min2=min(max(lt.min1,rt.min1),min(lt.min2,rt.min2)),nt.cmin=lt.min1<rt.min1?lt.cmin:rt.cmin;
}
void build(int k,int l,int r){
    nt.tmin=inf,nt.tmax=-inf,nt.tsum=0;
    if(l==r) return nt.max1=nt.min1=nt.sum=in[l],nt.max2=-inf,nt.min2=inf,nt.cmax=nt.cmin=1,void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
inline void pushsum(int k,int l,int r,int v){
    nt.sum+=(r-l+1ll)*v;
    nt.max1+=v,nt.min1+=v;
    if(nt.max2!=-inf) nt.max2+=v;
    if(nt.min2!=inf) nt.min2+=v;
    if(nt.tmin!=inf) nt.tmin+=v;
    if(nt.tmax!=-inf) nt.tmax+=v;
    nt.tsum+=v;
}
inline void pushmin(int k,int v){
    if(nt.max1<=v) return;
    nt.sum-=(nt.max1-v)*nt.cmax;
    if(nt.max1==nt.min2) nt.min2=v;
    if(nt.max1==nt.min1) nt.min1=v;
    nt.tmax=min(nt.tmax,v),nt.max1=v,nt.tmin=v;
}
inline void pushmax(int k,int v){
    if(nt.min1>=v) return;
    nt.sum+=(v-nt.min1)*nt.cmin;
    if(nt.min1==nt.max2) nt.max2=v;
    if(nt.min1==nt.max1) nt.max1=v;
    nt.tmin=max(nt.tmin,v),nt.min1=v,nt.tmax=v;
}
inline void pushdown(int k,int l,int r,int mid){
    if(nt.tsum) pushsum(ls(k),l,mid,nt.tsum),pushsum(rs(k),mid+1,r,nt.tsum);
    if(nt.tmin!=inf) pushmin(ls(k),nt.tmin),pushmin(rs(k),nt.tmin);
    if(nt.tmax!=-inf) pushmax(ls(k),nt.tmax),pushmax(rs(k),nt.tmax);
    nt.tsum=0,nt.tmax=-inf,nt.tmin=inf;
}
void modify_sum(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y) return pushsum(k,l,r,v),void();
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    if(x<=mid) modify_sum(ls(k),l,mid,x,y,v);
    if(y>mid) modify_sum(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
void modify_min(int k,int l,int r,int x,int y,int v){
    if(nt.max1<=v) return;
    if(l>=x&&r<=y&&v>nt.max2) return pushmin(k,v),void();
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    if(x<=mid) modify_min(ls(k),l,mid,x,y,v);
    if(y>mid) modify_min(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
void modify_max(int k,int l,int r,int x,int y,int v){
    if(nt.min1>=v) return;
    if(l>=x&&r<=y&&v<nt.min2) return pushmax(k,v),void();
    int mid=(l+r)>>1;
    pushdown(k,l,r,mid);
    if(x<=mid) modify_max(ls(k),l,mid,x,y,v);
    if(y>mid) modify_max(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query_sum(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.sum;
    int mid=(l+r)>>1,res=0;
    pushdown(k,l,r,mid);
    if(x<=mid) res+=query_sum(ls(k),l,mid,x,y);
    if(y>mid) res+=query_sum(rs(k),mid+1,r,x,y);
    return res;
}
int query_min(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.min1;
    int mid=(l+r)>>1,res=inf;
    pushdown(k,l,r,mid);
    if(x<=mid) res=min(res,query_min(ls(k),l,mid,x,y));
    if(y>mid) res=min(res,query_min(rs(k),mid+1,r,x,y));
    return res;
}
int query_max(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.max1;
    int mid=(l+r)>>1,res=-inf;
    pushdown(k,l,r,mid);
    if(x<=mid) res=max(res,query_max(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query_max(rs(k),mid+1,r,x,y));
    return res;
}
inline void subtask(){
    int n,m;read(n);
    for(int i=1;i<=n;i++) read(in[i]);
    build(1,1,n);read(m);
    while(m--){
        int op,l,r,x;read(op),read(l),read(r);
        if(op<=3) read(x);
        if(op==1) modify_sum(1,1,n,l,r,x);
        if(op==2) modify_max(1,1,n,l,r,x);
        if(op==3) modify_min(1,1,n,l,r,x);
        if(op==4) put(query_sum(1,1,n,l,r));
        if(op==5) put(query_max(1,1,n,l,r));
        if(op==6) put(query_min(1,1,n,l,r));
    }
}
signed main(){
    //ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

区间历史最值

传统懒标记

对于一些不太复杂的问题，我们可以沿用传统懒标记的做法

P4314 CPU 监控

https://www.luogu.com.cn/problem/P4314

题目描述

nn 个数，mm 个操作：

  1. 询问区间最大值
  2. 询问历史区间历史最大值
  3. 区间加
  4. 区间推平

数据范围

1≤n,m≤1051\le n,m\le 10^5 ，数字值域为 int 取值范围

笔记

本题和势能线段树没有什么关系，只是考虑以下如何用传统的懒标记解决区间历史最值问题

第一个难点是，既有区间加和区间推平，懒标记怎么下放。我们不难发现，作用完区间推平之后，后面无论是区间加还是区间推平，都可以归为区间推平（毕竟推平后所有数就都相等了）。所以我们可以考虑先下放区间加标记，再下放区间推平标记。下放区间加标记时，判断是否已经有了区间推平标记，如果有，就直接加到区间推平标记上，如果没有，就加到区间加标记上。下放区间推平标记就正常下放即可

第二个难点是如何处理区间历史最值，首先一个朴素的想法就是多维护一个区间历史最大值 hmaxhmax 即可，但这样就会出现问题：比如父节点一开始都为 11，然后对 33 推平，然后对 22 推平，然后后面操作访问到子节点时，子节点只会接收到对 22 推平的懒标记，之前对 33 推平的懒标记就被忽略了，但是子节点的历史最值是 33

因此我们还需要记录推平标记的历史最值，加减标记的历史最值

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
#define _ 100005
typedef pair<int,int> pii;
struct Node{int mx,hmx,cov,hcov,iscov,add,hadd;} tree[_<<2];
int in[_];
inline void pushup(int k){nt.mx=max(lt.mx,rt.mx),nt.hmx=max(lt.hmx,rt.hmx);}
void build(int k,int l,int r){
    nt.iscov=false,nt.add=0;
    if(l==r) return nt.mx=nt.hmx=in[l],void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);build(rs(k),mid+1,r);
    pushup(k);
}
void pushcov(int k,int v,int hv){
    if(nt.iscov) nt.hcov=max(nt.hcov,hv);
    else nt.iscov=true,nt.hcov=hv;
    nt.hmx=max(nt.hmx,hv);
    nt.cov=nt.mx=v;
    nt.add=0;
}
void pushsum(int k,int v,int hv){
    if(nt.iscov) pushcov(k,nt.cov+v,nt.cov+hv);
    else{
        nt.hadd=max(nt.hadd,nt.add+hv);
        nt.hmx=max(nt.hmx,nt.mx+hv);
        nt.add+=v,nt.mx+=v;
    }
}
void pushdown(int k){
    pushsum(ls(k),nt.add,nt.hadd);
    pushsum(rs(k),nt.add,nt.hadd);//nt.add可能为0，但是仍下放，因为nt.hadd会有贡献
    nt.add=nt.hadd=0;
    if(nt.iscov){
        pushcov(ls(k),nt.cov,nt.hcov);
        pushcov(rs(k),nt.cov,nt.hcov);
        nt.iscov=false;
    }
}
void modify_sum(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y) return pushsum(k,v,v),void();
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) modify_sum(ls(k),l,mid,x,y,v);
    if(y>mid) modify_sum(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
void modify_cover(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y) return pushcov(k,v,v),void();
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) modify_cover(ls(k),l,mid,x,y,v);
    if(y>mid) modify_cover(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query_max(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.mx;
    pushdown(k);
    int mid=(l+r)>>1,res=-inf;
    if(x<=mid) res=max(res,query_max(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query_max(rs(k),mid+1,r,x,y));
    return res;
}
int query_hmax(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.hmx;
    pushdown(k);
    int mid=(l+r)>>1,res=-inf;
    if(x<=mid) res=max(res,query_hmax(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query_hmax(rs(k),mid+1,r,x,y));
    return res;
}
inline void subtask(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    int m;cin>>m;
    while(m--){
        char op;int l,r,x;cin>>op>>l>>r;
        if(op=='Q') cout<<query_max(1,1,n,l,r)<<endl;
        if(op=='A') cout<<query_hmax(1,1,n,l,r)<<endl;
        if(op=='P') cin>>x,modify_sum(1,1,n,l,r,x);
        if(op=='C') cin>>x,modify_cover(1,1,n,l,r,x);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

最值操作和维护的最值同向

同向指的是，比如，我维护区间最小值，操作也是区间取 min，这种情况下可以继续沿用上述传统的懒标记方法

#164. 【清华集训2015】V

https://vjudge.net/problem/UniversalOJ-164

题目描述

给出一个长度为 n(n≤5×105)n(n\le 5\times 10^5) 的序列，m(m≤5×105)m(m\le 5\times 10^5) 次操作：

  1. 区间加（非负数）
  2. 区间减 kk （非负数）后再对 00 取 max
  3. 区间推平（非负数）
  4. 单点询问
  5. 单点询问历史最大值

数字值域最大为 10910^9

笔记

为了简单起见，我们把区间推平操作给转化为先减去正无穷，然后对 xx 取 max。不然再搞一个区间推平的懒标记就有点复杂了

于是本题和上题的区别就是多了个区间取 max，我们多维护两个懒标记：取 max 懒标记，历史最大取 max 懒标记

取 max 标记和加减标记下放时如何处理在前文已经说了

值得注意的是本题涉及到减去正无穷，所以有两个注意点：首先这个无穷值不能太小，不然我加了一堆 10910^9，然后再减去无穷值之后得到的结果还是正数；这个无穷值不能太大，不然我减两次无穷就炸了，代码中的解决方案是判断当前值是否小于了 -inf，小于的话就不再继续减了

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=5e14;
const int mod=0;
typedef pair<int,int> pii;
#define _ 500005
int in[_],n,m;
struct Node{int mx,hmx,add,hadd,tmx,htmx;} tree[_<<2];
inline void pushup(int k){nt.mx=max(lt.mx,rt.mx),nt.hmx=max(lt.hmx,rt.hmx);}
void build(int k,int l,int r){
    nt.tmx=nt.htmx=-inf;
    if(l==r) return nt.mx=nt.hmx=in[l],void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);build(rs(k),mid+1,r);
    pushup(k);
}
inline void pushadd(int k,int v,int hv){
    nt.hadd=max(nt.hadd,nt.add+hv);
    nt.hmx=max(nt.hmx,nt.mx+hv);
    if(nt.tmx!=-inf) nt.htmx=max(nt.htmx,nt.tmx+hv),nt.tmx+=nt.tmx<-inf?0:v;
    nt.add+=nt.add<-inf?0:v,nt.mx+=nt.mx<-inf?0:v;
}
inline void pushmax(int k,int v,int hv){
    nt.htmx=max(nt.htmx,hv);
    nt.hmx=max(nt.hmx,max(nt.mx,hv));
    nt.tmx=max(nt.tmx,v),nt.mx=max(nt.mx,v);
}
inline void pushdown(int k){
    pushadd(ls(k),nt.add,nt.hadd);
    pushadd(rs(k),nt.add,nt.hadd);
    nt.add=nt.hadd=0;
    if(nt.tmx!=-inf){
        pushmax(ls(k),nt.tmx,nt.htmx);
        pushmax(rs(k),nt.tmx,nt.htmx);
        nt.tmx=nt.htmx=-inf;
    }
}
void modify_add(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y) return pushadd(k,v,v),void();
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) modify_add(ls(k),l,mid,x,y,v);
    if(y>mid) modify_add(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
void modify_max(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y) return pushmax(k,v,v),void();
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) modify_max(ls(k),l,mid,x,y,v);
    if(y>mid) modify_max(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query_p(int k,int l,int r,int x){
    if(l==r) return nt.mx;
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) return query_p(ls(k),l,mid,x);
    else return query_p(rs(k),mid+1,r,x);
}
int query_h(int k,int l,int r,int x){
    if(l==r) return nt.hmx;
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) return query_h(ls(k),l,mid,x);
    else return query_h(rs(k),mid+1,r,x);
}
inline void subtask(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    while(m--){
        int op,l,r,x;cin>>op>>l;
        if(op==1) cin>>r>>x,modify_add(1,1,n,l,r,x);
        if(op==2) cin>>r>>x,modify_add(1,1,n,l,r,-x),modify_max(1,1,n,l,r,0);
        if(op==3) cin>>r>>x,modify_add(1,1,n,l,r,-inf),modify_max(1,1,n,l,r,x);
        if(op==4) cout<<query_p(1,1,n,l)<<endl;
        if(op==5) cout<<query_h(1,1,n,l)<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

最值操作和维护的最值反向

比如，我维护区间最小值，但操作是区间取 max，这时候就需要使用势能线段树了

P6242 【模板】线段树 3（区间最值操作、区间历史最值）

https://www.luogu.com.cn/problem/P6242

题目描述

给出一个长度为 nn 的数列 AA，同时定义一个辅助数组 BB，BB 开始与 AA 完全相同。接下来进行了 mm 次操作，操作有五种类型，按以下格式给出：

  • 1 l r k：对于所有的 i∈[l,r]i\in[l,r]，将 AiA_i 加上 kk（kk 可以为负数）。
  • 2 l r v：对于所有的 i∈[l,r]i\in[l,r]，将 AiA_i 变成 min⁡(Ai,v)\min(A_i,v)。
  • 3 l r：求 ∑i=lrAi\sum_{i=l}^{r}A_i。
  • 4 l r：对于所有的 i∈[l,r]i\in[l,r]，求 AiA_i 的最大值。
  • 5 l r：对于所有的 i∈[l,r]i\in[l,r]，求 BiB_i 的最大值。

在每一次操作后，我们都进行一次更新，让 Bi←max⁡(Bi,Ai)B_i\gets\max(B_i,A_i)。

数据范围

对于全部测试数据，保证 1≤n,m≤5×1051\leq n,m\leq 5\times 10^5，−5×108≤Ai≤5×108-5\times10^8\leq A_i\leq 5\times10^8，op∈[1,5]op\in[1,5]，1≤l≤r≤n1 \leq l\leq r \leq n，−2000≤k≤2000-2000\leq k\leq 2000，−5×108≤v≤5×108-5\times10^8\leq v\leq 5\times10^8。

笔记

如果本题没有区间历史最值的话，做法在之前已经说过了。我们回顾一下之前的做法，之前的做法中维护区间次值，实际上是把维护的数分为了两个部分：最值和非最值。如果操作仅对最值产生影响，那么可以快速处理。如果操作影响到了非最值，那么就暴力处理，同时这个划分方法确保了暴力处理是可以让势能下降的，从而确保了时间复杂度。

并且我们还会发现，划分数域后，所有的操作都可以视为对最值进行直接的修改，即使在某个节点上是对非最值修改，那么递归下去，也是对某个子节点的最值进行修改。这样一来，我们可以把所有的取最值操作转化为对最值的加减操作。比如当前最大值为 xx，我想对 k(k<x)k(k<x) 取 min，那么我们可以直接让最大值减去 x−kx-k ，在下传标记的时候，我们判断一下左右子节点的最大值是否是父节点的最大值，是的话就把这个仅对最大值操作的标记传过去。这个转化可以让我们抛弃掉不太好处理的区间最值标记，转向更加处理的加减标记

现在这道题，如果我们仍然沿用传统的懒标记方法就不太好处理了。但这种反向的特性，给了我们划分数域处理的机会。我们把区间内的数字划分为最大值和非最大值两部分，每部分维护加减懒标记和历史最大加减懒标记。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 500005
struct Tag{int add1,hadd1,add2,hadd2;};//1结尾为作用于最大，2结尾为作用于次大
struct Node{int mx,hmx,se,sum,cnt1;Tag tag;} tree[_<<2];
int in[_],n,m;
inline void pushup(int k){
    nt.sum=lt.sum+rt.sum;
    nt.mx=max(lt.mx,rt.mx);
    nt.hmx=max(lt.hmx,rt.hmx);
    if(lt.mx==rt.mx) nt.cnt1=lt.cnt1+rt.cnt1,nt.se=max(lt.se,rt.se);
    else nt.se=max(min(lt.mx,rt.mx),max(lt.se,rt.se)),nt.cnt1=lt.mx>rt.mx?lt.cnt1:rt.cnt1;
} 
void build(int k,int l,int r){
    if(l==r) return nt.mx=nt.hmx=nt.sum=in[l],nt.cnt1=1,nt.se=-inf,void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);build(rs(k),mid+1,r);
    pushup(k);
}
inline void update(int k,int l,int r,Tag tag){
    nt.sum+=tag.add1*nt.cnt1+tag.add2*(r-l+1-nt.cnt1);
    nt.tag.hadd1=max(nt.tag.hadd1,nt.tag.add1+tag.hadd1);
    nt.tag.hadd2=max(nt.tag.hadd2,nt.tag.add2+tag.hadd2);
    nt.tag.add1+=tag.add1;
    nt.tag.add2+=tag.add2;
    nt.hmx=max(nt.hmx,nt.mx+tag.hadd1);
    nt.mx+=tag.add1;
    if(nt.se!=-inf) nt.se+=tag.add2;
}
inline void pushdown(int k,int l,int r){
    int mx=max(lt.mx,rt.mx),mid=(l+r)>>1;
    Tag tag1=nt.tag,tag2=nt.tag;
    tag2.add1=nt.tag.add2,tag2.hadd1=nt.tag.hadd2;//构造区间内没有父节点最大值时，需要作用的标记。此时子节点的最大值相当于父节点的非最大值
    if(mx==lt.mx) update(ls(k),l,mid,tag1);
    else update(ls(k),l,mid,tag2);
    if(mx==rt.mx) update(rs(k),mid+1,r,tag1);
    else update(rs(k),mid+1,r,tag2);
    nt.tag.add1=nt.tag.add2=nt.tag.hadd1=nt.tag.hadd2=0; 
}
void modify_add(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){
        Tag tag;tag.add2=tag.hadd2=tag.add1=tag.hadd1=v;//无论是最大值还是非最大值，都需要+v
        update(k,l,r,tag);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r);
    if(x<=mid) modify_add(ls(k),l,mid,x,y,v);
    if(y>mid) modify_add(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
void modify_min(int k,int l,int r,int x,int y,int v){
    if(v>=nt.mx) return;
    if(l>=x&&r<=y&&v>nt.se){
        Tag tag;tag.add1=tag.hadd1=v-nt.mx,tag.add2=tag.hadd2=0;//仅最大值作用
        update(k,l,r,tag);
        return;
    }
    int mid=(l+r)>>1;
    pushdown(k,l,r);
    if(x<=mid) modify_min(ls(k),l,mid,x,y,v);
    if(y>mid) modify_min(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query_sum(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.sum;
    int mid=(l+r)>>1,res=0;
    pushdown(k,l,r);
    if(x<=mid) res+=query_sum(ls(k),l,mid,x,y);
    if(y>mid) res+=query_sum(rs(k),mid+1,r,x,y);
    return res;
}
int query_max(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.mx;
    int mid=(l+r)>>1,res=-inf;
    pushdown(k,l,r);
    if(x<=mid) res=max(res,query_max(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query_max(rs(k),mid+1,r,x,y));
    return res;
}
int query_hmax(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.hmx;
    int mid=(l+r)>>1,res=-inf;
    pushdown(k,l,r);
    if(x<=mid) res=max(res,query_hmax(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query_hmax(rs(k),mid+1,r,x,y));
    return res;
}
inline void subtask(){
    cin>>n>>m;for(int i=1;i<=n;i++) cin>>in[i];
    build(1,1,n);
    while(m--){
        int op,l,r,x;cin>>op>>l>>r;
        if(op==1) cin>>x,modify_add(1,1,n,l,r,x);
        if(op==2) cin>>x,modify_min(1,1,n,l,r,x);
        if(op==3) cout<<query_sum(1,1,n,l,r)<<endl;
        if(op==4) cout<<query_max(1,1,n,l,r)<<endl;
        if(op==5) cout<<query_hmax(1,1,n,l,r)<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

区间历史最值求和

题目描述

给出一个长度为 n(n≤105)n(n\le 10^5) 的序列，m(m≤105)m(m\le 10^5) 次操作：

  1. 区间加
  2. 询问给定区间的区间历史最大值之和

笔记

我们要维护的序列为 AiA_i，历史最大值为序列 BiB_i

然后我们令 Ci=Ai−BiC_i=A_i-B_i，容易发现 Ci≤0C_i\le 0 恒成立

当我们对 AiA_i 加 xx 的时候，CiC_i 也加了 xx。此时，如果 CiC_i 仍小于等于 00，说明 Ai+xA_i+x 并没有更新掉历史最大值。 如果 CiC_i 大于 0 了，说明 Ai+xA_i+x 比历史最大值还大，BiB_i 更新为 Ai+xA_i+x，于是 CiC_i 又变为了 0

于是我们可以再维护 CiC_i，实现 区间加、区间取 minmin、询问区间和 即可

询问区间历史最大值之和时，∑Bi=∑Ai−∑Ci\sum B_i=\sum A_i-\sum C_i

题目

【UR #19】前进四

题目描述

给出一个长度为 n(n≤106)n(n\le 10^6) 的序列 AA 和 m(m≤106)m(m\le 10^6) 个操作：

  1. 将序列中指定位置修改为 xx
  2. 给出 xx，求 Ax,Ax+1,...,AnA_x,A_{x+1},...,A_n 的不同后缀最小值个数

笔记

我们给每个询问和操作分配一个时间，第 ii 个询问或操作的时间是 i+1i+1。将序列的初始状态视为有 nn 个操作一，时间都是 11

然后我们对于每个位置，求出这个位置上哪些时间段内是哪些数，比如一个位置初始时是 11，在操作 33 被修改成了 55，那么我们就说这个位置的数在时间段 1∼31\sim 3 是 11，在时间段 4∼q+14\sim q+1 是 55

然后我们建立一个线段树，这个线段树的下标表示的是时间，维护在某个时间的后缀最小值为多少

然后我们从序列的最后一个位置开始向前枚举，当我们枚举到一个位置时，这个位置可能在不同时间有不同的数字，因此不同的时间，这个位置开始的后缀最小值也是不一样的。我们可以根据之前求出的哪些时间段内是哪些数，进行区间取 min。同时，可能还会存在关于这个位置的询问，但我们目前做的只能知道这个位置在不同时间的后缀最小值是多少

我们考虑，当我们从序列的最后一个位置开始向前枚举，不断在某个时间点上对一些数字取 minmin 的时候，成功取 min （即取 min 后数字变得更小了）的次数即为，在当前时间点上，从当前枚举到的位置作为起点开始的后缀最小值个数。成功取 min 的次数可以在区间取 min 的时候顺手记录

因此，关于这个位置的询问，我们只需要根据这个询问的时间点，在线段树上进行单点询问即可

回顾我们这个离线的过程，从序列的最后一个位置开始向前枚举，可以使得当前的状态仅由后面的位置贡献产生；线段树维护在某个时间的后缀最小值为多少，可以做到快速处理修改操作产生的后续影响

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 1000006
#define LOCAL
namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;
struct Node{int mx,se,val,tag;} tree[_<<2];
inline void pushup(int k){
    nt.mx=max(lt.mx,rt.mx);
    if(lt.mx==rt.mx) nt.se=max(lt.se,rt.se);
    else nt.se=max(min(lt.mx,rt.mx),max(lt.se,rt.se));
}
inline void update(int k,int v,int d){if(v<nt.mx) nt.mx=nt.tag=v,nt.val+=d;}
inline void pushdown(int k){if(nt.tag) update(ls(k),nt.tag,nt.val),update(rs(k),nt.tag,nt.val),nt.tag=0,nt.val=0;}
void build(int k,int l,int r){
    if(l==r) return nt.mx=inf,nt.se=-1,void();
    int mid=(l+r)>>1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    pushup(k);
}
void modify(int k,int l,int r,int x,int y,int v){
    if(nt.mx<=v) return;
    if(l>=x&&r<=y&&nt.se<v) return update(k,v,1),void();
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) modify(ls(k),l,mid,x,y,v);
    if(y>mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query(int k,int l,int r,int x){
    if(l==r) return nt.val;
    int mid=(l+r)>>1;
    pushdown(k);
    if(x<=mid) return query(ls(k),l,mid,x);
    else return query(rs(k),mid+1,r,x);
}
struct O{int x,l,r;};
struct Q{int id,time;};
vector<O> g[_];
vector<Q> q[_];
int cntq,ans[_];
inline void subtask(){
    int n,m;read(n),read(m);
    for(int i=1,x;i<=n;i++) read(x),g[i].push_back(O{x,1,m+1});
    for(int i=1;i<=m;i++){
        int op,x,v;read(op),read(x);
        if(op==1){
            read(v);
            (*(--g[x].end())).r=i-1;
            g[x].push_back(O{v,i,m+1});
        }else q[x].push_back(Q{++cntq,i});
    }
    build(1,1,m+1);
    for(int i=n;i>=1;i--){
        for(auto to:g[i]) modify(1,1,m+1,to.l,to.r,to.x);
        for(auto to:q[i]) ans[to.id]=query(1,1,m+1,to.time);
    }
    for(int i=1;i<=cntq;i++) put(ans[i]);
}
signed main(){
    //ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

GSS2 - Can you answer these queries II

https://www.luogu.com.cn/problem/SP1557

题目描述

给出 nn 个数，qq 次询问，求最大字段和，相同的数字只算一次，选出的子段可以为空，1≤n,q≤1051\le n,q\le 10^5

笔记

先不考虑相同的数字只算一次如何处理

先把询问离线下来，按询问区间右端点从小到大排序。然后枚举询问，不断从左到右添加数字到线段树中，直到添加的位置到达了询问的右端点。对于第 ii 个数字 aia_i，我们让线段树上区间 [1,i][1,i] 全加上 aia_i，这样线段树上维护的就是从当前询问的右端点开始，往前的前缀和

但是我们选出的子段不一定要包含当前询问的右端点。比如最大子段是区间 [l,r][l,r]，当前询问的右端点为 RR，那么rr 到 RR 之间的数字是不应该产生贡献的，也就是之前线段树 ll 位置的值很大，但随着 rr 到 RR 之间的数字加入，ll 位置的值变小了。我们发现为了得到 ll 位置的最大值，可以考虑维护区间的历史最大值

现在考虑相同的数字只算一次，我们只需要记录当前数字 aia_i 上一次的出现位置 pp，然后让区间 [p+1,i][p+1,i] 加上 aia_i 就可以了

cpp
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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair<int,int> pii;
#define _ 100005
const int off=100000;
struct Node{int add,hadd,mx,hmx;} tree[_<<2];
int n,m,in[_],las[_<<3];
inline void pushup(int k){nt.mx=max(lt.mx,rt.mx),nt.hmx=max(lt.hmx,rt.hmx);}
inline void pushadd(int k,int v,int hv){
    nt.hadd=max(nt.hadd,nt.add+hv);
    nt.hmx=max(nt.hmx,nt.mx+hv);
    nt.add+=v,nt.mx+=v;
}
inline void pushdown(int k){pushadd(ls(k),nt.add,nt.hadd);pushadd(rs(k),nt.add,nt.hadd);nt.add=nt.hadd=0;}
void modify(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y) return pushadd(k,v,v),void();
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls(k),l,mid,x,y,v);
    if(y>mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y) return nt.hmx;
    pushdown(k);
    int mid=(l+r)>>1,res=-inf;
    if(x<=mid) res=max(res,query(ls(k),l,mid,x,y));
    if(y>mid) res=max(res,query(rs(k),mid+1,r,x,y));
    return res;
}
struct Q{int index,l,r,ans;} q[_];
inline void subtask(){
    cin>>n;for(int i=1;i<=n;i++) cin>>in[i];cin>>m;
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].index=i;
    sort(q+1,q+m+1,[](Q x,Q y){return x.r<y.r;});
    for(int i=1,p=0;i<=m;i++){
        while(p<q[i].r){
            p++;
            modify(1,1,n,las[off+in[p]]+1,p,in[p]);
            las[off+in[p]]=p;
        }
        q[i].ans=query(1,1,n,q[i].l,q[i].r);
    }
    sort(q+1,q+m+1,[](Q x,Q y){return x.index<y.index;});
    for(int i=1;i<=m;i++) cout<<q[i].ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}

  1. 洛谷-灵梦 《区间最值操作与区间历史最值详解》 ↩︎

  2. etilletaS_ 《势能线段树专题》 ↩︎

  3. 吉如一《区间最值操作与历史最值问题》 见 2016年国家集训队论文集 ↩︎

最后更新于：2025-04-03 14:16:05
Caiwen
本文作者
一只蒟蒻，爱好编程和算法
Caiwen的博客
Powered by Next.js
All Copyright Reserved © 2022-2025
冀ICP备2024080902号-1
冀公网安备13090202000724号