题目链接：https://www.luogu.com.cn/problem/P4198

题目大意：维护有多少个不同的前缀最大值（相同数值但是位置更靠后的认为更大且两数不同，即认为每个数字加上与位置成正比的浮动）

做法

非常经典的题目，众所周知，信息学有一类题目的出题方法就是打破常规。

这道题目就是个经典的打破常规的题目，当然你也可以从别的角度去看他。

正常的线段树 updata 都是 $O(1)$ 的，但是这道题目的 updata 是 $\log$ 的。

更详细的来说，维护这么一个函数 $g(x,k)$ ，能够维护 $x$ 所管理的区间中 $\ge k$ 的不同前缀最大值个数。

这个函数可以 $\log$ ，当左区间的最大值 $<k$ ，那么直接去右区间，左区间贡献为 $0$ 。否则，说明考虑左区间的话，对右区间的不同前缀最大值没有影响，直接去左区间就行了，而右区间的贡献就是 $x$ 的不同前缀最大值个数，减去左儿子的。（满足可减性）

用这个函数可以在 $\log$ 的时间轻松实现 updata ，这样就可以在 $O(\log^2)$ 的时间解决这个问题。

显然，这个做法还能轻松实现区间不同的前缀最大值个数。

时间复杂度： $O(n+q\log^2n)$ 。

空间复杂度： $O(n)$ 。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5;
const int NN=2e5+5;
const double eps=1e-8;
struct Fac{LL a,b;};
bool operator<(Fac x,Fac y){return x.a*y.b<x.b*y.a;}
bool operator<=(Fac x,Fac y){return !(y<x);}
Fac a[N];
struct node{
    int lc,rc,c;
    Fac mx;
}tr[NN];int len;
int findans(int x,int l,int r,Fac k){
    if(l==r)return k<=tr[x].mx && tr[x].mx.a;
    int mid=(l+r)>>1;
    if(tr[tr[x].lc].mx<k)return findans(tr[x].rc,mid+1,r,k);
    else return tr[x].c-tr[tr[x].lc].c+findans(tr[x].lc,l,mid,k);
}
void updata(int x,int l,int mid,int r){
    assert(tr[x].lc && tr[x].rc);
    tr[x].mx=max(tr[tr[x].lc].mx,tr[tr[x].rc].mx);
    tr[x].c=tr[tr[x].lc].c+findans(tr[x].rc,mid+1,r,tr[tr[x].lc].mx);
}
int bt(int l,int r){
    int x=++len;
    if(l<r){
        int mid=(l+r)>>1;
        tr[x].lc=bt(l,mid);
        tr[x].rc=bt(mid+1,r);
        updata(x,l,mid,r);
    }
    else tr[x].mx=a[l];
    return x;
}
void change(int x,int l,int r,int id,Fac k){
    if(l==r){
        tr[x].mx=k;
        tr[x].c=k.a>0;
        return ;
    }
    int mid=(l+r)>>1;
    if(id<=mid)change(tr[x].lc,l,mid,id,k);
    else change(tr[x].rc,mid+1,r,id,k);
    updata(x,l,mid,r);
}
int n,q;
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)a[i]={0,1};
    bt(1,n);
    for(int i=1;i<=q;i++){
        int x,y;scanf("%d%d",&x,&y);
        a[x]={y,x};
        change(1,1,n,x,a[x]);
        printf("%d\n",tr[1].c);
    }
    return 0;
}

当然，这个问题还能扩展。

思考一下，假如维护的信息不满足可减性怎么办呢？

答案是每个点不维护区间的答案，而是维护在考虑左区间的情况下右区间的贡献即可。

这个方法又有个别名，叫兔队线段树。

原链接在这：https://www.cnblogs.com/PinkRabbit/p/Segment-Tree-and-Prefix-Maximums.html

一道练习题在这：https://codeforces.com/contest/671/problem/E

具体做法看原链接吧，我感觉粉兔已经说的很明白了。其实是因为我懒