首页 > 其他 > 详细

【bzoj3747】Kinoman[POI2015](线段树)

时间:2018-01-18 11:01:06      阅读:131      评论:0      收藏:0      [点我收藏+]

  题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3747

  对于这种题,考虑固定区间的右端点为r,设区间左端点为l能取得的好看值总和为a[l],那么就相当于当r取不同取值时所有al的最大值。

  设last[i]表示第i部电影上一次出现的位置,当右端点r右移1位时,因为只有看了一遍的电影能获取好看值,所以能取得f[r]的好看值的al只能是在last[r]~r这个区间。因此每次右移时,last[last[r]]+1~last[r]减去w[f[r]],last[r]+1~r加上w[f[r]]。

  具体实现, 就是维护一个资瓷区间加与查询区间最大的线段树。

  代码(常数真大):

技术分享图片
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 1ll<<60
ll read()
{
    ll tmp=0; char c=getchar(),f=1;
    for(;c<0||9<c;c=getchar())if(c==-)f=-1;
    for(;0<=c&&c<=9;c=getchar())tmp=tmp*10+c-0;
    return tmp*f;
}
using namespace std;
struct point{
    ll delta,mx;
}a[4000010];
ll w[1000010];
int f[1000010],last[1000010],pos[1000010];
int n,m;
void add(int now,int l,int r,int x,int y,ll k)
{
    if(x<=l&&r<=y){
        a[now].delta+=k; a[now].mx+=k;
    }
    else{
        int mid=(l+r)>>1;
        if(x<=mid)add(now<<1,l,mid,x,y,k);
        if(mid<y)add(now<<1|1,mid+1,r,x,y,k);
        a[now].mx=max(a[now<<1].mx,a[now<<1|1].mx)+a[now].delta; 
    }
}
ll getmax(int now,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return a[now].mx;
    else{
        ll tmp=-inf; int mid=(l+r)>>1;
        if(x<=mid)tmp=max(tmp,getmax(now<<1,l,mid,x,y));
        if(mid<y)tmp=max(tmp,getmax(now<<1|1,mid+1,r,x,y));
        return tmp+a[now].delta;
    }
}
int main()
{
    int i;
    n=read(); m=read();
    last[0]=-1;
    for(i=1;i<=n;i++){
        f[i]=read();
        if(!pos[f[i]])last[i]=0;
        else last[i]=pos[f[i]];
        pos[f[i]]=i;
    }
    for(i=1;i<=m;i++)w[i]=read();
    ll ans=-inf;
    for(i=1;i<=n;i++){
        add(1,1,n,last[i]+1,i,w[f[i]]);
        if(~last[last[i]])add(1,1,n,last[last[i]]+1,last[i],-w[f[i]]);
        ans=max(ans,getmax(1,1,n,1,i));
    }
    printf("%lld\n",ans);
}
bzoj3747

 

【bzoj3747】Kinoman[POI2015](线段树)

原文:https://www.cnblogs.com/quzhizhou/p/8308879.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!