题意：

有一个长度为n的隐藏的数列a，再给出一个数列f，f[i]是到i（包括自己）的最长递增数列的长度，给出每个数的范围，求出这个隐藏的数列a。

思路：

差分约束。

当$f_i=f_j+1(j<i)$时，有$a_i>a_j$，即$a_j-a_i<=-1$，所以有i->j的权值为-1的边。

当$f_i=f_j(j<i)$时，有$a_i<=a_j$，即$a_i-a_j<=0$，所以有j->i的权值为0的边。

那么范围如何处理呢？

假定有一个超级源点，对于每个范围[l,r]，

有$a_i-a_0>=l$，即$a_0-a_i<=-l$，所以有i->0的权值为-l的边，

有$a_i-a_0<=r$，所以有0->i的权值为r的边。

之后跑一下SPFA即可。

这里注意要用long long。

代码：

#define INF 0x3f3f3f3f3f3f3f3f
int pre[500010];
struct edge
{
    int to;
    int cost;
};
vector<edge>v[500010];
ll dis[500010];
bool vis[500010];
int cnt[500010];
int n,tp;
bool spfa()
{
    fill(dis,dis+1+n,INF);
    fill(vis,vis+1+n,false);
    fill(cnt,cnt+1+n,0);
    queue<int>q;q.push(0);
    vis[0]=true;dis[0]=0;cnt[0]++;
    while(!q.empty())
    {
        tp=q.front();vis[tp]=false;
        q.pop();
        for(int i=0;i<v[tp].size();i++)
        {
            edge &e=v[tp][i];
            if(dis[tp]+e.cost<dis[e.to])
            {
                dis[e.to]=dis[tp]+e.cost;
                if(!vis[e.to])
                {
                    q.push(e.to);
                    vis[e.to]=true;
                    cnt[e.to]++;
                    if(cnt[e.to]>n)return true;   //判断负环
                }
            }
        }
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int x,l,r;
        scanf("%d",&n);
        for(int i=0;i<=n;i++)
        {
            pre[i]=0;
            v[i].clear();
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(pre[x-1]!=0)
            {
                edge temp;
                temp.to=pre[x-1];temp.cost=-1;
                v[i].push_back(temp);
            }
            if(pre[x]!=0)
            {
                edge temp;
                temp.to=i;temp.cost=0;
                v[pre[x]].push_back(temp);
            }
            pre[x]=i;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&l,&r);
            edge temp;
            temp.to=0;temp.cost=-l;
            v[i].push_back(temp);
            temp.to=i;temp.cost=r;
            v[0].push_back(temp);
        }
        spfa();
        for(int i=1;i<n;i++)
            printf("%lld ",dis[i]);
        printf("%lld\n",dis[n]);
    }
    return 0;
}