相关链接
题目传送门：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;
}
