当前位置: 首页 > news >正文

商标自助查询系统官网/安卓手机优化软件排名

商标自助查询系统官网,安卓手机优化软件排名,做网站建设的一般在哪儿找,深圳企业推广网站排名目录 题目算法标签: 并查集区间染色, 线段树剪枝, 线段树延迟标记思路并查集区间染色代码线段树倒着推代码线段树正着推代码*警示后人 题目 3115. 疯狂的馒头 算法标签: 并查集区间染色, 线段树剪枝, 线段树延迟标记 思路 因为每个馒头的颜色取决于最后的染色情况, 因此可以…

题目

3115. 疯狂的馒头

算法标签: 并查集区间染色, 线段树剪枝, 线段树延迟标记

思路

因为每个馒头的颜色取决于最后的染色情况, 因此可以倒序向前进行染色每次将区间染为 i i i

并查集区间染色代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1e6 + 10, M = 1e7 + 10;int n, m, p, q;
int fa[N], ans[N];int find(int x) {if (fa[x] != x) fa[x] = find(fa[x]);return fa[x];
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> p >> q;for (int i = 0; i <= n + 1; ++i) fa[i] = i;for (int i = m; i >= 1; --i) {int u = (i * p + q) % n + 1;int v = (i * q + p) % n + 1;int l = min(u, v), r = max(u, v);int idx = find(l);while (idx <= r) {ans[idx] = i;fa[idx] = find(idx + 1);idx = find(idx);}}for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";return 0;
}

线段树倒着推代码

因为倒着推, 线段树只需要记录当前区间颜色即可, 因为是从后向前推, 因此当遇到当前区间已经被染色, 直接返回,. 也就是剪枝操作, 线段树模拟, 时间复杂度 O ( m log ⁡ n ) O(m\log n) O(mlogn), 在超时的边缘, 但是因为有剪枝, 可以 通过

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1e6 + 10;int n, m, p, q;
struct Node {int l, r, val;
} tr[N << 2];void push_up(int u) {if (tr[u << 1].val && tr[u << 1 | 1].val) tr[u].val = true;
}void build(int u, int l, int r) {tr[u] = {l, r, 0};if (l == r) return;int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);
}void modify(int u, int l, int r, int v) {if (tr[u].val) return;if (tr[u].l == tr[u].r) tr[u].val = v;else {int mid = tr[u].l + tr[u].r >> 1;if (l <= mid) modify(u << 1, l, r, v);if (r > mid) modify(u << 1 | 1, l, r, v);push_up(u);}
}void query(int u) {if (tr[u].l == tr[u].r) {cout << tr[u].val << "\n";return;}query(u << 1);query(u << 1 | 1);
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> p >> q;build(1, 1, n);for (int i = m; i >= 1; --i) {int u = (i * p + q) % n + 1;int v = (i * q + p) % n + 1;if (u > v) swap(u, v);modify(1, u, v, i);}query(1);return 0;
}

线段树正着推代码

因为正着推涉及到区间修改, 因此需要维护一个延迟标记, 常数会更大一些, 无法通过, 但是逻辑是正确的

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1e6 + 10;int n, m, p, q;
struct Node {int l, r, val, flag;
} tr[N << 2];void push_up(int u) {if (tr[u << 1].val == tr[u << 1 | 1].val) tr[u].val = tr[u << 1].val;else tr[u].val = -1;
}void push_down(int u) {if (tr[u].flag) {Node &ls = tr[u << 1], &rs = tr[u << 1 | 1];ls.val = tr[u].flag;ls.flag = tr[u].flag;rs.val = tr[u].flag;rs.flag = tr[u].flag;tr[u].flag = 0;}
}void build(int u, int l, int r) {tr[u] = {l, r, 0};if (l == r) return;int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);push_up(u);
}void modify(int u, int ql, int qr, int val) {if (tr[u].l >= ql && tr[u].r <= qr) {tr[u].val = val;tr[u].flag = val;return;}push_down(u);int mid = tr[u].l + tr[u].r >> 1;if (ql <= mid) modify(u << 1, ql, qr, val);if (qr > mid) modify(u << 1 | 1, ql, qr, val);push_up(u);
}int query(int u, int k) {if (k >= tr[u].l && k <= tr[u].r && tr[u].val != -1) return tr[u].val;int mid = tr[u].l + tr[u].r >> 1;push_down(u);if (k <= mid) return query(u << 1, k);return query(u << 1 | 1, k);
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m >> p >> q;build(1, 1, n);for (int i = 1; i <= m; ++i) {int u = (i * p + q) % n + 1;int v = (i * q + p) % n + 1;if (u > v) swap(u, v);modify(1, u, v, i);}for (int i = 1; i <= n; ++i) {int ans = query(1, i);cout << ans << "\n";}return 0;
}

*警示后人

如果线段树不是带有延迟标记的, 那么如果进行修改只能修改到点上, 如果是带有延迟标记的可以进行区间修改

http://www.lryc.cn/news/577598.html

相关文章:

  • 闵行营销型网站建设公司/友情链接的作用有哪些
  • 生猪价格今日猪价最新走势图/aso优化哪家好
  • 怎样购买起名软件自己做网站/友情链接样式
  • 石家庄大的网站开发公司/哈尔滨最新消息
  • 外网有哪些有趣的网站/抚顺网站建设
  • 重庆网站建设公司多少钱/站长之家站长工具
  • 一起做业网站/百度移动点击排名软件
  • 什么是二级网站推广/网站如何宣传推广
  • 网络广告视频/网站推广优化平台
  • 个体户可以备案网站吗/百度 seo优化作用
  • 站长要维护网站/seo网络推广有哪些
  • 河南网站优化要多少钱/营销方式有哪几种
  • 黄石做网站要多少钱/windows优化大师可以卸载吗
  • 网站图标可以用ps 做吗/百度问问首页
  • 成都市城乡建设委员会官方网站/360广告推广平台
  • 东莞知名网站建设/网站推广的6个方法是什么
  • reactjs 做的网站/短视频seo代理
  • 网站维护托管公司/营销软文300字
  • 中宁网站建设公司/营销型网站建设套餐
  • 手表 网站策划/网络营销的方法是什么
  • 旅游网站建设的概念/下载谷歌浏览器并安装
  • 电脑系统做的好的网站好/百度云搜索引擎入口
  • 如何做网站的seo/石家庄seo外包的公司
  • 珠宝类网站建设可执行报告/搜索引擎优化的主题
  • 网站划分栏目/郑州手机网站建设
  • 资源网站模板/百度账号客服
  • 云南建设监理协会网站/谷歌浏览器安卓版
  • 网站建设大赛策划书/海阳seo排名优化培训
  • 帮人做钓鱼网站/如何在各大网站发布信息
  • 网站更换服务器 备案/泉州seo按天收费