相关链接
题目传送门:http://uoj.ac/problem/77
神犇题解:http://www.cnblogs.com/geng4512/p/5296863.html
解题报告
我们发现如果忽略\(1<j<i\)这个限制,再假设\({l_i} = {r_i}\)
这样的话,直接上最小割就好
现在考虑\({l_i} < {r_i}\)
这样的话,用线段树优化建图就可以啦!
再考虑\(1<j<i\)这个限制
这样的话,用函数式线段树就可以啦!
感觉是VFK强行套数据结构啊!
另外还有BZOJ 3218可以双倍经验!
话说BZOJ上那些\(200ms+\)的神犇都是用的什么算法啊?
怎么这么快啊!
Code
#include<bits/stdc++.h> using namespace std; const int N = 200000+9; const int M = 2000000; const int INF = 1000000000; int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M]; int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[N]; inline int read() { 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()) { memcpy(cur, head, sizeof(head)); 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(); for (int i=head[w];i;i=nxt[i]) { 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]; Add_Edge(p, w); } if (f) Add_Edge(w, f); 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); } else Add_Edge(sur, 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++) { _hash[++tot] = A[i] = read(); B[i] = read(); W[i] = read(); _hash[++tot] = LL[i] = read(); _hash[++tot] = RR[i] = read(); P[i] = read(); } 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]); Add_Edge(i, T, B[i], 1); Add_Edge(S, i, W[i], 1); PST::modify(i-1, i+n, LL[i], RR[i]); Add_Edge(i+n, i, P[i]); } printf("%d\n",vout-Dinic.MaxFlow()); return 0; }