最近很有空，我填坑来了（
思路
这道题目有一个很困难的限制：重复玩的角色会让它带来的快乐值清零。我们考虑如何消去这个限制。
考虑如下方法：假如我们考虑 $1\cdots$ $r$ 玩的最大值。
区间内的最后一个 $x$ 类型角色玩它得到的快乐值是 $c_x$，倒数第二个 $x$ 类型角色玩它得到的快乐值是 $-c_x$
（这样意味着如果玩了这两个，那么快乐值就没了。）
其他的 $x$ 类型角色，因为都在这两个前面，想玩的话快乐值已经被清空了所以玩它得到的快乐值为 $0$，那么我们枚举选择区间的右端点，处理一下，就成了动态维护全体最大子段和。
模拟
如果没看懂，那我们来模拟一下样例：
3 3 6 2 6 1 3 1 1 2 1
首先枚举右端点 $r=1$，出现了一个新角色 $1$，目前的快乐值序列为：
3 0 0 0 0 0，最大子段和为 $3$
枚举右端点 $r=2$，又出现了一个新角色 $3$，快乐值序列为：
3 2 0 0 0 0，最大子段和为 $5$。
枚举右端点 $r=3$，此时出现了一个重复的 $1$，那么前面的那个快乐值变成负的。新的快乐值序列为：
-3 2 3 0 0 0，最大子段和为 $5$。
枚举右端点 $r=4$，此时又出现了一个 $1$，倒数第三个快乐值没了，倒数第二个要变成负的，新的快乐值序列为：
0 2 -3 3 0 0，最大子段和为 $3$。
（这里你可能会觉得有些问题，但你模拟一下游戏区间右端点为 $4$ 的情况你就知道没错。）
枚举右端点 $r=5$，这时出现了一个新的角色 $2$，快乐值序列变为：
0 2 -3 3 6 0，最大子段和为 $9$。
最后枚举右端点 $r=6$，又来了一个 $1$，快乐值序列变为：
0 2 0 -3 6 3，最大子段和为 $9$。
输出的答案为其中最大的一个，即 $9$，至此，这篇题解的大部分内容结束。
闲话
此题的数据范围是 $10^6$，首先要开 $LL$。其次，凭借着线段树巨大的常数，我们收获了一个 TLE，所以我们需要加最快的快读，$fread$：
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : * p1 ++) inline int rd () { int x = 0; char ch = getchar (); while (!isdigit(ch) ) ch = getchar (); while (isdigit(ch) ) { x = x * 10 + (ch ^ 48); ch = getchar (); } return x; }
当然，线段树的常数毕竟大，所以还是有几个点 TLE，我们加上 register，inline 还是有可能会超时，再加上卡常火车头勉强过了~
卡常火车头，（效果超强，慎用）本地机子运行能快个 $3$ 倍，当然加上进一步的指令集优化能够更快。
#pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks")
最后是 $AC$ 代码：
#pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include <iostream> #define int long long using namespace std; char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf; #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : * p1 ++) inline int read() { int x = 0; char ch = getchar (); while (!isdigit(ch) ) ch = getchar (); while (isdigit(ch) ) { x = x * 10 + ch - 48; ch = getchar (); } return x; } int n, m, t1, t2, ans; int c[1000005], x[1000005], last[1000005][2]; struct Segment_tree {int l, r, val, sum;}a[4000005]; inline void pushup (int l, int r, int k) { a[k].l = max (a[k << 1].l, a[k << 1].sum + a[k << 1 | 1].l); a[k].r = max (a[k << 1 | 1].r, a[k << 1 | 1].sum + a[k << 1].r); a[k].val = max (a[k << 1].r + a[k << 1 | 1].l, max (a[k << 1].val, a[k << 1 | 1].val) ); a[k].sum = a[k << 1].sum + a[k << 1 | 1].sum; } inline void update (int l, int r, int k) { if (l == r) { a[k].sum = a[k].l = a[k].r = a[k].val = t2; return; } int mid = l + r >> 1; if (t1 <= mid) update (l, mid, k << 1); else update (mid + 1, r, k << 1 | 1); pushup (l, r, k); } signed main () { n = read (); for (int i = 1; i <= n; i ++) c[i] = read (); m = read (); for (int i = 1; i <= m; i ++) x[i] = read (); for (int i = 1; i <= m; i ++) { t1 = last[x[i] ][1], t2 = 0; if (t1 != 0) update (1, m, 1); t1 = last[x[i] ][0], t2 = -c[x[i] ]; if (t1 != 0) update (1, m, 1); t1 = i, t2 = c[x[i] ]; update (1, m, 1); last[x[i] ][1] = last[x[i] ][0]; last[x[i] ][0] = i; ans = max (ans, a[1].val); } printf ("%lld", ans); return 0; }