「JSOI2013」贪心的导游

2021-04-18 11:26

阅读：622

标签：维护 for file swap geo swa while 处理 return

「JSOI2013」贪心的导游

传送门

多次询问区间内%一个数的最大值 ~~我们不妨设这个数为M_sea~~

值域比较小所以考虑分块维护。

我们观察到对于给定的一个 \(p\) ，函数 \(y = x \% p\) 是分段的且在各段内递增，所以我们可以先分块，记一下每个块内小于等于某个数的最大值，记为 \(g_i\) ，那么我们显然是要在所有的 \(i = kp - 1, k \ge 1\) 中查询 \(g_i\) 并减掉会被 % 掉的部分，那么我们就可以预处理出一个块内的答案了，然后查询的时候暴力查就是了。

#include 
#include 
#include 
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template  inline void swap(T& a, T& b) { T t = a; a = b; b = t; }
template  inline T max(T a, T b) { return a > b ? a : b; }
template  inline void read(T& s) {
    s = 0; int f = 0; char c = getchar();
    while ('0' > c || c > '9') f |= c == '-', c = getchar();
    while ('0'  r) swap(l, r);
        if (pos[l] == pos[r])
            for (rg int i = l; i

「JSOI2013」贪心的导游

标签：维护 for file swap geo swa while 处理 return

原文地址：https://www.cnblogs.com/zsbzsb/p/12283829.html

上一篇：vue中使用 vue-i18n 兼容多国语言

下一篇：JSP学习-sessionDemo

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：「JSOI2013」贪心的导游
文章链接：http://soscw.com/index.php/essay/76257.html

亲，登录后才可以留言！

「JSOI2013」贪心的导游

「JSOI2013」贪心的导游

评论

热门文章

推荐文章

最新文章

置顶文章