# 某岛

… : "…アッカリ～ン . .. . " .. .
March 18, 2020

## BZOJ 3218. a + b Problem

```const int N = int(1e5) + 9;
int a[N], l[N], r[N]; VI I;
int n, z;

struct Dinitz {
const static int M = N*20;
int D[N], hd[N], suc[M], to[M], cap[M];
int n, m, s, t;
inline void ae(int x, int y, int c){
suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,
suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = 0;
}
#define v to[i]
#define c cap[i]
#define f cap[i^1]
bool bfs(){
static int Q[N]; int cz = 0, op = 1;
fill(D, D+n, 0); D[Q[0] = s] = 1; while (cz < op){
int u = Q[cz++]; REP_G(i, u) if (!D[v]&&c){
D[Q[op++]=v] = D[u]+1;
if (v==t) return 1;
}
}
return 0;
}

LL run(){
LL z=0; while (bfs()){
static int cur[N], pre[N];
int u=s;pre[s]=-1;cur[s]=hd[s];while (~u){
#define i cur[u]
if (u==t){
int d=INF;for(u=s;u!=t;u=v)checkMin(d,c);
z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s;
}
#undef i
int i;for(i=cur[u];i;i=suc[i])if(D[u]+1==D[v]&&c){cur[u]=i,cur[v]=hd[v],pre[v]=u,u=v;break;}
if (!i)D[u]=0,u=pre[u];
}
}
return z;
}
#undef f
#undef c
#undef v
void init() {
RD(n); m=2,s=2*n+1,t=2*n+2;
REP_1(i, n) {
I.PB(RD(a[i])); int b, w; RD(b, w); z += b+w;
I.PB(RD(l[i])); I.PB(RD(r[i]));
ae(s,i,b); ae(i,t,w); ae(i,n+i,RD());
}
UNQ(I); REP_1(i, n) {
a[i]=LBD(I,a[i])+1;
l[i]=LBD(I,l[i])+1;
r[i]=LBD(I,r[i])+1;
}
::n = n; n = t+1;
}
} G;

struct Presitent_Segment_Tree {
const static int N = ::N * 10;
#define lx l[x]
#define rx r[x]
#define ml (ll + rr >> 1)
#define mr (ml + 1)
int l[N], r[N], nn;
int n, s, t, a, b;

void add_edge(int x, int y) {
G.ae(G.t+x, G.t+y, INF);
}

inline int new_node(int y) {
int x = ++nn; G.n += 1;
if (y) {
lx = l[y]; rx = r[y];
}
return x;
}
int add(int y, int p, int t) {
int x = new_node(y), root = x, ll = 1, rr = n;
while (ll < rr) {
if (p < mr) {
x = lx; rr = ml;
} else {
x = rx; ll = mr;
}
}
return root;
}
void gao(int x,int ll,int rr) {
if (!x || b < ll || rr < a) return;
if (a <= ll && rr <= b) {
return;
}
gao(lx,ll,ml);
gao(rx,mr,rr);
}
void gao(int x, int a, int b, int s) {
this->a = a; this->b = b; this->s = s;
gao(x, 1, n);
}
} T; int root[N];

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

G.init(); T.n = SZ(I); REP_1(i, n) {
T.gao(root[i-1],l[i],r[i],n+i-G.t);