国旗计划：原题链接题意：     输入：第一行给你一个n和m，n代表边防战士的人数，m代表总共有几个站点，接下来有n行，每行给你两个站点C和D，战士行走的区间为[C,D]，区间会重叠，但不会完全覆盖。     输出：输出每个战士，在以他自身的区间为起点的前提下，至少需要多少人可以使战士之间行走的区间形成一个环。做题思路：     初步入手本题，可以想到如果要判断成环，最好的办法是将环拆分成链，即当右边的点小于左边的点时，说明该点跨过了环，因此将右边的点加上站点总数，即可生成假设在一条链上的两点间的距离。初始输入代码： cin >>n>>m;    for (int i=1;i<=n;i++)    {        cin >>w[i].l>>w[i].r;        //破环成链        if (w[i].r<w[i].l)w[i].r+=m;    }     在生成完链后，题目要求也变成了找到覆盖3-10的这个区间，问题是该怎么求解，找到最少的人数去覆盖这个区间，这里可以先试用贪心的思想进行思考，因为战士之间的区间是不会完全覆盖的，所以只要每次是下一个选中区间的起点是当前区间中，最靠近选择区间末的区间，即可完成最少人数成环这一条件。     以此为依据，在原先来链的基础上，再copy（复制）一份每个区间都加上一个环时的情况，用以判断当区间跨过环时，存在2-5的区间，但无法求解的情况，同时，因为题目只规定了战士不会被完全覆盖，但其顺序可能是被打乱的，所以为了满足区间查找的单调性，对数组进行sort排序。改进后输入代码： //输入+处理     cin >>n>>m;    for (int i=1;i<=n;i++)    {     //记录id，在输出结果时，是原序输出        w[i].id=i;        cin >>w[i].l>>w[i].r;        //破环成链        if (w[i].r<w[i].l)w[i].r+=m;    }    //起点排序    sort(w+1,w+n+1);    //复制一份    n2=n*2;    for (int i=n+1;i<=n2;i++)     {        w[i]=w[i-n];        w[i].l+=m;        w[i].r+=m;    }     接下来是查找区间，但注意，如果直接查找区间会导致是o(n^2)的时间复杂度，也就是超时，因此需要优化区间查找，为此，来到本次题解的重中之中，倍增(st)。     在使用倍增前，先了解倍增的使用条件：必须要有单调性，很显然，这个条件已经满足。     其次是倍增的原理：同二分一样，二分的作用是不断缩减数组，以此来找到需要的数，而倍增则是不断增大。它的运算原理可以参考二进制定理：2^n=2^(n-1)+2^(n-2)+...+2^0+1。     因此其运行规则为：先走2^n步，倘若大于等于数值则说明步数过多，倘若小于，将将步数加上2^n，加至最后，加起来的总步数会是要求步数-1的值。st的代码：//贪心选择区间+st生成静态数据void st(){    //自建图：    int next=1;    //链上共n2条    for (int i=1;i<=n2;i++)    {        //找到每个区间离右端点最近的左端点所在的区间        while (next <= n2 && w[next].l<= w[i].r)next++;        //记录区间        go[i][0]=next-1;    }        //倍增：i = 1，2，4，8，16..共 logn 次    for (int i=1;(1 << i)<=n;i++)    {        //枚举每条线段        for (int s=1;s<=n2;s++)        {    //若走2^3步，2^3= 2^2+2^2            //先从 s 到走2^2步到中转站            //再从中转站走2^2到终点            go[s][i]=go[go[s][i-1]][i-1];        }    }}     构建完图后，即可运用图表进行求解每位士兵的最少人数，即st的调用。//st的使用 void getRes(int x){ //len为终点长度，该长度代表能否成环 //now为初始的节点 //ans记录人数，因为放入了自身的初始节点，所以人数至少为1     int len=w[x].l+m,now=x,ans=1;    //i初始为log2(n),20是为了方便计算     for (int i=20;i>=0;i--)    {     //从大到小开始查找         int to=go[now][i];        //当to存在,长度在len内         if (to && w[to].r<len)        {            ans=ans+(1<<i); //累加跳过的区域            now=to;//从新位置开始        }    }    //记录时使用id记录人数，毕竟sort过了，但输出要使用原序列  //ans+1因为ans是小于len的，还无法成环， //但因为st性质，他的下一步必定大于len，此时可以成环     res[w[x].id]=ans+1;}     最后直接输出存入的数值，即可得出答案，这里直接放ac代码：#include <bits/stdc++.h>using namespace std;const int maxn = 4e5 + 10;int n, n2, m;struct Index{    int id,l,r;//编号+区间    //以起始点小的排序    bool operator<(const Index &b) const { return l< b.l;}};Index w[maxn*2];//破环成链,因此空间需要开两份int go[maxn][25];//倍增记录自建图int res[maxn];//记录结果//贪心选择区间+st生成静态数据void st(){    //自建图：    int next=1;    //在链上选择共n2条    for (int i=1;i<=n2;i++)    {        //每个区间的下一个右端点最大的区间        while (next <= n2 && w[next].l<= w[i].r)next++;        //区间i的下一个区间        go[i][0]=next-1;    }        //倍增：i = 1，2，4，8，16..共 logn 次    for (int i=1;(1 << i)<=n;i++)    {        //枚举每条线段        for (int s=1;s<=n2;s++)        {    //若走 2^3 步，2^3= 2^2+2^2            //先从 s 到走2^2步到中转站            //再从中转站走2^2到终点            go[s][i]=go[go[s][i-1]][i-1];        }    }}//st的使用 void getRes(int x){ //len为终点长度，该长度代表能否成环 //now为初始的节点 //ans记录人数，因为放入了自身的初始节点，所以人数至少为1     int len=w[x].l+m,now=x,ans=1;    //i初始为log2(n),20是为了方便计算     for (int i=20;i>=0;i--)    {     //从大到小开始查找         int to=go[now][i];        //当to存在,长度在len内         if (to && w[to].r<len)        {            ans=ans+(1<<i); //累加跳过的区域            now=to;//从新位置开始        }    }    //记录时使用id记录人数，毕竟sort过了，但输出要使用原序列  //ans+1因为ans是小于len的，还无法成环， //但因为st性质，他的下一步必定大于len，此时可以成环     res[w[x].id]=ans+1;}int main(){ //输入+初步处理     cin >>n>>m;    for (int i=1;i<=n;i++)    {        w[i].id=i;        cin >>w[i].l>>w[i].r;        //破环成链        if (w[i].r<w[i].l)w[i].r+=m;    }    //起点排序    sort(w+1,w+n+1);    //复制一份    n2=n*2;    for (int i=n+1;i<=n2;i++)     {        w[i]=w[i-n];        w[i].l+=m;        w[i].r+=m;    }    //倍增(st)开始     st();    //循环得出每个节点的最少成环人数     for (int i=1;i<=n;i++)getRes(i);    //输出答案     for (int i=1;i<=n;i++)cout <<res[i]<<" ";    cout <<"\n";    return 0;}