莫队块长
  • 板块学术版
  • 楼主MyukiyoMekyaZJunior
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/12/9 19:43
  • 上次更新2023/11/5 06:20:54
查看原帖
莫队块长
51376
MyukiyoMekyaZJunior楼主2020/12/9 19:43
struct Query	// 这是一个莫队(
{
    int l,r;
    inline bool operator < (const Query &nt) const
    {
        if(l/block==nt.l/block)
            return ((l/block)&1)?r<nt.r:r>nt.r;
        return l<nt.l;
    }
};

这个 blockblock (块长)一般取的是 n\sqrt n ,但是我在一些地方看到可以取 n2m3\dfrac {n}{\sqrt{\frac {2m}{3}}}nn 是数组长度,mm 是询问个数。

请问这样真的能有效减少运行时间么?原理是什么?

2020/12/9 19:43
加载中...