首页 > 其他 > 详细

[POI2015]KIN (线段树)

时间:2018-10-04 20:49:00      阅读:157      评论:0      收藏:0      [点我收藏+]

题目链接


Solution

线段树.
观察题目可以得到一个小 \(trick\) :
对于任意一个节点 \(i\) ,那么和它颜色相同的上一个节点 \(pre[i]\),肯定不会放在一个区间.
于是考虑对于每一个节点计算它可以献出贡献的区间.
\(O(n)\) 扫出每一个点的 \(pre\) .
然后从左往右,一次将节点可以贡献的范围即 \([pre_i~,~nxt_i)\).
同时将同颜色的上一个节点贡献删除.
然后线段树统计全局最大值即可.

Code

#include<bits/stdc++.h>
#define N 1000008
#define ll long long
#define mid (l+r>>1)
#define in(x) x=read()
using namespace std;

int read()
{
    char ch=getchar(); int w=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
    return w;
}
ll pre[N],sgx[N*4],n,k,lazy[N*4];
ll col[N],w[N],lst[N],ans;

void push_down(int node)
{
    if(!lazy[node])return;
    lazy[node<<1]+=lazy[node]; lazy[node<<1|1]+=lazy[node];
    sgx[node<<1|1]+=lazy[node]; sgx[node<<1]+=lazy[node];
    lazy[node]=0;
}

void change(int node,int l,int r,int L,int R,int v)
{
    if(l>R||r<L)return;
    if(l>=L&&r<=R){lazy[node]+=v;sgx[node]+=v;return;}
    push_down(node);
    change(node<<1,l,mid,L,R,v);
    change(node<<1|1,mid+1,r,L,R,v);
    sgx[node]=max(sgx[node<<1],sgx[node<<1|1]);
    return;
}

int main()
{
    in(n),in(k);
    for(int i=1;i<=n;i++){
        in(col[i]);
        pre[i]=lst[col[i]];
        lst[col[i]]=i;
    }
    for(int i=1;i<=k;i++)in(w[i]);
    for(int i=1;i<=n;i++){
        change(1,1,n,pre[i]+1,i,w[col[i]]);
        change(1,1,n,pre[pre[i]]+1,pre[i],-w[col[i]]);
        ans=max(ans,sgx[1]);
    }
    cout<<ans<<endl;
}

[POI2015]KIN (线段树)

原文:https://www.cnblogs.com/Kv-Stalin/p/9743307.html

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