题目链接
思路
考虑枚举右端点。首先考虑应用前缀和，对于一个r，找一个最小的sum[l]，把需要去掉的部分也放到sum[l]里。但这种做法是错的….对于一个i，把他上一次出现的位置记做pre[i]，每次把1到pre[i]之间所有区间的前缀和都加上一个w[i]，但是不论如何区间中第一次出现的数是会被计算的，所以这样不可以。
考虑另一种表示方式，对于每个遇到的 i ，把1到 i 这段都加上w[i]，这样的话sum[j]就表示的是 j 到 i 的连续区间和。然后考虑如何使得每个pre[i]之前的位置第i种电影的贡献是0。重新考察刚刚那种做法为什么不对，不把那个多出来的次数当成第一个数，而是理解为每次区间中有一个重复的，我们会在求和的时候加一次，减去的时候减一次，相当于没有减。于是这次我们考虑不让他加上，只减去。于是每次遇到一个i，是把pre[i]+1到i加上w[i]，把pre[pre[i]]+1到pre[i]减去，这样使得任意pre[i]之前的都不会计算 i 的贡献。 回顾我们的表示方法，他的好处是使得我们可以控制加减的范围，而当使用前缀和的时候，我们无法控制每个值加在了哪里，只能进行减，于是无法操作。 如果还没有理解的可以看看代码UPD:（套路部分）
对于一类允许离线，且对区间中数字出现个数有要求的题目，可以考虑按顺序将点加入，然后适当对pre[u], pre[pre[u]]等进行修改操作代码
#include#include #include #include #include #include #include #include #define MAXN 1000050#define INF (1<<28)#define LLINF (1LL<<40)#define LL long longusing namespace std;int n, m, f[MAXN], w[MAXN], pre[MAXN], app[MAXN];struct node{ LL maxn, lazy;}t[MAXN<<2];void push_down(int u){ if(t[u].lazy){ t[u<<1].lazy += t[u].lazy, t[u<<1].maxn += t[u].lazy; t[u<<1|1].lazy += t[u].lazy, t[u<<1|1].maxn += t[u].lazy; t[u].lazy = 0; }}void add(int u, int l, int r, int tl, int tr, int x){ if(tl > tr) return; if(tl <= l && r <= tr){ t[u].maxn += x, t[u].lazy += x; return; } push_down(u); int mid = (l+r)>>1; if(tl <= mid) add(u<<1, l, mid, tl, tr, x); if(mid < tr) add(u<<1|1, mid+1, r, tl, tr, x); t[u].maxn = max(t[u<<1].maxn, t[u<<1|1].maxn);}LL query(int u, int l, int r, int tl, int tr){ if(tl <= l && r <= tr){ return t[u].maxn; } push_down(u); int mid = (l+r)>>1; LL ret = 0; if(tl <= mid) ret = max(ret, query(u<<1, l, mid, tl, tr)); if(mid < tr) ret = max(ret, query(u<<1|1, mid+1, r, tl, tr)); return ret;}/*共有m部电影，编号为1~m，第i部电影的好看值为w[i]。在n天之中（从1~n编号）每天会放映一部电影，第i天放映的是第f[i]部。你可以选择l,r(1<=l<=r<=n)，并观看第l,l+1,…,r天内所有的电影。如果同一部电影你观看多于一次，你会感到无聊，于是无法获得这部电影的好看值。所以你希望最大化观看且仅观看过一次的电影的好看值的总和。输入输出格式输入格式：第一行两个整数n,m(1<=m<=n<=1000000)。第二行包含n个整数f[1],f[2],…,fn。第三行包含m个整数w[1],w[2],…,wm。输出格式：输出观看且仅观看过一次的电影的好看值的总和的最大值。*/ int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &f[i]); pre[i] = app[f[i]]; app[f[i]] = i; } LL ans = 0; for(int i = 1; i <= m; i++) scanf("%d", &w[i]); for(int i = 1; i <= n; i++) { add(1, 1, n, pre[i]+1, i, w[f[i]]); add(1, 1, n, pre[pre[i]]+1, pre[i], -w[f[i]]); /* The following 2 lines are wrong! add(1, 1, n, 1, i, w[f[i]]); add(1, 1, n, 1, pre[i], -w[f[i]]); */ ans = max(ans, query(1, 1, n, 1, n)); } printf("%lld", ans); return 0;}