Codevs 5914 [SXOI2016]最大值

Codevs 5914 [SXOI2016]最大值

Codevs 5914 [SXOI2016]最大值

70分算法+30分打表

#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define lc k<<1
#define rc k<<1|1
#define EF if(ch==EOF) return x;
using namespace std;
const int N=1e5+;
const int inf=2e9;
typedef long long ll;
int n,Q,ans,a[N],mx[N];
ll sum[N<<];bool tag[N<<];
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;EF;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void build(int k,int l,int r){
if(l==r){
sum[k]=mx[l];
return ;
}
int mid=l+r>>;
build(lc,l,mid);
build(rc,mid+,r);
sum[k]=sum[lc]+sum[rc];
}
void pushdown(int k,int l,int r){
if(!tag[k]||l==r) return ;
int mid=l+r>>;
sum[lc]=sum[k]/(r-l+)*(mid-l+);
sum[rc]=sum[k]/(r-l+)*(r-mid);
tag[lc]=tag[rc]=;tag[k]=;
}
void change(int k,int l,int r,int x,int y,int v){
if(l==x&&r==y){
sum[k]=1LL*(r-l+)*v;
tag[k]=;
return ;
}
pushdown(k,l,r);
int mid=l+r>>;
if(y<=mid) change(lc,l,mid,x,y,v);
else if(x>mid) change(rc,mid+,r,x,y,v);
else change(lc,l,mid,x,mid,v),change(rc,mid+,r,mid+,y,v);
sum[k]=sum[lc]+sum[rc];
}
ll query(int k,int l,int r,int p){
if(l==r) return sum[k];
pushdown(k,l,r);
int mid=l+r>>;
if(p<=mid) return query(lc,l,mid,p);
else return query(rc,mid+,r,p);
// sum[k]=sum[lc]+sum[rc];
}
void ord(){
int Max=-inf;ans=;
for(int j=;j<=n;j++){
Max=max(Max,a[j]);
ans+=Max;
}
printf("%d\n",ans);
for(int i=,x,y;i<=Q;i++){
x=read();y=read();
a[x]+=y;
int Max=-inf;ans=;
for(int j=;j<=n;j++){
Max=max(Max,a[j]);
ans+=Max;
}
printf("%d\n",ans);
}
}
int main(){
n=read();
for(int i=;i<=n;i++) a[i]=read();Q=read();
if(n<=){
ord();
return ;
}
mx[]=-inf;
for(int i=;i<=n;i++) mx[i]=max(mx[i-],a[i]);
build(,,n);printf("%I64d\n",sum[]);
for(int i=,x,y;i<=Q;i++){
x=read();y=read();
a[x]+=y;
int l=x,r=n,pos=;
while(l<=r){
int mid=l+r>>;
if(query(,,n,mid)<a[x]) l=mid+,pos=mid;
else r=mid-;
}
if(pos) change(,,n,x,pos,a[x]);
printf("%I64d\n",sum[]);
}
return ;
}

如果你会线段树log^2求单调栈的话..此题可做

你考虑。。

维护每个区间的答案

以及一个看似暴力的询问函数(x,y)

表示从x节点出发 左边max是y的答案

然后你会发现每次只需要递归到一侧

就log^2了

对啊……好像是维护斜率啥的吧……

不是斜率

讨论最大值的来源

是这样的

对于x

左边最大值是y

如果你发现x左儿子最大值<=y

那么显然没有递归左儿子的必要

否则递归完左儿子后,右儿子的答案与y无关

因为变成了x左儿子的最大值

这个通过线段树之前维护的信息就可以知道

每次都只会递归一侧

不管是查询还是信息合并都用这个logn的函数就好了

线段树维护的是什么呀?
区间最大值
以及区间的答案

可以参考:上帝之手

上一篇:PHP递归创建多级目录(一道面试题的解题过程)


下一篇:Java数组一定要初始化才能使用吗?