ZJOI讲课的题目，数据结构什么的还是很友好的说

首先我们发现题目中提到的距离\(\le L\)的东西显然可以用单调队列维护

但是暴力搞去不掉区间并的限制，那么我们考虑从区间并入手

对于这种问题的套路有一个就是线段树维护一个区间的最优解，然后计算完一个点的答案之后直接在线段树上更新即可

所以我们有了一个很naive的思路——线段树套单调队列，但随便一想时空复杂度都是\(O(n^2)\)的

让我们想一下复杂度变大的原因是什么，其实就是pushdown带来的大量空间浪费

我们再仔细观察依稀这个问题的性质，发现其可以标记永久化，那么就很舒服了，时空复杂度都达到了优秀的\(O(n\log\ n)\)

然后像我这样naive的人就写出了这样的巨慢CODE

#include<cstdio>

#include<cctype>

#include<deque>

#include<algorithm>

#define RI register int

#define CI const int&

#define Tp template <typename T>

using namespace std;

const int N=250005,INF=2e9;

int n,m,rst[N<<1],L[N],R[N],ans[N],dis[N],cnt,ret;

class FileInputOutput

{

    private:

        static const int S=1<<21;

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

        #define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))

        char Fin[S],Fout[S],*A,*B; int Ftop,pt[15];

    public:

        Tp inline void read(T& x)

        {

            x=0; char ch; while (!isdigit(ch=tc()));

            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

        }

        Tp inline void write(T x)

        {

            if (!x) return (void)(pc('0'),pc('\n')); if (x<0) x=-x,pc('-'); RI ptop=0;

            while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc('\n');

        }

        inline void Fend(void)

        {

            fwrite(Fout,1,Ftop,stdout);

        }

        #undef tc

        #undef pc

}F;

inline int find(CI x)

{

    return lower_bound(rst+1,rst+cnt+1,x)-rst;

}

class Segment_Tree

{

    private:

        deque <int> dq[N<<3];

    public:

        #define TN CI now=1,CI l=1,CI r=cnt

        #define O beg,end,pos

        inline void build(TN)

        {

            dq[now].push_back(1); if (l==r) return; int mid=l+r>>1;

            build(now<<1,l,mid); build(now<<1|1,mid+1,r);

        }

        inline void insert(CI beg,CI end,CI pos,TN)

        {

            while (!dq[now].empty()&&ans[pos]<ans[dq[now].back()]) dq[now].pop_back();

            dq[now].push_back(pos); if (l==r) return; int mid=l+r>>1;

            if (beg<=mid) insert(O,now<<1,l,mid); if (end>mid) insert(O,now<<1|1,mid+1,r);

        }

        inline void getpos(CI beg,CI end,CI pos,TN)

        {

            if (beg<=l&&r<=end)

            {

                while (!dq[now].empty()&&dis[pos]-dis[dq[now].front()]>m) dq[now].pop_front();

                if (!dq[now].empty()&&(!~ret||ans[dq[now].front()]<ans[ret]))    ret=dq[now].front(); return;

            }

            int mid=l+r>>1; if (beg<=mid) getpos(O,now<<1,l,mid); if (end>mid) getpos(O,now<<1|1,mid+1,r);

        }

        #undef TN

        #undef O

}SEG;

int main()

{

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    RI i; for (F.read(n),F.read(m),i=2;i<=n;++i)

    F.read(L[i]),F.read(R[i]),rst[++cnt]=L[i],rst[++cnt]=R[i],F.read(dis[i]);

    sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;

    for (i=2;i<=n;++i) L[i]=find(L[i]),R[i]=find(R[i]);

    for (SEG.build(),i=2;i<=n;++i)

    {

        ret=-1; SEG.getpos(L[i],R[i],i); if (!~ret) ans[i]=INF;

        else ans[i]=ans[ret]+1; SEG.insert(L[i],R[i],i);

    }

    for (i=2;i<=n;++i) F.write(ans[i]!=INF?ans[i]:-1); return F.Fend(),0;

}

没办法，我们发现这个程序慢有两点：

• deque巨慢无比，而且内存占用极大
• 没有维护每个节点的答案，这样查询的时候复杂度极高

然后解决方案也很简单：

• 把deque换成list（快如闪电）
• 单独写删除操作，并且记下每个点的答案

然后就可以顺利地通过此题了QWQ

#include<cstdio>

#include<cctype>

#include<list>

#include<algorithm>

#define RI register int

#define CI const int&

#define Tp template <typename T>

using namespace std;

const int N=250005,INF=1e9;

int n,m,rst[N<<1],q[N],L[N],R[N],dis[N],ans[N],cnt,pos;

class FileInputOutput

{

    private:

        static const int S=1<<21;

        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

        #define pc(ch) (Ftop<S?Fout[Ftop++]=ch:(fwrite(Fout,1,S,stdout),Fout[(Ftop=0)++]=ch))

        char Fin[S],Fout[S],*A,*B; int Ftop,pt[15];

    public:

        Tp inline void read(T& x)

        {

            x=0; char ch; while (!isdigit(ch=tc()));

            while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

        }

        Tp inline void write(T x)

        {

            if (!x) return (void)(pc('0'),pc('\n')); if (x<0) x=-x,pc('-'); RI ptop=0;

            while (x) pt[++ptop]=x%10,x/=10; while (ptop) pc(pt[ptop--]+48); pc('\n');

        }

        inline void Fend(void)

        {

            fwrite(Fout,1,Ftop,stdout);

        }

        #undef tc

        #undef pc

}F;

inline int find(CI x)

{

    return lower_bound(rst+1,rst+cnt+1,x)-rst;

}

class Segment_Tree

{

    private:

        list <int> dq[N<<3]; int val[N<<3];

        inline void miner(int &x,CI y)

        {

            if (y<x) x=y;

        }

        inline int get(CI now)

        {

            if (dq[now].empty()) return INF; return ans[dq[now].front()];

        }

        inline void pushup(CI now,const bool& op)

        {

            val[now]=get(now); if (op) miner(val[now],val[now<<1]),miner(val[now],val[now<<1|1]);

        }

    public:

        #define TN CI now=1,CI l=1,CI r=cnt

        #define O beg,end,pos

        inline void build(TN)

        {

            val[now]=INF; if (l==r) return; int mid=l+r>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r);

        }

        inline void insert(CI beg,CI end,CI pos,TN)

        {

            if (beg<=l&&r<=end)

            {

                while (!dq[now].empty()&&ans[pos]<=ans[dq[now].back()])

                dq[now].pop_back(); dq[now].push_back(pos); return pushup(now,l!=r);

            }

            int mid=l+r>>1; if (beg<=mid) insert(O,now<<1,l,mid);

            if (end>mid) insert(O,now<<1|1,mid+1,r); pushup(now,l!=r);

        }

        inline void remove(CI beg,CI end,CI pos,TN)

        {

            if (beg<=l&&r<=end)

            {

                while (!dq[now].empty()&&dq[now].front()<=pos)

                dq[now].pop_front(); return pushup(now,l!=r);

            }

            int mid=l+r>>1; if (beg<=mid) remove(O,now<<1,l,mid);

            if (end>mid) remove(O,now<<1|1,mid+1,r); pushup(now,l!=r);

        }

        inline int query(CI beg,CI end,TN)

        {

            if (beg<=l&&r<=end) return val[now]; int mid=l+r>>1,ret=get(now);

            if (beg<=mid) miner(ret,query(beg,end,now<<1,l,mid));

            if (end>mid) miner(ret,query(beg,end,now<<1|1,mid+1,r)); return ret;

        }

        #undef TN

        #undef O

}SEG;

int main()

{

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    RI i,H=1,T=1; for (F.read(n),F.read(m),i=2;i<=n;++i)

    F.read(L[i]),F.read(R[i]),rst[++cnt]=L[i],rst[++cnt]=R[i],F.read(dis[i]);

    sort(rst+1,rst+cnt+1); cnt=unique(rst+1,rst+cnt+1)-rst-1;

    for (i=2;i<=n;++i) L[i]=find(L[i]),R[i]=find(R[i]);

    for (SEG.build(),SEG.insert(L[1]=q[1]=1,R[1]=cnt,1),i=2;i<=n;++i)

    {

        while (H<=T&&dis[i]-dis[q[H]]>m) pos=q[H++],SEG.remove(L[pos],R[pos],pos);

        ans[i]=SEG.query(L[i],R[i]); if (ans[i]!=INF)

        F.write(++ans[i]),SEG.insert(L[i],R[i],i),q[++T]=i; else F.write(-1);

    }

    return F.Fend(),0;

}

最新文章

1. go语言：多个[]byte数组合并成一个[]byte
2. 【USACO 3.2】Factorials（阶层非零尾数）
3. Sqlserver 2008清除数据库日志
4. JavaScript——理解闭包及作用
5. UIEditBox 控件的使用 点击输入框 自动切换 到下一个输入框 并上移 背景
6. 【java基础学习】网络编程
7. Solrj和Solr DIH索引效率对比分析
8. tp三大自动
9. java.util.concurrent包API学习笔记
10. phpstorm 和web storm汉化
11. AutoLayout的一些注意事项
12. Quartz 2D官方文档翻译（持续更新中）
13. 安装用户脚本的福音：Tampermonkey（油猴）
14. Spring框架下的定时任务quartz框架的使用
15. [BZOJ1861][ZJOI2006]书架
16. tomcat 启动方式
17. POI 读取 excel
18. 把项目挂载到composer上
19. FastAdmin笔记~
20. @log的decorator完美实现（原创）

热门文章

1. 基于python语言的tensorflow的‘端到端’的字符型验证码识别源码整理(github源码分享)
2. git 建议使用
3. Python：SQLMap源码精读—基于时间的盲注（time-based blind）
4. ZZCMS v8.2 前台Insert注入+任意文件删除
5. Springboot 系列（十二）使用 Mybatis 集成 pagehelper 分页插件和 mapper 插件
6. jQuery获取或设置元素的宽度和高度
7. HeadFirst设计模式读书笔记之工厂模式
8. element表格添加序号
9. PhotoshopCS5中将单位修改成百分比
10. 《JavaScript高级程序设计》笔记：表单脚本（十四）