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,rl,r，就是在森林上面从 l l 开始，最少跳多少步，可以到达一个大于等于rr的节点。这个可以倍增求。

关键是求 a[i] a [ i ] 了，考虑每一个座位，如果在 [l,r] [ l , r ] 都是空的，那么 [l,r] [ l , r ] 的这些点的 a[i] a [ i ] 至少是 r r <script type="math/tex" id="MathJax-Element-905">r</script>，也就是一个区间修改和查询最大值，线段树维护即可。

我们可以把预定的票排序，对于一种票，相当于求已知区间的补集，然后加入线段树即可。

代码：

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

const int maxn=e5+;

using namespace std;

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

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)/;
    if (y<=mid) ins(p*2,l,mid,x,y,k);
    else if (x>mid) ins(p*2+,mid+,r,x,y,k);
    else 
    {
        ins(p*2,l,mid,x,mid,k);
        ins(p*2+,mid+,r,mid+,r,k);
    }
}

int getmax(int p,int l,int r,int x)
{
    if (l==r) return t[p];
    int mid=(l+r)/;
    int tmp;
    if (x<=mid) tmp=getmax(p*2,l,mid,x);
           else tmp=getmax(p*2+,mid+,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=;i<=m;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].k);
    sort(a+,a+m+,cmp);
    for (int i=;i<=n;i++) ins(,,n,i,i,i);
    j=;    
    for (int i=;i<=k;i++)
    {
        int r=;
        while (a[j].k==i)
        {
            if (r<a[j].l) ins(,,n,r,a[j].l,a[j].l);
            r=max(r,a[j].r);
            j++;
        }
        ins(,,n,r,n,n);
    }   
    for (int i=;i<=n;i++) f[i][]=getmax(,,n,i); 
    for (int j=;j<;j++)
    {
        for (int i=;i<=n;i++) f[i][j]=f[f[i][j-]][j-];
    }
    scanf("%d",&q);
    for (int i=;i<=q;i++)
    {
        scanf("%d%d",&x,&y);
        if (f[x][]<y) printf("-1\n");
        else
        {
            int k=;
            ans=;
            while (k>=)
            {
                if (f[x][k]<y)
                {
                    x=f[x][k];
                    ans+=(<<k);
                }
                k--;
            }
            printf("%d\n",ans+);
        }
    }
}