jzoj 5865. 【NOIP2018模拟9.11】假期旅行 线段树

Description

Input

Output

Sample Input

5 4 3
1 4 1
2 5 3
2 3 2
4 5 2
3
1 5
3 5
4 5

Sample Output

-1
2
1

Data Constraint

Hint

分析：
我们设a[i]$a[i]$为从城市i$i$开始，最远能到达的城市。这样就连成了一个森林。也就是说，对于一个询问l,r$l,r$，就是在森林上面从l$l$开始，最少跳多少步，可以到达一个大于等于r$r$的节点。这个可以倍增求。
关键是求a[i]$a[i]$了，考虑每一个座位，如果在[l,r]$[l,r]$都是空的，那么[l,r]$[l,r]$的这些点的a[i]$a[i]$至少是r$r$，也就是一个区间修改和查询最大值，线段树维护即可。
我们可以把预定的票排序，对于一种票，相当于求已知区间的补集，然后加入线段树即可。

代码：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>

const int maxn=2e5+7;

using namespace std;

int n,m,k,q,x,y,ans,j;
int t[maxn*4],f[maxn][20];

struct node{
    int l,r,k;
}a[maxn];

bool cmp(node a,node b)
{
    if (a.k==b.k) return a.l<b.l;
    return a.k<b.k;
}

void ins(int p,int l,int r,int x,int y,int k)
{
    if ((l==x) && (r==y))
    {
        t[p]=max(t[p],k);
        return;
    }
    int mid=(l+r)/2;
    if (y<=mid) ins(p*2,l,mid,x,y,k);
    else if (x>mid) ins(p*2+1,mid+1,r,x,y,k);
    else 
    {
        ins(p*2,l,mid,x,mid,k);
        ins(p*2+1,mid+1,r,mid+1,r,k);
    }
}

int getmax(int p,int l,int r,int x)
{
    if (l==r) return t[p];
    int mid=(l+r)/2;
    int tmp;
    if (x<=mid) tmp=getmax(p*2,l,mid,x);
           else tmp=getmax(p*2+1,mid+1,r,x);
    return max(tmp,t[p]);
}

int main()
{
    freopen("trip.in","r",stdin);
    freopen("trip.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
    sort(a+1,a+m+1,cmp);
    for (int i=1;i<=n;i++) ins(1,1,n,i,i,i);
    j=1;    
    for (int i=1;i<=k;i++)
    {
        int r=1;
        while (a[j].k==i)
        {
            if (r<a[j].l) ins(1,1,n,r,a[j].l,a[j].l);
            r=max(r,a[j].r);
            j++;
        }
        ins(1,1,n,r,n,n);
    }   
    for (int i=1;i<=n;i++) f[i][0]=getmax(1,1,n,i); 
    for (int j=1;j<20;j++)
    {
        for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    }
    scanf("%d",&q);
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        if (f[x][19]<y) printf("-1\n");
        else
        {
            int k=19;
            ans=0;
            while (k>=0)
            {
                if (f[x][k]<y)
                {
                    x=f[x][k];
                    ans+=(1<<k);
                }
                k--;
            }
            printf("%d\n",ans+1);
        }
    }
}