## 【UOJ 77】A+B Problem

### Code

#include<bits/stdc++.h>
using namespace std;

const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;

int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[N];

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
static int E = 1; vout += f * t;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;

namespace Persistent_Segment_Tree{
#define PST Persistent_Segment_Tree
int ch[N][2],root[N],cnt,pur,sur,L,R;

void insert(int p, int &w, int l, int r, int f = 0) {
if (w = ++cnt, p) {
ch[w][0] = ch[p][0];
ch[w][1] = ch[p][1];
}
if (l < r) {
int mid = l + r + 1 >> 1;
if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
else insert(ch[p][1], ch[w][1], mid, r, w);
}

inline void insert(int p, int v) {
pur = v; sur = p;
insert(root[p-1], root[p], 1, tot);
}

void modify(int w, int l, int r) {
if (!w) return;
else if (L <= l && r <= R) Add_Edge(w, pur);
else {
int mid = l + r + 1 >> 1;
if (L < mid) modify(ch[w][0], l, mid-1);
if (mid <= R) modify(ch[w][1], mid, r);
}
}

inline void modify(int p, int node, int l, int r) {
pur = node; L = l; R = r;
modify(root[p], 1, tot);
}
};

int main() {
n = read(); PST::cnt = n << 1;
S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
}
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=n;i++) {
A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
}
for (int i=1,l,r;i<=n;i++) {
PST::insert(i, A[i]);
PST::modify(i-1, i+n, LL[i], RR[i]);
}
printf("%d\n",vout-Dinic.MaxFlow());
return 0;
}


## 【BZOJ 4383】[POI2015] Pustynia

#### 代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000000;
const int M = 5000000;
const int INF = 1000000000;

int sol[N],vis[N],in[N],n,m,s,bas,tot;
queue<pair<int,int> > leaf;

inline void Add_Edge(int u, int v, int w) {
static int T = 0; in[v]++;
to[++T] = v; nxt[T] = head[u];
head[u] = T; cost[T] = w;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void build(int w, int l, int r) {
bas = max(bas, w);
if (l < r) {
int mid = l + r + 1 >> 1;
Add_Edge(w, w<<1, 0); build(w<<1, l, mid - 1);
Add_Edge(w, w*2+1, 0); build(w*2+1, mid, r);
} else {
leaf.push(make_pair(w,l));
}
}

bool Get_Ans(int w) {
sol[w] = true;
if (vis[to[i]] && val[w] - cost[i] < val[to[i]]) {
return false;
} else {
val[to[i]] = min(val[to[i]], val[w] - cost[i]);
if (--in[to[i]] == 0) {
if (!Get_Ans(to[i])) {
return false;
};
}
}
}
return true;
}

inline bool solve() {
for (int i=1;i<=tot;i++) {
if (!sol[i] && !in[i]) {
if (!Get_Ans(i)) {
return false;
}
}
}
return true;
}

void insert(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
} else {
int mid = l + r + 1 >> 1;
if (L < mid) insert(w<<1, l, mid-1, L, R);
if (R >= mid) insert(w*2+1, mid, r, L, R);
}
}

int main(){
build(1,1,n);
while (!leaf.empty()) {
leaf.pop();
}
tot = bas + n;
fill(val, val+N, INF);
for (int i=1,p;i<=s;i++) {
vis[p+bas] = 1;
}

for (int i=1,l,r,k,last;i<=m;i++) {
for (int j=1,tmp;j<=k;j++) {
}
arr[0] = l-1; arr[k+1] = r+1;
for (int j=1;j<=k+1;j++) {
if (arr[j] - arr[j-1] > 1) {
insert(1,1,n,arr[j-1]+1,arr[j]-1);
}
}
}
if (!solve()) {
puts("NIE");
} else {
for (int i=bas;i<=tot;i++) {
if (in[i] || val[i] < 1) {
puts("NIE");
exit(0);
}
}

puts("TAK");
for (int i=1;i<=n;i++)
printf("%d ",val[i+bas]);
}
return 0;
}