出这题的人是怎么想出来的……

言归正传，这题是二分图套值域线段树。

首先经过 @Vfleaking的神奇建图后，把图拆成二分图，

不妨利用有向图最小割的性质建图（以前我一直以为最小割和边的方向无关，可这样的话很奇怪哦……）

理解悲剧……

我们可以利用边有向的性质解决黑白色块……

然后发现线段树很多……主席树闪亮登场

然后·就这麽A了？…………

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Rep(i,n) for(int i=0;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<
             <<' '<
              
               <<' '<
               
                <
                
                 >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
                 
                  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<
                  
                   <<'*'; 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<
                   
                    <
                    
                     <