人傻了,咋编译一直不过啊
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5;
const double eps = 1e-9;
int rt[maxn];
struct node {
int l, r, sum;
};
struct Segtree {
node tr[maxn * 30];
int tot = 0;
void pushup(int t) {
tr[t].sum = tr[tr[t].l].sum + tr[tr[t].r].sum;
}
int modify(int l, int r, int pos, int q, int val) {
int p = ++tot;
tr[p] = tr[q], tr[p].sum += val;
// cout << l << " " << r << " " << p << endl;
if(l == r)
return p;
int mid = l + r >> 1;
if(pos <= mid)
tr[p].l = modify(l, mid, pos, tr[q].l, val);
else
tr[p].r = modify(mid + 1, r, pos, tr[q].r, val);
pushup(p);
return p;
}
int query(int l, int r, int pos, int p) {
if(pos > r)
return 0;
if(!p)
return 0;
if(l == r)
return tr[p].sum;
int mid = l + r >> 1;
if(pos <= mid)
return query(l, mid, pos, tr[p].l) + tr[tr[p].r].sum;
return query(mid + 1, r, pos, tr[p].r);
}
} tree;
int n, m, w, Tt[maxn], x[maxn], y[maxn], a[maxn], b[maxn], c[maxn];
vector<int> v[maxn];
int l[maxn], r[maxn];
int tim[maxn], tot, dp[maxn];
int qpos(int x) {
return lower_bound(tim + 1, tim + tot + 1, x) - tim;
}
struct Seg {
int p, ed, l, r;
};
vector<int> bg[maxn], ed[maxn];
vector<Seg> q[maxn];
int f[maxn], t[maxn];
int cal(int l, int r) {
if(l > r)
return 0;
return tree.query(1, tot, l + 1, rt[r - 1]);
}
int calc(int id, int x, int l, int r) {
return dp[id] + Tt[x] * cal(l, r);
}
void add(int p, int ed, int i) {
while(f[p] < t[p]) {
Seg tmp = q[p][t[p] - 1];
if(calc(tmp.p, p, tmp.ed, tmp.l) >= calc(i, p, ed, tmp.l))
t[p]--, q[p].pop_back();
else if(calc(tmp.p, p, tmp.ed, tmp.r) < calc(i, p, ed, tmp.r)) {
if(tmp.r != tot)
q[p].push_back(Seg{i, ed, tmp.r + 1, tot});
break;
}
else {
int l = tmp.l - 1, r = tmp.r;
while(l + 1 < r) {
int mid = l + r >> 1;
if(calc(tmp.p, p, tmp.ed, mid) < calc(i, p, ed, mid))
l = mid;
else
r = mid;
}
q[p][t[p] - 1].r = l;
t[p]++, q[p].push_back(Seg{i, ed, r, tot});
}
}
if(f[p] == t[p]) {
t[p]++;
q[p].push_back(Seg{i, ed, 1, tot});
}
}
long long solve(int N, int M, int W, std::vector<int> T,
std::vector<int> X, std::vector<int> Y,
std::vector<int> A, std::vector<int> B, std::vector<int> C,
std::vector<int> L, std::vector<int> R){
n = N, m = M, w = W;
for (int i = 1; i <= n; i++)
Tt[i] = T[i - 1];
for (int i = 1; i <= m; i++)
x[i] = X[i - 1], y[i] = Y[i - 1], a[i] = A[i - 1], b[i] = B[i - 1], c[i] = C[i - 1], tim[++tot] = a[i], tim[++tot] = b[i], x[i]++, y[i]++;
x[0] = 1, y[0] = 1, a[0] = 0, b[0] = 0;
for (int i = 1; i <= w; i++)
l[i] = L[i - 1], r[i] = R[i - 1], tim[++tot] = l[i], tim[++tot] = r[i];
sort(tim + 1, tim + tot + 1);
tot = unique(tim + 1, tim + tot + 1) - tim - 1;
for (int i = 1; i <= m; i++)
a[i] = qpos(a[i]), b[i] = qpos(b[i]);
for (int i = 1; i <= w; i++)
l[i] = qpos(l[i]), r[i] = qpos(r[i]);
for (int i = 1; i <= w; i++)
v[r[i]].push_back(l[i]);
for (int i = 1; i <= tot; i++) {
rt[i] = rt[i - 1];
for (int j = 0; j < v[i].size(); j++)
rt[i] = tree.modify(1, tot, v[i][j], rt[i], 1);
}
for (int i = 0; i <= m; i++)
bg[a[i]].push_back(i);
q[1].push_back(Seg{0, x[0], 1, tot});
t[1]++;
int ans = 9e18;
for (int i = 0; i <= tot; i++) {
// cout << i << endl;
int nw = ed[i].size();
for (int j = 0; j < ed[i].size(); j++) {
int p = ed[i][j];
add(y[p], b[p], p);
}
for (int j = 0; j < bg[i].size(); j++) {
int p = bg[i][j];
while(f[x[p]] < t[x[p]] && q[x[p]][f[x[p]]].r < i)
f[x[p]]++;
if(f[x[p]] == t[x[p]])
continue;
Seg k = q[x[p]][f[x[p]]];
dp[p] = calc(k.p, x[p], k.ed, a[p]) + c[p];
ed[b[p]].push_back(p);
// cout << p << " " << dp[p] << " " << tim[k.ed] << " " << cal(k.ed, a[p]) << endl;
if(y[p] == n)
ans = min(ans, calc(p, n, b[p], tot + 1));
}
for (int j = nw; j < ed[i].size(); j++) {
int p = ed[i][j];
add(y[p], b[p], p);
}
}
// cout << cal(qpos(15), qpos(20)) << endl;
return (ans == 9e18 ? -1 : ans);
}