相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4906
解题报告
这题我们看一眼就知道可以用平衡树来维护序列
至于收益问题,我们发现区间信息可以合并
只需要记录一个区间左右两个端点的状态即可
于是搞一个$Splay$然后带$4^3$的常数来合并区间信息即可
总时间复杂度:$O(4^3n \log n)$
Code
这个代码win下没问题
ubuntu 16.04下也没有问题
UOJ的自定义测试也不会RE
然而一交到B站上就RE
我也很绝望啊,弃疗了_(:з」∠)_
反正北京省选测评也是在win下,就当a了吧
#include<bits/stdc++.h> #define LL long long using namespace std; const int SGZ = 4; const int N = 400000; namespace Splay{ int tot; struct Node *null, *root; struct Node{ Node *ch[2], *fa; LL len, plen, adv[SGZ], sum[SGZ][SGZ]; inline Node() { } inline Node(LL l, LL a, LL b, LL c) { memset(sum, 0, sizeof(sum)); sum[0][0] = adv[0] = sum[3][3] = adv[3] = l * a; sum[1][1] = adv[1] = l * b; sum[2][2] = adv[2] = l * c; len = plen = l; ch[0] = ch[1] = fa = null; for (int i = 0; i < SGZ; i++) { for (int j = i; j < SGZ; j++) { for (int k = i - 1; ~k; k--) { sum[k][j] = max(sum[k][j], sum[i][j]); } for (int k = j + 1; k < SGZ; k++) { sum[i][k] = max(sum[i][k], sum[i][j]); } } } } inline void relax(LL &a, LL b) { a = b > a? b: a; } inline void maintain() { memset(sum, 0, sizeof(sum)); //merge left son if (ch[0] != null) { for (int i = 0; i < SGZ; i++) { for (int k = SGZ - 1; k >= i; k--) { for (int j = k; j >= i; j--) { relax(sum[i][k], ch[0]->sum[i][j] + adv[k]); } } } plen = len + ch[0]->plen; } else { for (int i = 0; i < SGZ; i++) { sum[i][i] = adv[i]; } plen = len; } //merge right son if (ch[1] != null) { for (int l = 0; l < SGZ; l++) { for (int i = SGZ - 1; i >= l; i--) { for (int r = SGZ - 1; r >= i; r--) { relax(sum[l][r], sum[l][i] + ch[1]->sum[i][r]); } } } plen += ch[1]->plen; } for (int i = 0; i < SGZ; i++) { for (int j = i; j < SGZ; j++) { for (int k = i - 1; ~k; k--) { relax(sum[k][j], sum[i][j]); } for (int k = j + 1; k < SGZ; k++) { relax(sum[i][k], sum[i][j]); } } } } inline void rotate() { int t = fa->ch[1] == this; if (fa->fa != null) { int tt = fa->fa->ch[1] == fa; fa->fa->ch[tt] = this; } fa->ch[t] = ch[t^1]; ch[t^1]->fa = fa; ch[t^1] = fa; fa = ch[t^1]->fa; ch[t^1]->fa = this; ch[t^1]->maintain(); maintain(); } inline void splay(Node *ed) { while (fa != ed) { if (fa->fa != ed) { if ((fa->ch[0] == this) ^ (fa->fa->ch[0] == fa)) { rotate(); rotate(); } else { fa->rotate(); rotate(); } } else { rotate(); } } } inline LL ans() { LL ret = 0; for (int i = 0; i < SGZ; i++) { for (int j = i; j < SGZ; j++) { ret = max(ret, sum[i][j]); } } return ret; } Node *find(LL pp) { if (ch[0]->plen >= pp) { return ch[0]->find(pp); } else if (ch[0]->plen + len >= pp) { return this; } else { return ch[1]->find(pp - ch[0]->plen - len); } } Node *min() { if (ch[0] != null) { return ch[0]->min(); } else { return this; } } }p[N]; inline void insert(LL pp, int a ,int b, int c, LL l) { p[++tot] = Node(l, a, b, c); Node *nw = p + tot; if (root != null) { Node *pos = root->find(pp); pos->splay(null); root = pos; int nlen = root->ch[0]->plen + root->len - pp, LEN = root->len, ls = root->ch[0] - p, rs = root->ch[1] - p; p[++tot] = Node(nlen, LEN? root->adv[0] / LEN: 0, LEN? root->adv[1] / LEN: 0, LEN? root->adv[2] / LEN: 0); *root = Node(LEN - nlen, LEN? root->adv[0] / LEN: 0, LEN? root->adv[1] / LEN: 0, LEN? root->adv[2] / LEN: 0); root->ch[0] = p + ls, root->ch[1] = p + rs; if (root->ch[1] != null) { root->ch[1]->min()->splay(root); p[tot].fa = root->ch[1]; root->ch[1]->ch[0] = p + tot; nw->fa = p + tot; p[tot].ch[0] = nw; p[tot].maintain(); root->ch[1]->maintain(); root->maintain(); } else { p[tot].fa = root; root->ch[1] = p + tot; nw->fa = p + tot; p[tot].ch[0] = nw; p[tot].maintain(); root->maintain(); } } else { root = nw; } } inline LL query() { return root->ans(); } inline void init() { null = root = p; } }; int main() { Splay::init(); int n; scanf("%d", &n); for (LL i = 1, LastAns = 0; i <= n; ++i) { LL pos, len, tmp, a, b, c; cin>>pos>>a>>b>>c>>len; Splay::insert(pos, a, b, c, len); tmp = Splay::query(); printf("%lld\n", tmp - LastAns); LastAns = tmp; } return 0; }