Educational Codeforces Round 69 (Rated for Div. 2) E. Culture Code dp(线段树转移） or 最短路计数

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],num,minn;
#define  ll long long
ll ans;
const ll mod=1e9+7;
struct node{ll minn,num;}t[N<<2];

node merge(node a,node b)
{
    if(a.minn==b.minn)return (node){a.minn,(a.num+b.num)%mod };
    if(a.minn<b.minn) return (node){a.minn,a.num};
    if(a.minn>b.minn) return (node){b.minn,b.num};
}
void upnode(int x,int v,int num,int l,int r,int pos)
{
    if(l==r){t[pos]=(node){v,num};return;}
    int m=(l+r)>>1;
    if(x<=m)upnode(x,v,num,l,m,pos<<1);
    else upnode(x,v,num,m+1,r,pos<<1|1);
    t[pos]=merge(t[pos<<1],t[pos<<1|1]);
}
node qmin(int L,int R,int l,int r,int pos)
{
    if(L<=l&&r<=R)return t[pos];
    int m=l+r>>1;node ans=(node){1000000000,0};
    if(L<=m)ans=merge(ans,qmin(L,R,l,m,pos<<1));
    if(R>m)ans=merge(ans,qmin(L,R,m+1,r,pos<<1|1));
    return ans;
}
struct NODE{int in,out;}s[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d%d",&s[i].out,&s[i].in);
    sort(s+1,s+1+n,[](NODE a,NODE b){return a.in<b.in;});

    for(int i=n;i>=1;i--)
    {
        int L=1,R=n,ans=-1;
        while(L<=R)
        {
            int mid=(L+R)>>1;
            if(s[mid].in>=s[i].out)ans=mid,R=mid-1;
            else L=mid+1;
        }
        if(ans==-1)upnode(i,s[i].in,1,1,n,1);
        else 
        {
            node u=qmin(ans,n,1,n,1);
            upnode(i,u.minn-(s[i].out-s[i].in),u.num,1,n,1);
        }
    }
    cout<<t[1].num;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
struct node{int in,out;}s[N];
int n,ans,dis[N],cnt[N],vis[N],pos,head[N],minn=1e9;
struct Edge{int to,nex,v;}edge[N<<1];
void add(int a,int b,int c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;};

int main()
{   
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d%d",&s[i].out,&s[i].in);
    sort(s+1,s+1+n,[](node a,node b){return a.in<b.in;});
    for(int i=0;i<n;i++)add(i,i+1,s[i+1].in-s[i].in);
    for(int i=1;i<=n;i++)
    {
        int temp=-1,L=1,R=n;
        while(L<=R)
        {
            int mid=L+R>>1;
            if(s[mid].in>=s[i].out)temp=mid,R=mid-1;else L=mid+1;
        }
        if(temp==-1)continue;
        else add(i,temp,s[temp].in-s[i].out);
    }
    memset(dis,0x3f,sizeof dis);
    dis[0]=0;cnt[0]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=head[i];j;j=edge[j].nex)
        {
            int v=edge[j].to;
            if(dis[i]+edge[j].v<dis[v])dis[v]=dis[i]+edge[j].v,cnt[v]=cnt[i];
            else if(dis[i]+edge[j].v==dis[v])cnt[v]+=cnt[i],cnt[v]%=mod;
        }
    }
    for(int i=1;i<=n;i++{if(s[i].out>s[n].in&&dis[i]<minn)minn=dis[i];}
    for(int i=1;i<=n;i++)
    if(s[i].out>s[n].in&&dis[i]==minn)ans=(ans+cnt[i])%mod;
    cout<<ans;
    return 0;
}