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+);
}
}
}