出這題的人是怎么想出來的……

言歸正傳，這題是二分圖套值域線段樹。

首先經過 @Vfleaking的神奇建圖后，把圖拆成二分圖，

不妨利用有向圖最小割的性質建圖（以前我一直以為最小割和邊的方向無關，可這樣的話很奇怪哦……）

理解悲劇……

我們可以利用邊有向的性質解決黑白色塊……

然后發現線段樹很多……主席樹閃亮登場

然后·就這麼A了？…………

?

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<functional> #include<cmath> #include<cctype> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define ForD(i,n) for(int i=n;i;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define RepD(i,n) for(int i=n;i>=0;i--) #define MEM(a) memset(a,0,sizeof(a)) #define MEMI(a) memset(a,127,sizeof(a)) #define MEMi(a) memset(a,128,sizeof(a)) #define INF (2139062143) #define MAXN (500000 +10) #define MAXM (500000 +10) int n,m,s,t; int edge[MAXM],next[MAXM]={0},pre[MAXN]={0},weight[MAXM],size=1; void addedge(int u,int v,int w) {edge[++size]=v;weight[size]=w;next[size]=pre[u];pre[u]=size; } void addedge2(int u,int v,int w){/*cout<<u<<' '<<v<<' '<<w<<endl;*/addedge(u,v,w),addedge(v,u,0);} int cnt[MAXN]={0},d[MAXN]={0}; long long totflow=0; long long sap(int x,int flow) {if (x==t) return flow;int nowflow=0;Forp(x){int &v=edge[p];if (d[v]==d[x]-1&&weight[p]){long long fl=sap(v,min(weight[p],flow));weight[p]-=fl,weight[p^1]+=fl,nowflow+=fl,flow-=fl;if (!flow) return nowflow;}} if (!(--cnt[d[x]++])) d[s]=t+1;cnt[d[x]]++;return nowflow; } struct node {node *ch[2];node(){ch[0]=ch[1]=NULL;} }q[MAXN],*root[MAXN]={NULL}; int tail=0; void ins(node *&p,node *x,int l,int r,int c) {int m=(l+r) >>1;p=&q[++tail];if (x) *p=*x;if (l==r) return;if (c<=m) ins(p->ch[0],p->ch[0],l,m,c);else ins(p->ch[1],p->ch[1],m+1,r,c); } void print(node *p) {//cout<< } node *ans[MAXN]; int ans_siz=0; void qur(node *p,int l,int r,int L,int R) {if (!p||L>R) return;int m=l+r >>1;if (L<=l&&r<=R) {ans[++ans_siz]=p;return;}if (l==r) return;if (L<=m) qur(p->ch[0],l,m,L,R);if (m<R) qur(p->ch[1],m+1,r,L,R); } int a2[MAXN],a[MAXN],b[MAXN],w[MAXN],l[MAXN],r[MAXN],p[MAXN]; int main() {freopen("bzoj3218.in","r",stdin); // freopen(".out","w",stdout);scanf("%d",&n);For(i,n) scanf("%d%d%d%d%d%d",&a[i],&b[i],&w[i],&l[i],&r[i],&p[i]);memcpy(a2,a,sizeof(a));sort(a2+1,a2+n+1);int size=unique(a2+1,a2+n+1)-(a2+1);For(i,n) {a[i]=lower_bound(a2+1,a2+size+1,a[i])-(a2);l[i]=lower_bound(a2+1,a2+size+1,l[i])-(a2);r[i]=upper_bound(a2+1,a2+size+1,r[i])-(a2)-1;}For(i,n) ins(root[i],root[i-1],1,size,a[i]);s=2*n+1; t=2*n+2;For(i,n) addedge2(s,i,b[i]),addedge2(i,t,w[i]),addedge2(i,n+i,p[i]);For(i,tail){if (q[i].ch[0]) addedge2(t+i,t+((q[i].ch[0])-q),INF);if (q[i].ch[1]) addedge2(t+i,t+((q[i].ch[1])-q),INF);}For(i,n){ans_siz=0;qur(root[i],1,size,a[i],a[i]);qur(root[i-1],1,size,a[i],a[i]);node *cur=ans[1],*last=NULL;if (ans_siz>1) last=ans[2];//cout<<t+((cur)-(q))<<'*';addedge2(t+((cur)-(q)),i,INF);if (ans_siz>1) addedge2(t+(cur-(q)),t+((last)-(q)),INF);}For(i,n){ans_siz=0;qur(root[i],1,size,l[i],r[i]);For(j,ans_siz) addedge2(n+i,t+((ans[j])-(q)),INF);} //cout<<2*n+2+tail<<endl; cnt[0]=2*n+2+tail;while (d[s]<=t) {totflow+=sap(s,INF);} //For(i,2*n+tail) cout<<d[i]<<' ';long long ans=-totflow;For(i,n) ans+=b[i]+w[i];cout/*<<totflow<<' '*/<<ans<<endl; return 0; }

?

?

轉載于:https://www.cnblogs.com/snake-hand/p/3144807.html

總結

以上是生活随笔為你收集整理的BZOJ 3218(a + b Problem-二分图套值域线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。