首页 > 其他分享 >UOJ #712. 【北大集训2021】简单数据结构

UOJ #712. 【北大集训2021】简单数据结构

时间:2024-08-10 22:06:36浏览次数:10  
标签:std return int 712 kMaxN stk 2021 UOJ vec

Description

你有一个长度为 \(n\) 的序列 \(a\),下面你要进行 \(q\) 次修改或询问。

  1. 给定 \(v\),将所有 \(a_i\) 变为 \(\min(a_i, v)\)。
  2. 将所有 \(a_i\) 变为 \(a_i + i\)。
  3. 给定 \(l, r\),询问 \(\sum_{i=l}^r a_i\)。

\(1\leq n,q\leq 2\times 10^5,0\leq a_i,v_i\leq 10^{12}\)。

Solution

首先如果没有 chkmin 操作是好做的。同时如果 \(a_i\) 初始值为 \(0\) 那么从始至终序列 \(a\) 都是单调不降的,对于 chkmin 操作只要二分+区间赋值,也很好做。

考虑 \(a_i\) 初值不为 \(0\) 的情况。

注意到如果某个时刻 \(x<y\) 且 \(a_x\leq a_y\),那么之后的所有时刻都满足 \(a_x\leq a_y\),这是显然的。

然后就可以发现对于所有 chkmin 过的位置,它们的 \(a\) 值一定单调不降。于是只要维护当前 chkmin 过的位置,对于这些二分+区间赋值。没有 chkmin 的位置直接线段树维护即可。

考虑怎么求出每个 \(a_i\) 第一次被 chkmin 的时间。设 \(v_i\) 表示第 \(i\) 次操作 chkmin 的值,\(c_i\) 表示前 \(i\) 次操作做了多少次二操作。

容易发现对于每个 \(i\),可以二分答案 \(p\),那么对于 \([1,p]\) 里的所有操作,如果存在 \(a_i+i\cdot c_j\geq v_j\) 就说明 \(p\) 可行。移项一下可以得到 \(a_i\geq v_j-i\cdot c_j\),右边是个关于 \(i\) 的一次函数,所以可以对于前 \(p\) 个操作按照 \((c_j,v_j)\) 维护下凸壳,然后用 \(k=i\) 的直线去截这个凸壳即可快速得到答案。

但是这么做是 \(O\left(nq\log^2 n\right)\) 的,可以用整体二分优化到 \(O\left(q\log^2 n\right)\)。

时间复杂度:\(O\left((n+q)\log^2 n\right)\)。

Code

#include <bits/stdc++.h>

#define int int64_t

using pii = std::pair<int, int>;

const int kMaxN = 2e5 + 5;

int n, q;
int a[kMaxN], op[kMaxN], l[kMaxN], r[kMaxN], v[kMaxN];
std::vector<int> vv[kMaxN];
std::vector<std::tuple<int, int, int>> chkm;

pii add(pii a, pii b) { return {a.first + b.first, a.second + b.second}; }
pii sub(pii a, pii b) { return {a.first - b.first, a.second - b.second}; }
int64_t mul(pii a, pii b) {
  return 1ll * a.first * b.second - 1ll * a.second * b.first;
}

int64_t func(int k, pii a) { return -1ll * k * a.first + a.second; }

void solve(std::vector<std::tuple<int, int, int>> vec, std::vector<int> id) {
  if (!vec.size()) return;
  if (vec.size() == 1) {
    auto [j, c, v] = vec[0];
    for (auto i : id) {
      if (a[i] >= v - i * c) {
        vv[j].emplace_back(i);
      }
    }
    return;
  }
  std::vector<pii> pt, stk;
  std::vector<int> Lv, Rv;
  std::vector<std::tuple<int, int, int>> lvec, rvec;
  for (int i = 0; i < vec.size() / 2; ++i) {
    lvec.emplace_back(vec[i]);
    pt.emplace_back(std::get<1>(vec[i]), std::get<2>(vec[i]));
  }
  for (int i = vec.size() / 2; i < vec.size(); ++i) rvec.emplace_back(vec[i]);
  std::sort(pt.begin(), pt.end());
  for (auto p : pt) {
    for (; stk.size() >= 2 &&
           mul(sub(p, stk.back()), sub(stk.back(), stk[stk.size() - 2])) >= 0;
         stk.pop_back()) {
    }
    stk.emplace_back(p);
  }
  for (auto i : id) {
    int L = 0, R = stk.size(), res = 0;
    while (L + 1 < R) {
      int mid = (L + R) >> 1;
      if (func(i, stk[mid]) <= func(i, stk[mid - 1]))
        L = res = mid;
      else
        R = mid;
    }
    if (func(i, stk[res]) <= a[i])
      Lv.emplace_back(i);
    else
      Rv.emplace_back(i);
  }
  solve(lvec, Lv), solve(rvec, Rv);
}

void prework() {
  std::vector<int> id(n);
  std::iota(id.begin(), id.end(), 1);
  solve(chkm, id);
}

struct SGT {
  int cnt[kMaxN * 4];
  int64_t mx[kMaxN * 4], mxid[kMaxN * 4], sum[kMaxN * 4], sumid[kMaxN * 4],
      tag[kMaxN * 4], tagcov[kMaxN * 4];

  void pushup(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    sumid[x] = sumid[x << 1] + sumid[x << 1 | 1];
    mx[x] = std::max(mx[x << 1], mx[x << 1 | 1]);
    mxid[x] = std::max(mxid[x << 1], mxid[x << 1 | 1]);
    cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
  }

  void addtag1(int x, int64_t v) {
    if (!cnt[x]) return;
    sum[x] += sumid[x] * v, tag[x] += v;
    mx[x] += mxid[x] * v;
  }

  void addtag2(int x, int64_t v) {
    if (!cnt[x]) return;
    sum[x] = cnt[x] * v, mx[x] = tagcov[x] = v;
    tag[x] = 0;
  }

  void pushdown(int x) {
    if (~tagcov[x]) {
      addtag2(x << 1, tagcov[x]), addtag2(x << 1 | 1, tagcov[x]);
      tagcov[x] = -1;
    }
    if (tag[x]) {
      addtag1(x << 1, tag[x]), addtag1(x << 1 | 1, tag[x]);
      tag[x] = 0;
    }
  }

  void build(int x, int l, int r, bool op = 1) {
    tagcov[x] = -1;
    if (l == r) {
      if (op) {
        cnt[x] = 1, sumid[x] = mxid[x] = l;
        sum[x] = a[l];
      } else {
        mxid[x] = mx[x] = -1;
      }
      return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid, op), build(x << 1 | 1, mid + 1, r, op);
    pushup(x);
  }

  void update1(int x, int l, int r, int ql, int v, bool op = 1) {
    if (l == r) {
      if (op) {
        tag[x] = 0, tagcov[x] = -1, cnt[x] = 1, sumid[x] = mxid[x] = l;
        addtag2(x, v);
      } else {
        cnt[x] = sum[x] = sumid[x] = mxid[x] = tag[x] = 0;
        tagcov[x] = mx[x] = -1;
      }
      return;
    }
    pushdown(x);
    int mid = (l + r) >> 1;
    if (ql <= mid)
      update1(x << 1, l, mid, ql, v, op);
    else
      update1(x << 1 | 1, mid + 1, r, ql, v, op);
    pushup(x);
  }

  void update2(int x, int l, int r, int ql, int qr, int v) {
    if (l > qr || r < ql)
      return;
    else if (l >= ql && r <= qr)
      return addtag2(x, v);
    pushdown(x);
    int mid = (l + r) >> 1;
    update2(x << 1, l, mid, ql, qr, v),
        update2(x << 1 | 1, mid + 1, r, ql, qr, v);
    pushup(x);
  }

  int getpos(int x, int l, int r, int v) {
    if (mx[x] < v) return 0;
    if (l == r) return l;
    pushdown(x);
    int mid = (l + r) >> 1;
    if (mx[x << 1] >= v)
      return getpos(x << 1, l, mid, v);
    else
      return getpos(x << 1 | 1, mid + 1, r, v);
  }

  int64_t query(int x, int l, int r, int ql, int qr) {
    if (l > qr || r < ql)
      return 0;
    else if (l >= ql && r <= qr)
      return sum[x];
    pushdown(x);
    int mid = (l + r) >> 1;
    return query(x << 1, l, mid, ql, qr) +
           query(x << 1 | 1, mid + 1, r, ql, qr);
  }

  void print(int x, int l, int r) {
    if (l == r) return void(std::cerr << sum[x] << ' ');
    pushdown(x);
    int mid = (l + r) >> 1;
    print(x << 1, l, mid), print(x << 1 | 1, mid + 1, r);
  }
  void print() {
    print(1, 1, n);
    std::cerr << '\n';
  }
} sgt[2];

void dickdreamer() {
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  int nowcnt = 0;
  for (int i = 1; i <= q; ++i) {
    std::cin >> op[i];
    if (op[i] == 1) {
      std::cin >> v[i];
      chkm.emplace_back(i, nowcnt, v[i]);
    } else if (op[i] == 2) {
      ++nowcnt;
    } else {
      std::cin >> l[i] >> r[i];
    }
  }
  prework();
  sgt[0].build(1, 1, n, 0), sgt[1].build(1, 1, n, 1);
  for (int i = 1; i <= q; ++i) {
    if (op[i] == 1) {
      for (auto x : vv[i]) {
        sgt[0].update1(1, 1, n, x, v[i]);
        sgt[1].update1(1, 1, n, x, 0, 0);
      }
      int p = sgt[0].getpos(1, 1, n, v[i]);
      if (p) sgt[0].update2(1, 1, n, p, n, v[i]);
    } else if (op[i] == 2) {
      sgt[0].addtag1(1, 1), sgt[1].addtag1(1, 1);
    } else {
      std::cout << sgt[0].query(1, 1, n, l[i], r[i]) +
                       sgt[1].query(1, 1, n, l[i], r[i])
                << '\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,return,int,712,kMaxN,stk,2021,UOJ,vec
From: https://www.cnblogs.com/Scarab/p/18352852

相关文章

  • UOJ354 新年的投票
    最近我博客似乎出了点bug,倒是不太会修,将就着看吧。本文主要关注第四个子任务,前面三个有叙述不清的敬请谅解。UOJ354新年的投票Sub1不管人的编号直接爆搜就能够找到一个合法方案。Sub3第\(i\)个人假设自己是第一个\(1\),\(1\simi-1\)的都不能是\(1\),如果自己确实有这......
  • 2021年庐阳区青少年信息学科普日真题- 跳跃(jump)
    题目描述猴子的正上方,每1米处,都有一个桃子,一共有N个桃子,每个桃子都有其能量值,摘下这个桃子吃下就获得了这个能力值。猴子每跳1米会消耗1个点能量,在能量值允许的下,它可以跳到任何一个可以到达的高度,并且将这个高度及以下高度的桃子摘下吃掉。确保猴子初始的能量一定可以摘下......
  • [EC Final 2021] Vision Test
    挺牛题,没做出来,但是参考了Rainbow博客之后发现这些套路自己其实都会啊QwQ。我提交的翻译:给定一个长度为\(n\)的数组\(x\),接下来你有\(q\)次询问。第\(i\)次询问给出一个区间\(l,r\),设\(k=r-l+1\),你提取出\(x\)数组下标在\(l,r\)之间的区间\(y_i=x_{i+l}(0\le......
  • windows平台中使用vscode远程连接linux进行c++开发配置教程(内容详细适合小白)-2021-3-3
    文章目录一、简要介绍二、软件安装步骤1.linux系统安装2.vscode安装3.ssh安装4.配置Remote-SSH5.安装远程插件6.简单小测试三、配置vscode开发环境1.默认设置、用户设置、远程设置和工作区设置2.c++开发设置a).c_cpp_properties.jsonb).tasks.jsonc).launc......
  • Dreamweaver (DW)2021 下载 安装
    将 Dreamweaver2021 压缩包解压到本地:点击蓝色字体下载压缩包提取码ixsu鼠标右键点击 Set-up 选择 以管理员身份运行:点击 更改位置 可以自定义选择安装路径 也可以选择默认位置点击 继续:等待安装正常等待5分钟左右:安装完成点击关闭:双击桌面 Drea......
  • UOJ354 新年的投票
    task3:intn=15;intval[1<<16];inte[1<<16][16];signedmain(){ freopen("vote3.ans","w",stdout); intV=1e8; For(i,0,n-1)e[1<<i][i]=V,e[0][i]=-V,val[1<<i]=V; For(j,1,n-1){ For(s,0,(1<<n)-1) i......
  • ECMAScript 12 (ES12, ES2021) 新特性
    还是大剑师兰特:曾是美国某知名大学计算机专业研究生,现为航空航海领域高级前端工程师;CSDN知名博主,GIS领域优质创作者,深耕openlayers、leaflet、mapbox、cesium,canvas,webgl,echarts等技术开发,欢迎加底部微信(gis-dajianshi),一起交流。No.内容链接1Openlayers【入门教程】-......
  • Luogu7740 [NOI2021]机器人游戏 做题记录
    link一道炸裂的题目。首先样例解释已经告诉我们可以容斥。考虑枚举可行的位置集合\(S\),我们需要统计\(\forallp\inS\),纸条初始状态和目标状态都相同的方案数。显然每个机器人独立,可以分开考虑。对于一个机器人,他的行动对纸条的每个格子要么赋值为\(0/1\),要么不变,要么取......
  • 2021-工业互联网内部预选-Crypto_crackCipher
    Crypto_crackCipher考点:RSA、共模攻击、小明文攻击#题目n:319346705152431353765444947778001678187416808894823574760436641015522638469659027090626875609493629475537497235247214357478969579124921471930436717627582739285578749256377881281252349890970546215813089......
  • 2021年我因为Tab Session Manager丢失数据,好像是研究过一次leveldb的查看/解码方式 但
    Default\LocalStorage\leveldb.ldb 2023年下半年我因为chatmindai修改域名,又研究过一次,因为时间关系也没有细究 最近,我想查看一下anki的devtool的LocalStorage,即https://ankiweb.net/shared/info/31746032这个插件产生的C:\Users\xxx\AppData\Local\Anki\QtWebEngine\De......