【数据结构】bzoj3747Kinoman

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。

=========================================华丽丽的分割线===============================================

没什么难的吧，直接枚举左端点，然后右端点用一个线段树维护出最大值。

每一次改变左端点的时候，总会有一些点的值改变，然后发现就是几个区间修改。

然后直接写就好辣。

时间复杂度O(nlogn)，代码如下：

 1 #include <bits/stdc++.h>
 2 #define Maxn 1000007
 3 using namespace std;
 4 int read()
 5 {
 6     int x=0,f=1;char ch=getchar();
 7     while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
 8     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 9     return x*f;
10 }
11 struct seg
12 {
13     int lx,rx;
14     long long tag,mx;
15 };
16 int n,m;
17 int f[Maxn],w[Maxn];
18 int next[Maxn],last[Maxn];
19 seg tree[Maxn*4];
20 long long ans=0;
21 void build(int node, int l, int r)
22 {
23     tree[node].lx=l,tree[node].rx=r;
24     tree[node].tag=0,tree[node].mx=0;
25     if (l==r) return;
26     int mid=(l+r)/2;
27     build(node*2,l,mid);
28     build(node*2+1,mid+1,r);
29 }
30 void pushdown(int node)
31 {
32     if (tree[node].tag==0) return;
33     tree[node*2].tag+=tree[node].tag;
34     tree[node*2].mx+=tree[node].tag;
35     tree[node*2+1].tag+=tree[node].tag;
36     tree[node*2+1].mx+=tree[node].tag;
37     tree[node].tag=0;
38 }
39 void update(int node, int l, int r, long long del)
40 {
41     if (tree[node].rx<l) return;
42     if (tree[node].lx>r) return;
43     if (tree[node].lx>=l&&tree[node].rx<=r)
44     {
45         tree[node].tag+=del;
46         tree[node].mx+=del;
47         return;
48     }
49     pushdown(node);
50     update(node*2,l,r,del);
51     update(node*2+1,l,r,del);
52     tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
53 }
54 int main()
55 {
56     n=read(),m=read();
57     memset(f,0,sizeof(f));
58     for (int i=1;i<=n;i++)
59         f[i]=read();
60     memset(w,0,sizeof(w));
61     for (int i=1;i<=m;i++)
62         w[i]=read();
63     memset(last,0,sizeof(last));
64     for (int i=n;i;i--)
65     {
66         next[i]=last[f[i]];
67         last[f[i]]=i;
68     }
69     build(1,1,n);
70     for (int i=1;i<=m;i++)
71         if (last[i])
72         {
73             if (next[last[i]]>0)
74                 update(1,last[i],next[last[i]]-1,w[i]);
75             else update(1,last[i],n,w[i]);
76         }
77     for (int i=1;i<=n;i++)
78     {
79         ans=max(ans,tree[1].mx);
80         int pos=next[i];
81         if (pos>0)
82         {
83             update(1,i,pos-1,-w[f[i]]);
84             if (next[pos]>0)
85                 update(1,pos,next[pos]-1,w[f[i]]);
86             else update(1,pos,n,w[f[i]]);
87         } else update(1,i,n,-w[f[i]]);
88     }
89     printf("%lld
",ans);
90     return 0;
91 }