题意：\(n \le 5000\)个区间\(l,r\le 5000\)，每个区间可以选一个点得到val[i]的价值，每个点最多选1次，求最大价值

---

有个显然的\(n^2\)条边的费用流建图(二分图最大权匹配)，每个区间一个点连(1,val[i])的边，区间向区间内每个点连边，每个点向t连容量为1的边

提前知道这是线段树优化建图，所以想了一个做法：线段树每个节点拆点限制流量，每个节点都向t连边

其实不用这么麻烦，直接线段树父节点向子节点连INF边，子节点处限制流量就可以了

这种做法利用了线段树"一个区间分成log段，并且途径最多log个点"的特点。倍增不能实现这样，因为倍增没有父子关系我没想出如何限制流量

PS:跑得好慢啊40s卡时过，毕竟nlogn个点的费用流...

咦？这个二分图最大权匹配很特殊啊貌似可以贪心乱搞100ms就过去啊，具体见下一篇

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define fir first#define sec second#define lc x<<1#define rc x<<1|1#define mid ((l+r)>>1)#define lson lc, l, mid#define rson rc, mid+1, rtypedef long long ll;const int N=3e4+5, M=4e5+5, INF=1e9;inline ll read(){    char c=getchar();ll x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n, s, t, tot, l, r;struct meow{int l, r, val;}a[N];struct edge{int v, c, f, w, ne;}e[M];int cnt=1, h[N];inline void ins(int u, int v, int c, int w) {    e[++cnt]=(edge){v, c, 0, w, h[u]}; h[u]=cnt;    e[++cnt]=(edge){u, 0, 0, -w, h[v]}; h[v]=cnt;}void build(int x, int l, int r) { //printf("build %d %d %d\n",x,l,r);    if(l==r) ins(x, t, 1, 0), tot=max(tot, x);    else {        ins(x, lc, INF, 0); build(lson);        ins(x, rc, INF, 0); build(rson);    }}void segIns(int x, int l, int r, int ql, int qr, int u) { //printf("segIns %d %d %d\n",x,l,r);    if(ql<=l && r<=qr) ins(u, x, 1, 0);    else {        if(ql<=mid) segIns(lson, ql, qr, u);        if(mid
        
          pre[N];inline void lop(int &x) {if(x==N) x=1;}bool spfa(int s, int t) {    memset(inq, 0, sizeof(inq));    memset(d, 0, sizeof(d));    head=tail=1;    q[tail++]=s; d[s]=0; inq[s]=1;    pre[t].fir = -1;    while(head!=tail) {        int u=q[head++]; inq[u]=0; lop(head);        for(int i=h[u];i;i=e[i].ne) {            int v=e[i].v;            if(e[i].c > e[i].f && d[v]