zoj4028 LIS，差分约束

题意：给你以i为结尾的最长上升子序列的值，和每个值的区间范围求可行的a【i】

题解：差分约束，首先满足l[i]<=a[i]<=r[i],可以建一个虚拟节点n+1，那么有a[n+1]-a[i]<=-l[i],a[i]-a[n+1]<=r[i],同时对于之前出现过f【i】（假设为j）的情况，此时a[i]>=a[j](保证没法转移),a[j]-a[i]<=0,还有对于从上一个f[i]-1转移过来的点j,有a[i]>a[j]，即a[j]-a[i]<=-1

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

struct edge {

    int to,Next,c;

}e[maxn];

int l[N],r[N],f[N];

int last[N];

ll dis[N];

bool vis[N];

int head[N],cnt,n;

void add(int u,int v,int c)

{

//    printf("%d %d %d\n",u,v,c);

    e[cnt].to=v;

    e[cnt].c=c;

    e[cnt].Next=head[u];

    head[u]=cnt++;

}

void spfa()

{

    memset(vis,,sizeof vis);

    for(int i=;i<=n+;i++)dis[i]=1e18;

    queue<int>q;

    q.push(n+);

    vis[n+]=;dis[n+]=;

    while(!q.empty())

    {

//        printf("%d\n",q.front());

        int u=q.front();

        q.pop();

        vis[u]=;

        for(int i=head[u];~i;i=e[i].Next)

        {

            int To=e[i].to;

            if(dis[To]>dis[u]+e[i].c)

            {

                dis[To]=dis[u]+e[i].c;

                if(!vis[To])

                {

                    vis[To]=;

                    q.push(To);

                }

            }

        }

    }

    bool ok=;

    for(int i=;i<=n;i++)

    {

        if(ok)printf("%d",dis[i]);

        else printf(" %d",dis[i]);

        ok=;

    }

    puts("");

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        memset(last,,sizeof last);

        cnt=;

        memset(head,-,sizeof head);

        scanf("%d",&n);

        for(int i=;i<=n;i++)scanf("%d",&f[i]);

        for(int i=;i<=n;i++)scanf("%d%d",&l[i],&r[i]);

        for(int i=;i<=n;i++)

        {

            add(i,n+,-l[i]);

            add(n+,i,r[i]);

            if(last[f[i]])add(last[f[i]],i,);

            if(f[i]>)add(i,last[f[i]-],-);

            last[f[i]]=i;

        }

        spfa();

    }

    return ;

}

/***********************

***********************/