BZOJ 3218: a + b Problem【当网络流遇上可持久化线段树】

首先搞二元关系
这个本来的关系是一坨点 是否有一个点选择了白 这个不好弄
可以转换成 是否全部选择了黑

对每个点i新建一个点i’
含义是 点i之前的a值在li~ri范围的点 是不是全部选了黑色
i’选择了全部选黑且范围内某个点选了白的代价是inf
i’选择了不是全部选择了黑且i选择了黑的代价是pi

这样就可以得到correct ans了

但是这个的边数是n^2级的 too大to过
把上面的方程解了可以发现 范围内的点要向i‘连inf的边 这个的边数是n^2的 这个就是瓶颈

怎么办呢=-=
经过黄神的提醒(边数是nlogn级的
突然想到了这题是不是可以用可持久化线段树= =
线段树的权值表示a的权值
线段树的一个节点都代表了网络流的一个节点
一个节点[t, l, r]表示1~t号节点中 a值在l~r的都向这个点直接或间接的连了inf的边
查询就是把线段树中代表1~i-1中的a值在li~ri间的节点向当前的i’连边 可以知道最多log个节点
插入就是 对于一个新的点i 权值为ai 在可持久化线段树中插入到ai位置
对于经过的新建的点t last_t->t连inf的边 i->t连inf的边 last_t是上个线段树t位置的这个节点
每次新建也是log个点 log条边
所以总边数、点数都是nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;
const int inf = 0x3fffffff;
const int inf2 = 1000 * 1000 * 1000;

//===========================NetworkFlow===============

const int NFmaxn = 1000005;
const int NFmaxm = 1000005;
const int NFinf = 0x3fffffff;

struct NF_Line
{
  int to, next, v, opt;
};

struct Network_Flow
{
  NF_Line li[NFmaxm];
  int be[NFmaxn], l, s, t, n, num[NFmaxn], note[NFmaxn];

  void makeline(int fr, int to, int v)
  {
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
    li[l].opt = l + 1;

    ++l;
    li[l].next = be[to];
    be[to] = l;
    li[l].to = fr;
    li[l].v = 0;
    li[l].opt = l - 1;
  }

  void create(int N)
  {
    n = N;
  }

  int sap(int now, int maxf)
  {
    if (now == t) return maxf;
    int mi = n, tot = 0;
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (li[i].v && note[to] + 1 == note[now])
      {
        int k = sap(to, min(maxf - tot, li[i].v));
        li[i].v -= k;
        tot += k;
        li[li[i].opt].v += k;
        if (note[s] >= n || tot == maxf) return tot;
      }
      if (li[i].v) mi = min(mi, note[to]);
    }
    if (!tot)
    {
      if (!--num[note[now]])
      {
        note[s] = n;
        return 0;
      }
      ++num[note[now] = mi + 1];
    }
    return tot;
  }

  int query(int S, int T)
  {
    s = S, t = T;
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
    num[0] = n;
    int ans = 0;
    while (note[s] < n) ans += sap(s, NFinf);
    return ans;
  }

  void clear()
  {
    l = s = t = n = 0;
    memset(be, 0, sizeof(be));
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
  }
}nf;

//===========================NetworkFlow===============

struct node
{
    int l, r;
}t[maxn];

int n, m, root[maxn], tot, tot2, s, T, ans;

void query(int now, int l, int r, int lf, int rt, int p)
{
    if (!now) return;
    if (l >= lf && r <= rt)
    {
        nf.makeline(now, p, inf);
        return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) query(t[now].l, l, mid, lf, rt, p);
    if (rt >= mid + 1) query(t[now].r, mid + 1, r, lf, rt, p);
}

int ins(int no, int l, int r, int lr, int p)
{
    int now = ++tot;
    t[now] = t[no];
    if (no) nf.makeline(no, now, inf);
    nf.makeline(p, now, inf);
    if (l == r) return now;
    int mid = (l + r) / 2;
    if (lr <= mid) t[now].l = ins(t[no].l, l, mid, lr, p);
    else t[now].r = ins(t[no].r, mid + 1, r, lr, p);
    return now;
}

int main()
{
    scanf("%d", &n);
    s = ++tot, T = ++tot;
    for (int i = 1; i <= n; ++i)
    {
        int a, b, w, l, r, p, tp = ++tot, now = ++tot;
        scanf("%d%d%d%d%d%d", &a, &b, &w, &l, &r, &p);
        nf.makeline(tp, now, p);
        nf.makeline(s, now, w);
        nf.makeline(now, T, b);
        ans += w + b;
        query(root[i - 1], 0, inf2, l, r, tp);
        root[i] = ins(root[i - 1], 0, inf2, a, now);
    }
    nf.create(tot);
    printf("%d", ans - nf.query(s, T));
}