BZOJ 3747 POI2015 Kinoman

因为上午没有准备够题目,结果发现写完这道题没题可写了QAQ

又因为这道题范围是100w,我写了发线段树,以为要T,上午就花了一个小时拼命卡常数

结果下午一交居然过了QAQ

我们考虑枚举L,求最大R使得[L,R]是对于当前L最大权值的区间

考虑每个点的影响

如果从L向右他是第一个,那么他会对后面产生a[f[L]]的贡献

如果从L向右他是第二个,那么他会对后面产生-a[f[L]]的贡献

然后我们维护一棵线段树,每次查询最值并且进行更新即可

include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std; typedef long long LL;
const int maxn=1000010;
int n,m,x,y,v,tim;
int f[maxn];
int a[maxn];
int next[maxn],h[maxn];
LL mx[maxn<<2],add[maxn<<2];
LL ans=0,tot=0; inline void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
}
inline LL Max(LL a,LL b){return a>b?a:b;}
inline void push_down(int o){
int L=(o<<1),R=(L|1);
add[L]+=add[o];mx[L]+=add[o];
add[R]+=add[o];mx[R]+=add[o];
add[o]=0;
}
inline void modify(int o,int L,int R){
if(L>=x&&R<=y){
mx[o]+=v;add[o]+=v;
return;
}
if(add[o]!=0)push_down(o);
int mid=(L+R)>>1;
if(y<=mid)modify(o<<1,L,mid);
else if(x>mid)modify(o<<1|1,mid+1,R);
else modify(o<<1,L,mid),modify(o<<1|1,mid+1,R);
mx[o]=Max(mx[o<<1],mx[o<<1|1]);
}
inline LL ask(int o,int L,int R){
if(L>=x&&R<=y)return mx[o];
if(add[o]!=0)push_down(o);
int mid=(L+R)>>1;
if(y<=mid)return ask(o<<1,L,mid);
else if(x>mid)return ask(o<<1|1,mid+1,R);
else return Max(ask(o<<1,L,mid),ask(o<<1|1,mid+1,R));
}
int main(){
read(n);read(m);y=n;
for(int i=1;i<=n;++i)read(f[i]);
for(int i=1;i<=m;++i)read(a[i]);
for(int i=n;i>=1;--i){
next[i]=h[f[i]];
h[f[i]]=i;
}
for(int i=1;i<=m;++i){
if(h[i]){
x=h[i];v=a[i];
modify(1,1,n);
if(next[h[i]]){
x=next[h[i]];v=-a[i];
modify(1,1,n);
}
}
}
for(int L=1;L<=n;++L){
x=L;
ans=Max(ans,ask(1,1,n)-tot);
tot+=a[f[L]];
int n1=next[L],n2=next[n1];
if(n1){
x=n1;v=(a[f[L]]<<1);
modify(1,1,n);
}
if(n2){
x=n2;v=-a[f[L]];
modify(1,1,n);
}
}printf("%lld\n",ans);
return 0;
}

  

上一篇:【转】Linux定时任务之 【crontab】


下一篇:Poj2676