题解：P10538 [APIO2024] 星际列车
考虑把边变成点，点变成边，那么会连出一个 DAG。此时 DAG 的转移也可以看成：在时间轴上依次考虑每条边（或是 DAG 上的点），碰到左端点就计算这条边的 dp 值，碰到右端点就将这条边标记为可转移的。这样边数是
发现边数多的就是原图中一个点的度数很大。考虑对度数根号分治。若一个 DAG 上的点入度
那么总复杂度为
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 1e5;
const int inf = 1e9;
const ll INF = 1e15;
int read() {
int s = 0,f = 1;char ch = getchar();
while (!isdigit(ch)) f = ch == '-'? -1 : 1, ch = getchar();
while(isdigit(ch)) s = s * 10 + ch - '0', ch = getchar();
return s * f;
}
const int mod = 998244353;
int qpow(int a,int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % mod;
b >>= 1, a = 1ll * a * a % mod;
}
return res;
}
int getmod(int x) {
return x - (x >= mod) * mod;
}
int n,m,w;
ll val[N + 10];
const int bl = 2200;
int b2;
struct node {
int v,w,l,r,i;
};
vector<node> vc1[N + 10],vc2[N + 10];
void add1(int u,int v,int w,int l,int r,int i) {
vc1[u].push_back({v,w,l,r,i});
}
void add2(int u,int v,int w,int l,int r,int i) {
vc2[u].push_back({v,w,l,r,i});
}
int tot,h[N * 4 + 10];
struct block {//支持单点加，前缀查询
int st[N * 4 + 10],ed[N * 4 + 10],bl[N * 4 + 10];
void build() {
int ct = 0;
for (int i = 1;i <= tot;i += b2) {
st[++ct] = i, ed[ct] = min(tot,i + b2 - 1);
for (int j = st[ct];j <= ed[ct];j ++ ) bl[j] = ct;
}
}
int s1[N * 4 + 10],s2[N * 4 + 10];
inline void modify(int x,int s) {
for (int i = bl[x];i <= bl[tot];i ++ ) s1[i] += s;
for (int i = x;i <= ed[bl[x]];i ++ ) s2[i] += s;
}
inline int query(int x) {
return !x ? 0 : s1[bl[x] - 1] + s2[x];
}
}t;
ll ww[N + 10];
int du[N + 10],to2[N + 10],tt,to1[N + 10];
struct Seg2 {
struct node {
ll v,tag;
}t[N * 16 + 10];
inline void pushup(int x) {
t[x].v = min(t[x<<1].v,t[x<<1|1].v);
}
inline void f(int x,ll s) {
t[x].v += s, t[x].tag += s;
}
inline void pushdown(int x) {
f(x<<1,t[x].tag), f(x<<1|1,t[x].tag);
t[x].tag = 0;
}
void modify1(int x,int k,int L,int R,ll s) {
if (L == R) {
t[x].v = min(t[x].v,s);
return ;
}
int mid = L + R >> 1;
if (t[x].tag) pushdown(x);
if (mid >= k) modify1(x<<1,k,L,mid,s);
else modify1(x<<1|1,k,mid + 1,R,s);
pushup(x);
}
void modify(int x,int l,int r,int L,int R,ll s) {
if (l > r) return;
if (L >= l && r >= R) {
f(x,s);
return;
}
int mid = L + R >> 1;
if (t[x].tag) pushdown(x);
if (mid >= l) modify(x<<1,l,r,L,mid,s);
if (mid < r) modify(x<<1|1,l,r,mid + 1,R,s);
pushup(x);
}
ll query(int x,int l,int r,int L,int R) {
if (l > r) return INF;
if (L >= l && r >= R) return t[x].v;
int mid = L + R >> 1;
pushdown(x);
ll res = INF;
if (mid >= l) res = query(x<<1,l,r,L,mid);
if (mid < r) res = min(res,query(x<<1|1,l,r,mid + 1,R));
return res;
}
};
vector<Seg2> t2;
vector<int> res;
int id[N + 10],tl[N + 10],tr[N + 10],bh[N + 10],lst[N + 10];
vector<int> vc[N * 4 + 10];
ll dis[N + 10];
vector<int> vc3[N * 4 + 10];
vector<int> vc4[N * 4 + 10];
struct edge {
int v,w,nxt;
}ed[40000000];
int head[N + 10],cnt;
inline void add(int u,int v,int w) {
ed[++cnt] = {v,w,head[u]};
head[u] = cnt;
}
vector<pair<int,int> > vc5[N * 4 + 10];
long long solve(int N,int M,int W,vector<int> T,vector<int> X,vector<int> Y,vector<int> A,vector<int> B,vector<int> C,vector<int> L,vector<int> R) {
n = N, m = M, w = W;
tot = 0;
for (int i = 0;i < n;i ++ ) val[i + 1] = T[i];
for (int i = 0;i < w;i ++ ) h[++tot] = L[i], h[++tot] = R[i];
for (int i = 0;i < m;i ++ ) h[++tot] = A[i], h[++tot] = B[i];
sort(h + 1,h + tot + 1), tot = unique(h + 1,h + tot + 1) - h - 1;
for (int i = 0;i < w;i ++ ) {
L[i] = lower_bound(h + 1,h + tot + 1,L[i]) - h;
R[i] = lower_bound(h + 1,h + tot + 1,R[i]) - h;
vc[R[i]].push_back(L[i]);
}
b2 = sqrt(tot);
for (int i = 1;i <= m;i ++ ) {
int u = X[i - 1] + 1,v = Y[i - 1] + 1,c = C[i - 1],l = A[i - 1],r = B[i - 1];
l = lower_bound(h + 1,h + tot + 1,l) - h;
r = lower_bound(h + 1,h + tot + 1,r) - h;
tl[i] = l, tr[i] = r;
add1(u,v,c,l,r,i);
add2(v,u,c,l,r,i);
ww[i] = c;
vc3[l].push_back(i);
vc4[r].push_back(i);
}
int qt = 0;
//vc1:i 的出边 vc2: 入边
for (int i = 1;i <= n;i ++ ) {
for (auto v : vc2[i]) to1[v.i] = i;
for (auto v : vc1[i]) to2[v.i] = i;
if (vc2[i].size() > bl) {
bh[i] = ++tt;
continue;
}
}
t.build();
t2.resize(tt + 1);
for (int i = 1;i <= tt;i ++ )
t2[i].modify(1,1,tot,1,tot,INF);
for (int i = 1;i <= m;i ++ ) id[i] = i;
sort(id + 1,id + m + 1,[](int x,int y){return tl[x] == tl[y] ? tr[x] < tr[y] : tl[x] < tl[y];});
int ct = 0;
for (int i = 1;i <= m;i ++ ) dis[i] = INF;
for (int i = 1;i <= tot;i ++ ) {
for (auto u : vc4[i]) {
if (bh[to1[u]]) {
t2[bh[to1[u]]].modify1(1,tr[u],1,tot,dis[u]);
}
}
for (auto u : vc3[i]) {
if (bh[to2[u]]) {
int x = bh[to2[u]];
for (;lst[x] < i;lst[x] ++ )
for (auto v : vc[lst[x]]) t2[x].modify(1,1,v - 1,1,tot,val[to2[u]]);
dis[u] = min(dis[u],ww[u] + t2[x].t[1].v);
}
else {
if (to2[u] == 1) {
dis[u] = ww[u] + 1ll * val[1] * ct;
continue;
}
for (auto v : vc2[to2[u]]) if (v.r <= i) dis[u] = min(dis[u],dis[v.i] + ww[u] + 1ll * val[to2[u]] * (ct - t.query(v.r)));
}
}
for (auto v : vc[i]) t.modify(v,1), ct ++;
}
ll res = INF;
for (auto v : vc2[n]) {
res = min(res,dis[v.i] + 1ll * val[n] * (w - t.query(v.r)));
}
return res == INF ? -1 : res;
}
int main() {
int n = read(),m = read(),w = read();
vector<int> T;
vector<int> X;
vector<int> Y;
vector<int> A;
vector<int> B;
vector<int> C;
vector<int> L;
vector<int> R;
for (int i = 1;i <= n;i ++ ) T.push_back(read());
for (int i = 1;i <= m;i ++ ) X.push_back(read()), Y.push_back(read()), A.push_back(read()), B.push_back(read()), C.push_back(read());
for (int i = 1;i <= w;i ++ ) L.push_back(read()), R.push_back(read());
cout << solve(n,m,w,T,X,Y,A,B,C,L,R);
return 0;
}用了大约