因为一个zz错误调了一个早上……汇点写错了……spfa也写错了……好吧好像是两个……

把数轴上的每一个点向它右边的点连一条边，容量为$k$，费用为$0$，然后把每一个区间的左端点向右端点连边，容量为$1$，费用为区间长度，然后求一个最大费用最大流。因为坐标太大，记得离散

然而并不是很明白为什么这样做是对的……想了想，把网络流当成一个水流好了，水从左流到右，那么如果是在一个区间内，不可能满流（因为被区间左端点至右端点那一条边给分去了一部分流），但是被分去的那一部分流会在区间右端点被流回来，所以不想交的区间是没有影响的（因为是开区间，所以右端点和另一区间左端点重合并没有影响）。然后如果区间内还有其他区间的左端点，又会分流，一直这样下去，直到有超过$k$个区间覆盖了同一点，那样流就不够了，不会再分（因为从源点也只有$k$的流），那么只要求出了一个最大流，就是一个满足题目条件的方案。又因为要使长度最大，那么我们要让区间的流带上费用，求一个最大费用流即可

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #define inf 0x3f3f3f3f 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)10 char buf[1<<21],*p1=buf,*p2=buf;11 inline int read(){12     #define num ch-'0'13     char ch;bool flag=0;int res;14     while(!isdigit(ch=getc()))15     (ch=='-')&&(flag=true);16     for(res=num;isdigit(ch=getc());res=res*10+num);17     (flag)&&(res=-res);18     #undef num19     return res;20 }21 const int N=5005,M=500005;22 int ver[M],Next[M],head[N],edge[M],flow[M],tot=1;23 int dis[N],disf[N],Pre[N],last[N],vis[N],n,s,t,k;24 inline void add(int u,int v,int f,int e){25     ver[++tot]=v,Next[tot]=head[u],head[u]=tot,flow[tot]=f,edge[tot]=e;26     ver[++tot]=u,Next[tot]=head[v],head[v]=tot,flow[tot]=0,edge[tot]=-e;27 }28 bool spfa(){29     queue
          
            Q;30 memset(dis,0xef,sizeof(dis));31 Q.push(s),dis[s]=0,vis[s]=1,disf[s]=inf,Pre[t]=-1;32 while(!Q.empty()){33 int u=Q.front();Q.pop();vis[u]=0;34 for(int i=head[u];i;i=Next[i]){35 int v=ver[i];36 if(flow[i]>0&&dis[v]
           
            r) swap(l,r);69 q[i]=node(l,r,r-l);70 st[++m]=l,st[++m]=r;71 }72 sort(st+1,st+1+m);73 m=unique(st+1,st+1+m)-st-1;74 for(int i=1;i<=n;++i){75 q[i].l=lower_bound(st+1,st+1+m,q[i].l)-st;76 q[i].r=lower_bound(st+1,st+1+m,q[i].r)-st;77 }78 s=0,t=m+1;79 for(int i=s;i