首页 > 其他分享 >UOJ #919. 【UR #28】环环相扣 题解

UOJ #919. 【UR #28】环环相扣 题解

时间:2024-11-26 12:44:03浏览次数:12  
标签:std int 题解 bmod 28 ret UR leq kMaxN

Description

给定一个长度为 \(n\) 的整数序列 \(a_1\sim a_n\),其中的元素两两互不相等。

有 \(q\) 个询问,每个询问给定一个区间 \([l,r]\),你要选择三个下标 \(i,j,k\in[l,r]\) 满足 \(i\neq j,j\neq k,k\neq i\),最大化 \((a_i\bmod a_j)+(a_j\bmod a_k)+(a_k\bmod a_i)\) 的值。

你只需要输出这个最大值。

\(3\leq n\leq2\times10^6\),\(1\leq q\leq8\times10^5\),\(\text{op}\in\{0,1\}\),\(1\leq a_i\leq10^{18}\),\(a_1\sim a_n\) 互不相等,\(1\leq l\leq r\leq n\),\(r-l+1\geq3\)。

Solution

不妨设 \(a_x>a_y>a_z\),那么对于 \((x,y,z)\) 只有两种贡献:\(a_x\bmod a_y+a_y\bmod a_z+a_z\) 和 \(a_x\bmod a_z+a_z+a_y\)。

对于一组询问 \([l,r]\),有个结论是 \([l,r]\) 内的区间最大值和次大值都必须选。

  • 证明

    先把区间的数拿出来并排序,使得 \(a_1<a_2<\ldots<a_m\),则选择 \((m-2,m-1,m)\) 可以得到一个答案下界为 \(a_{m-1}+a_{m-2}\)。

    • 如果最终答案为 \(a_x\bmod a_y+a_y\bmod a_z+a_z\),由于 \(a_x\bmod a_y+a_y\bmod a_z+a_z\leq\min\{a_x,2\cdot a_y-1\}\),则 \(x\leq m-1\) 或 \(y\leq m-2\) 一定没上面那个优,所以 \(x=m\) 且 \(y=m-1\)。

    • 如果最终答案为 \(a_x\bmod a_z+a_z+a_y\),由于 \(a_x\bmod a_z+a_z+a_y\leq a_x+a_y\),当 \(x\neq m\) 一定达不到最优解,又因为 \(a_y\) 只出现了一次,所以 \(y\) 一定尽量取到 \(m-1\)。

于是 \(x\) 和 \(y\) 就固定了,设 \(F(x,l,r)\) 表示将 \([l,r]\) 中的 \(x\) 和把剩下的最大值去掉后的所有 \(k\),\(a_x\bmod a_k+a_k\) 的最大值。

那么答案就是 \(\max\{F(x,l,r)+a_y,F(y,l,r)+a_x\bmod a_y\}\),由于 \(x,y\) 已经确定,所以我们只需要求出 \(F(x,l,r)\) 的值即可。


考虑将 \(F(x,l,r)\) 拆成 \(F(x,l,x-1)\) 和 \(F(x,x+1,r)\)。对于 \(F(x,l,x-1)\),让 \(l\) 从 \(x\) 枚举到 \(1\) 可以得到一个 \(O(n^2)\) 的做法。

又有个结论是如果扫到了某个 \(l\),如果存在至少两个 \(a_i>\frac{a_x}{2}\) 就可以停止扫描。

  • 证明

    不妨设这两个数是 \(a_i,a_j\) 且 \(a_i<a_j\)。

    • 如果 \(a_i>a_x\),与 \(x\) 为区间最大值/次大值矛盾,这个区间一定不会被询问到。

    • 如果 \(\frac{a_x}{2}<a_i<a_x\),则 \(a_i\bmod a_x+a_x=a_i\),已经到了最大值,前面的一定不会更优。

基于这个做法暴力枚举 \(l\) 可以做到 \(O(n\log V+q\log n)\),过不了。


还有个结论是扫描到 \(a_i\) 时,如果已经存在两个数 \(\geq 2\cdot a_i\),则 \(a_i\) 就可以删掉。

  • 证明

    如果 \(a_j\geq 2\cdot a_i\),则 \(a_x\bmod a_j+a_j\geq a_j\geq 2\cdot a_i>a_x\bmod a_i+a_i\),所以 \(a_i\) 一定不会对答案造成贡献。

所以可以在从小到大枚举 \(x\) 的过程中,维护一个栈表示目前还没删掉的数和这些数的删除标记。然后在扫描 \(l\) 的过程中,维护另一个标记表示 \(>\frac{a_x}{2}\) 的个数。如果当前 \(a_i\leq \frac{a_x}{2}\) 就将 \(i\) 的删除标记加 \(1\)。否则将另一个标记加一,如果另一个标记到了 \(2\) 就停止扫描,并把栈里面删除标记为 \(2\) 的数删掉,并将 \(x\) 加到栈里。

容易证明上面那个做法的预处理复杂度为 \(O(n)\)。

时间复杂度:\(O(n+q\log n)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 2e6 + 5;

int n, q, tp;
int64_t a[kMaxN];
std::vector<std::pair<int, int64_t>> vecl[kMaxN], vecr[kMaxN];

int get(int x, int y) { return a[x] > a[y] ? x : y; }

struct SGT {
  int N, mx[kMaxN * 4];

  void pushup(int x) {
    mx[x] = get(mx[x << 1], mx[x << 1 | 1]);
  }

  void build(int n) {
    for (N = 1; N <= n + 1; N <<= 1) {}
    for (int i = N; i <= N + n; ++i) mx[i] = i - N;
    for (int i = N - 1; i; --i) pushup(i);
  }

  int query(int l, int r) {
    int ret = 0;
    for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) {
      if (~l & 1) ret = get(ret, mx[l ^ 1]);
      if (r & 1) ret = get(ret, mx[r ^ 1]);
    }
    return ret;
  }
} sgt;

void getl() {
  static int stk[kMaxN] = {0}, cnt[kMaxN] = {0}, tmp[kMaxN];
  int top = 0;
  for (int i = 1; i <= n; ++i) {
    int now = 0, mx = 0, cur = top + 1;
    int64_t res = LLONG_MIN;
    for (int j = top; j; --j) {
      if (!mx) {
        mx = stk[j];
      } else if (a[stk[j]] < a[mx]) {
        res = std::max(res, a[i] % a[stk[j]] + a[stk[j]]);
      } else {
        res = std::max(res, a[i] % a[mx] + a[mx]);
        mx = stk[j];
      }
      vecl[i].emplace_back(stk[j], res);
      if (a[stk[j]] > a[i] / 2) {
        if (++now == 2) break;
      } else {
        ++cnt[stk[j]];
      }
      cur = j;
    }
    int m = 0;
    for (int j = cur; j <= top; ++j)
      if (cnt[stk[j]] < 2)
        tmp[++m] = stk[j];
    top = cur - 1;
    for (int j = 1; j <= m; ++j) stk[++top] = tmp[j];
    stk[++top] = i;
    std::reverse(vecl[i].begin(), vecl[i].end());
  }
}

void getr() {
  static int stk[kMaxN] = {0}, cnt[kMaxN] = {0}, tmp[kMaxN];
  int top = 0;
  for (int i = n; i; --i) {
    int now = 0, mx = 0, cur = top + 1;
    int64_t res = LLONG_MIN;
    for (int j = top; j; --j) {
      if (!mx) {
        mx = stk[j];
      } else if (a[stk[j]] < a[mx]) {
        res = std::max(res, a[i] % a[stk[j]] + a[stk[j]]);
      } else {
        res = std::max(res, a[i] % a[mx] + a[mx]);
        mx = stk[j];
      }
      vecr[i].emplace_back(stk[j], res);
      if (a[stk[j]] > a[i] / 2) {
        if (++now == 2) break;
      } else {
        ++cnt[stk[j]];
      }
      cur = j;
    }
    int m = 0;
    for (int j = cur; j <= top; ++j)
      if (cnt[stk[j]] < 2)
        tmp[++m] = stk[j];
    top = cur - 1;
    for (int j = 1; j <= m; ++j) stk[++top] = tmp[j];
    stk[++top] = i;
    std::reverse(vecr[i].begin(), vecr[i].end());
  }
}

void prework() {
  sgt.build(n);
  getl(), getr();
}

int64_t F(int x, int l, int r, int mx) {
  int64_t ret = LLONG_MIN;
  int y = sgt.query(l, x - 1), z = sgt.query(x + 1, r);
  if (y && y != mx) ret = std::max(ret, a[y] + a[x] % a[y]);
  if (z && z != mx) ret = std::max(ret, a[z] + a[x] % a[z]);
  auto it1 = std::lower_bound(vecl[x].begin(), vecl[x].end(), std::pair<int, int64_t>{l, LLONG_MIN});
  auto it2 = std::lower_bound(vecr[x].begin(), vecr[x].end(), std::pair<int, int64_t>{r, LLONG_MAX}, std::greater<>());
  if (it1 != vecl[x].end()) ret = std::max(ret, it1->second);
  if (it2 != vecr[x].end()) ret = std::max(ret, it2->second);
  return ret;
}

int64_t query(int l, int r) {
  int x = sgt.query(l, r), y = get(sgt.query(l, x - 1), sgt.query(x + 1, r));
  return std::max(F(x, l, r, y) + a[y], F(y, l, r, x) + a[x] % a[y]);
}

void dickdreamer() {
  std::cin >> n >> q >> tp;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  prework();
  int64_t lastans = 0;
  for (int i = 1; i <= q; ++i) {
    int l, r;
    std::cin >> l >> r;
    l = (l + lastans * tp - 1) % n + 1;
    r = (r + lastans * tp - 1) % n + 1;
    std::cout << (lastans = query(l, r)) << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:std,int,题解,bmod,28,ret,UR,leq,kMaxN
From: https://www.cnblogs.com/Scarab/p/18569891

相关文章

  • WPF笔记4——静态资源(StaticResource)
    在WPF中,资源(Resource)是一种存储和共享对象的方式,可以在应用程序的不同部分之间重用。在WPF中,有两种资源引用方式:静态资源(StaticResource)和动态资源(DynamicResource)静态资源(StaticResource)静态资源,用于在xaml加载时解析并应用资源。它通常用于引用在资源字典中定义的对象,如样式......
  • Python_异步编程-并发编程-协程和future
    操作系统创建线程Unix进程的设计思想,实现了forkexecwaitexit四个精巧的系统调用来支持对进程的灵活管理。父进程进程通过fork系统调用创建自身的副本(子进程);称为“子进程”的副本可调用exec系统调用用另一个程序覆盖其内存空间,这样就可以执行新程序了;......
  • 【题解】P4688 [Ynoi2016] 掉进兔子洞
    洛谷P4688[Ynoi2016]掉进兔子洞莫队配合bitset例题。lxl官方题解。https://olddrivertree.blog.uoj.ac/blog/4690想到如果只有每个数只出现一次怎么做,可以莫队移动区间用bitset维护每个数的是否出现,再对\(3\)个区间进行与操作就是交集出现的数。但是这只能求出数字......
  • 11.25 NOIP 模拟赛题解
    T1P1069[NOIP2009普及组]细胞分裂原题链接这道题就是基本的数学知识。我们直接来转化题意,这道题就是让我们求min⁡(k......
  • input的onblur和onchange事件区别是什么?
    onblur和onchange都是HTML元素的事件属性,用于处理用户与表单元素交互时的不同情况。它们的主要区别在于触发时机和触发条件:onblur(失去焦点):当一个元素失去焦点时触发。这意味着当用户点击页面上其他元素、按下Tab键切换到下一个元素或使用鼠标点击到其他地方时,都会......
  • 说下你对柯里化函数(currying)的理解,它有什么运用场景?
    柯里化(Currying)是一种将接受多个参数的函数转换为一系列只接受一个参数的函数的技术。在JavaScript中,柯里化函数会返回一个新的函数,这个新函数接受下一个参数,并继续返回新的函数,直到所有参数都传入为止,最终返回计算结果。理解柯里化:想象一下一个需要三个参数的函数add(x,......
  • R : 计算平均Bray-Curtis距离.R
    rm(list=ls())setwd("C:\\Users\\Administrator\\Desktop\\machinelearning\\MultipleLinearRegression")#导入所需的库#如果需要的话,可以使用`install.packages("readr")`安装readr库library(readr)#读取CSV文件,确保不使用行名data<-read.csv(&qu......
  • dymean-structure损失总结
    在full_profile=False的情况下,整体的损失函数会简化为以下内容:1.总Loss当full_profile=False时,总的损失函数为:\(\text{loss}=\text{xloss}+\text{violation_loss},\)其中:\(\text{violation_loss}=\text{bond_loss}+\text{sc_bond_loss}.\)2.各部分的具......
  • CF1753C题解
    鲜花被卡了一万年。考虑过序列变换的各种情况和逆序对,结果这俩情况状态太多,而且相同逆序对ans也不一定相同。/llsol我们最后想要的状态为所有\(0\)都在\(1\)的左边,令\(cnt_0\)为\(0\)的个数,\(cnt_1\)为\(1\)个数。\(cnt_0+cnt_1=n\),结束的状态前\(cnt_0\)个数......
  • P5572 [CmdOI2019] 简单的数论题 题解
    题目描述\(T\)组数据,给定\(n\gem\),求:\[\sum_{i=1}^n\sum_{j=1}^m\varphi(\frac{\text{lcm}(i,j)}{\gcd(i,j)})\\\]对\(23333\)取模。数据范围\(1\leT\le3\cdot10^4,1\lem\len\le5\cdot10^4\)。时间限制\(\texttt{2s}\),空间限制\(\texttt{128......