题解：P7719 「EZEC-10」多彩的线段

· · 题解

对于询问，贪心的从左到右扫一遍，每次选出当前左端点往右覆盖最长的线段。

对于每个 i\in [1,n]，预处理出 d_i 表示以 i 为左端点的最长线段长度，那么询问就是不断执行 a=a+d_a，直到 a\ge b 为止。

我们把 i 向 i+d_i 连边，这样 n 个点就构成了一棵以 n 为根的有根树，询问就是求 a 的第一个 \ge b 的祖先。

先考虑怎么求出 d_i，对于每种颜色 (l_i,r_i,k_i)，相当于 \forall j\in [1,k_i]，i\in[l,r-j] 的 d_i\ge j。可以把每种颜色拆成一个区间和 k_i 个单点（为了方便预处理直接拆成 k_i 个区间）。

设 K=\max(k_i)，由于 d_i\le K\le 10 因此可以对于每种长度 j 求出 O(m) 个区间的并集，并集中的 d_i\ge j。

同时可以发现，j 的并集一定包含 j+1 的并集，因此可以用 j 的并集，减去 j+1 的并集，得到 d_i=j 的区间，使用双指针可以做到线性。

这部分预处理的时间复杂度为 O(mK\log m)，瓶颈在于给区间排序。

但是 n 很大，不能暴力建树，考虑进行缩点。

如果一条链满足，链中每个点到它父亲的距离一样，就可以进行缩点，仅保留链底，链顶，以及相邻两点的距离，这样我们仍然可以求出每个点在树上的深度。

如果一段区间 [l,r] 满足 \forall i\in [l,r],d_i=j，那么可以仅保留开头和末尾的 j 个点，中间的点都可以缩起来。

我们称保留下来的点为关键点，通过之前的预处理可以发现，长度为 n 的序列可以划分为 O(m) 个 d_i 相同的区间和 O(mK) 个单点，因此关键点数是 O(mK) 的。

求出关键点后，考虑如何建树，我们需要找到每个关键点缩点后的父亲。因为原树每条边的长度 \le K，并且不存在边 (a,b) 和 (c,d)，使得 a\lt c\lt d\lt b，因为这样 c 一定可以到达 b。因此，每个关键点的缩点后的父亲在关键点序列中到它的距离也 \le K，直接暴力枚举即可，复杂度 O(mK^2)。

对于询问 (a,b)，需要找到 a 所在链的链底，二分找到 \le a 的第一个关键点，同样到链底的距离 \le K。然后找到 \le b 的第一个关键点祖先即可算出距离，这里我写倍增被卡常了，换成求出 DFS 序后 O(K) 枚举就行了。

时间复杂度 O(mK(\log m+K)+q(\log m+K))，空间复杂度 O(mK)。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
#define fi first
#define se second
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
    char c=getchar();
    for(;c<48||c>57;c=getchar());
    for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
int ty,n,m,q,d[N],p[N],dp[N],ct,Ans,in[N],out[N];
vector<int>e[N];
vector<pair<int,int> >vc[12],tt;
void dfs(int x){
    in[x]=++in[0];
    for(auto v:e[x])dfs(v);
    out[x]=in[0];
}
int main(){
    read(ty),read(n),read(m),read(q);
    for(int i=1,l,r,k;i<=m;++i){
        read(l),read(r),read(k);
        for(int j=1;j<=k;++j)vc[j].emplace_back(l,r-j);
    }
    for(int j=10;j;--j){
        sort(vc[j].begin(),vc[j].end());
        vector<pair<int,int> >tmp;
        for(int i=0;i<vc[j].size();++i){
            auto [l,r]=vc[j][i];
            while(i+1<vc[j].size()&&vc[j][i+1].fi<=r+1)++i,r=max(r,vc[j][i].se);
            tmp.emplace_back(l,r);
        }
        vc[j]=tmp;
        for(int i=0,o=0;i<vc[j].size();++i){
            auto [l,r]=vc[j][i];
            while(l<=r){
                while(o<vc[j+1].size()&&vc[j+1][o].fi<l)++o;
                if(o<vc[j+1].size()){
                    if(vc[j+1][o].fi>r){
                        tt.emplace_back(l,j);
                        break;
                    }
                    if(vc[j+1][o].fi>l)tt.emplace_back(l,j);
                    l=vc[j+1][o].se+1;
                }else{
                    tt.emplace_back(l,j);
                    break;
                }
            }
        }
    }
    sort(tt.begin(),tt.end());
    tt.emplace_back(n,0);
    for(int i=0;i+1<tt.size();++i){
        int lim=tt[i].fi+tt[i].se;
        if(i&&tt[i-1].se>tt[i].se)++lim;
        lim=min(lim,tt[i+1].fi);
        for(int j=tt[i].fi;j<lim;++j)
            ++ct,p[ct]=j,d[ct]=tt[i].se;
    }
    p[++ct]=n;
    for(int i=ct-1;i;--i)
        for(int j=i+1;;++j)if((p[j]-p[i])%d[i]==0){
            e[j].emplace_back(i),dp[i]=dp[j]+(p[j]-p[i])/d[i];
            break;
        }
    dfs(ct);
    for(int i=1,a,b;i<=q;++i){
        read(a),read(b);
        if(ty)a^=Ans,b^=Ans;
        int u=upper_bound(p+1,p+ct+1,a)-p-1,v=upper_bound(p+1,p+ct+1,b)-p-1;
        while((a-p[u])%d[u]!=0)--u;
        Ans=-(a-p[u])/d[u];
        while(in[u]<in[v]||in[u]>out[v])--v;
        Ans+=dp[u]-dp[v];
        if(b!=p[v])Ans+=(b-p[v]-1)/d[v]+1;
        printf("%d\n",Ans);
    }
    return 0;
}