- 技术
- 求最大值（线段树+思维）
思路：最大值肯定存在相邻的数之间，用线段树维护区间最大值（用C++14会内存超限）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=2e5+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
struct node
{
int l
,r
;
int maxx
;
}tr
[N
<<2];
int a
[N
];
void push_up(int root
)
{
tr
[root
].maxx
=max(tr
[lson
].maxx
,tr
[rson
].maxx
);
return ;
}
void build(int l
,int r
,int root
)
{
tr
[root
].l
=l
;tr
[root
].r
=r
;
if(l
==r
)
{
tr
[root
].maxx
=a
[l
+1]-a
[l
];
return ;
}
int mid
=l
+r
>>1;
build(l
,mid
,lson
);
build(mid
+1,r
,rson
);
push_up(root
);
return ;
}
void update(int root
,int x
,int k
)
{
if(tr
[root
].l
==x
&&tr
[root
].r
==x
)
{
tr
[root
].maxx
=k
;
return ;
}
int mid
=tr
[root
].l
+tr
[root
].r
>>1;
if(mid
>=x
)
update(lson
,x
,k
);
else
update(rson
,x
,k
);
push_up(root
);
return ;
}
int main()
{
int n
;
while(~scanf("%d",&n
))
{
for(int i
=1;i
<=n
;i
++)
read(a
[i
]);
int m
;
read(m
);
build(1,n
-1,1);
while(m
--)
{
int x
,k
;
read(x
),read(k
);
a
[x
]=k
;
if(x
!=n
)update(1,x
,a
[x
+1]-a
[x
]);
if(x
!=1)update(1,x
-1,a
[x
]-a
[x
-1]);
int ans
=tr
[1].maxx
;
double res
=(double)ans
;
printf("%.2f\n",res
);
}
}
return 0;
}
Processed:
0.020, SQL:
9
