「BZOJ3747」[POI2015] Kinoman
Description
共有m部电影，编号为1~m，第i部电影的好看值为w[i]。
在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。
你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。
Input
第一行两个整数n,m(1<=m<=n<=1000000)。
第二行包含n个整数f[1],f[2],…,f[n](1<=f[i]<=m)。
第三行包含m个整数w[1],w[2],…,w[m](1<=w[j]<=1000000)。
Output
输出观看且仅观看过一次的电影的好看值的总和的最大值。
Sample Input
9 4
2 3 1 1 4 1 2 4 1
5 3 6 6
2 3 1 1 4 1 2 4 1
5 3 6 6
Sample Output
15
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
样例解释：
观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
题解
不得不说我的代码超级慢
线段树经典题
nxt[i]记录第i天的电影下次播放时间
枚举区间左端点，线段树维护每个位置作为右端点的答案
考虑l-r的左端点变为l+1
发现l到nxt[l]-1的答案减少w[f[l]]
而nxt[l]到nxt[nxt[l]]-1增加w[f[l]]
线段树维护，支持区间修改以及查询最大值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #define ll long long using namespace std; int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m; int f[1000005],w[1000005]; int last[1000005],nxt[1000005]; ll ans; struct seg{ int l,r; ll tag,mx; }t[4000005]; void pushdown(int k) { int l=t[k].l,r=t[k].r; if(l==r)return; ll tag=t[k].tag;t[k].tag=0; t[k<<1].tag+=tag;t[k<<1|1].tag+=tag; t[k<<1].mx+=tag;t[k<<1|1].mx+=tag; } void build(int k,int l,int r) { t[k].l=l;t[k].r=r; if(l==r)return; int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void add(int k,int x,int y,int val) { if(t[k].tag)pushdown(k); int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(l==x&&y==r) { t[k].tag=val;t[k].mx+=val; return; } if(y<=mid)add(k<<1,x,y,val); else if(x>mid)add(k<<1|1,x,y,val); else add(k<<1,x,mid,val),add(k<<1|1,mid+1,y,val); t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)f[i]=read(); for(int i=1;i<=m;i++)w[i]=read(); for(int i=n;i;i--) { nxt[i]=last[f[i]]; last[f[i]]=i; } build(1,1,n); for(int i=1;i<=m;i++) if(last[i]) { if(!nxt[last[i]])add(1,last[i],n,w[i]); else add(1,last[i],nxt[last[i]]-1,w[i]); } for(int i=1;i<=n;i++) { ans=max(ans,t[1].mx); int t=nxt[i]; if(t) { add(1,i,t-1,-w[f[i]]); if(nxt[t])add(1,t,nxt[t]-1,w[f[i]]); else add(1,t,n,w[f[i]]); } else add(1,i,n,-w[f[i]]); } printf("%lld\n",ans); return 0; } |
计数器 9774905
OI 课件=>
OI 课件=>
学长tql
黄学长我榜样