题解：P11554 [ROIR 2016] 假期旅行 (Day 1)

· · 题解

题目分析

观察题目，发现不用在意每一站坐在哪个空座位，而是坐了多少个不同的座位。那么可以将每个座位的起点与终点存在动态数组中，再用倍增求解即可。

AC 代码

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
const int Log=20;

int n,m,k,q;

vector<pair<int,int>> vec[maxn];
int up[maxn][Log];

int ask(int s,int t){
    int ans=0;
    for(int i=19;i>=0;i--)
        if(up[s][i]<t) ans+=(1<<i),s=up[s][i];
    if(up[s][0]>=t) return ans+1;
    return -1;
}

#define fi first
#define se second
signed main(){
    freopen("trip.in","r",stdin);
    freopen("trip.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1,s,t,id;i<=m;i++){
        scanf("%d%d%d",&s,&t,&id);
        vec[id].push_back({s,t});
    }   

    for(int i=1;i<=k;i++){
        sort(vec[i].begin(),vec[i].end());
        int u=1;
        for(auto& v:vec[i]){
            if(v.fi>u) up[u][0]=max(up[u][0],v.fi);
            u=max(u,v.se);
        }
        if(u<=n) up[u][0]=n;
    }

    for(int i=1;i<=n;i++) up[i][0]=max(up[i][0],up[i-1][0]);
    for(int i=1;i<20;i++)
        for(int j=1;j<=n;j++)
            up[j][i]=up[up[j][i-1]][i-1];

    scanf("%d",&q);
    while(q--){
        int s,t;
        scanf("%d%d",&s,&t);
        printf("%d\n",ask(s,t));
    }
    return 0;
}