摘要:线段树维护全局多少位置是前缀最大值

luogu4198楼房重建

题面

在下午机房外面的走廊一边晒太阳一边想题好舒服啊…

题目分析

首先显然是先算出楼房顶部的斜率,然后查询有多少位置是前缀最大值.

至于这个怎么维护,可以使用线段树,节点信息为此节点表示的区间的最大值和仅考虑该区间的答案.

考虑如何向上合并节点信息,明显在合并时左区间已经求得的答案并不会受到影响,因为只有右区间的点会被挡住,分两种情况:

  • 左区间的最大值大于等于右区间的最大值,这时候答案为左区间的答案.
  • 左区间的最大值小于右区间的最大值,答案为左区间答案和右区间大于左区间最大值的点的个数.

右区间大于左区间最大值的点的个数可以递归求得,递归过程也是分两种情况,这里将左区间的最大值视为限制:

  • 当前递归区间的左区间最大值小于等于限制,那么这个左区间对答案的贡献为0,答案为对右区间进行递归获得的答案.
  • 当前递归区间的左区间最大值大于限制,那么当前区间的答案为对左区间进行递归获得的答案加上右区间满足限制为左区间最大值的答案.

为什么是右区间满足限制为左区间最大值呢,因为这个情况下左区间的最大值大于限制,所以对于右区间来说原来的限制就被左区间的最大值取代了.

因为不知道怎么考虑在左区间的限制下右区间的答案,开始想的是对右区间进行一次同样的递归,限制改为新的限制,但是复杂度明显不对于是拿了50分.

想了一会后发现因为我们对于一段区间的答案是仅考虑这一段区间的,那么整个区间的答案就包含了左区间的答案和在左区间的限制下的右区间的答案,用整个的答案减掉左区间答案就得到了右区间在左区间限制下的答案.

代码

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
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%Lf\n",x)
#define endl putchar('\n')
typedef long long lxl;
typedef long double lbl;
const lxl big=100010;
lxl n,m,NodeCnt,root;
lxl c[2][big<<2],sum[big<<2],y[big];
lbl max[big<<2];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
lxl calc(lxl t,lxl l,lxl r,lbl limit)
{
if(l==r)return max[t]>limit;
lxl lson=c[0][t],rson=c[1][t],chiha(0),mid((l+r)>>1);
if(max[lson]<=limit)chiha+=calc(rson,mid+1,r,limit);
else chiha+=calc(lson,l,mid,limit)+sum[t]-sum[lson];
return chiha;
}
inline void PushUp(lxl t,lxl l,lxl r)
{
max[t]=std::max(max[c[0][t]],max[c[1][t]]);
if(max[c[1][t]]<=max[c[0][t]])sum[t]=sum[c[0][t]];
else sum[t]=sum[c[0][t]]+calc(c[1][t],((l+r)>>1)+1,r,max[c[0][t]]);
}
void BuildTree(lxl &t,lxl l,lxl r)
{
if(!t)t=++NodeCnt;
if(l==r)return;
lxl mid((l+r)>>1);
BuildTree(c[0][t],l,mid),BuildTree(c[1][t],mid+1,r);
}
void modify(lxl t,lxl l,lxl r,lxl x)
{
if(l==r){y[l]=read(),max[t]=(lbl)((lbl)y[l]/(lbl)l),sum[t]=1;return;}
lxl mid((l+r)>>1);
if(x<=mid)modify(c[0][t],l,mid,x);
else modify(c[1][t],mid+1,r,x);
PushUp(t,l,r);
}
int main(void)
{
// freopen("P4198_2.in","r",stdin);
// freopen("test.out","w",stdout);
n=read(),m=read();
BuildTree(root,1,n);
for(R int i(1);i<=m;++i)
{
lxl x=read();
modify(root,1,n,x);
printf("%lld\n",sum[root]);
}
return 0;
}