3747: [POI2015]Kinoman
Time Limit: 60 Sec
Memory Limit: 128 MB
[
Submit][
Status][
Discuss]
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
Sample Output
15 样例解释： 观看第2,3,4,5,6,7天内放映的电影，其中看且仅看过一次的电影的编号为2,3,4。
HINT
遍历左区间，右区间则线段树求最值
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 1000000 + 5;
const ll inf = 1e18;
int f[N],nxt[N],last[N],ls[N*4],rs[N*4],m,n,sz,root;
ll w[N],mx[N*4],flag[N*4],a[N],ans=-inf;
void update( int nd ){ mx[nd] = max( mx[ls[nd]], mx[rs[nd]] ); }
void pushdown( int nd ){
if( flag[nd] ){
mx[ls[nd]] += flag[nd]; flag[ls[nd]] += flag[nd];
mx[rs[nd]] += flag[nd]; flag[rs[nd]] += flag[nd];
flag[nd] = 0;
}
}
void build( int &nd, int l, int r ){
nd = ++sz;
if( l == r ){ mx[nd] = a[l]; return ; }
int mid = (l+r)>>1;
build( ls[nd], l, mid ); build( rs[nd], mid+1, r );
update(nd);
}
void modify( int nd, int l, int r, int L, int R, ll val ){
if( L <= l && R >= r ){
mx[nd] += val;
flag[nd] += val;
return;
}
int mid = (l+r)>>1;
pushdown(nd);
if( L <= mid ) modify( ls[nd], l, mid , L, R, val );
if( R > mid ) modify( rs[nd], mid+1, r, L, R, val );
update(nd);
}
ll query( int nd, int l, int r, int L, int R ){
if( L <= l && R >= r ) return mx[nd];
ll res = -inf; int mid = (l+r)>>1;
pushdown(nd);
if( L <= mid ) res = max( res, query( ls[nd], l, mid, L, R ) );
if( R > mid ) res = max( res, query( rs[nd], mid+1, r, L, R ) );
return res;
}
int main(){
scanf("%d%d", &n, &m);
for( int i = 1; i <= n; i++ ) scanf("%d", &f[i]), nxt[i] = n+1; nxt[n+1] = n+1;
for( int i = 1; i <= m; i++ ) scanf("%lld", &w[i]), last[i] = n+1;
for( int i = n; i >= 1; i-- ){
nxt[i] = last[f[i]];
last[f[i]] = i;
}
for( int i = 1; i <= m; i++ ){
if( last[i] <= n ) a[last[i]] += w[i];
if( nxt[last[i]] <= n ) a[nxt[last[i]]] -= w[i];
}
for( int i = 1; i <= n; i++ ) a[i] += a[i-1];
build( root, 1, n );
for( int i = 1; i <= n; i++ ){
int now = i;
ans = max( ans, query(root,1,n,now,n) );
modify(root,1,n,now,n,-w[f[i]]);
if( nxt[now] <= n ) modify(root,1,n,nxt[now],n,2*w[f[i]]), now = nxt[now];
if( nxt[now] <= n ) modify(root,1,n,nxt[now],n,-w[f[i]]);
}
printf("%lld", ans);
return 0;
}
总结
query怎能忘了返回值呢？
