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

题解:CF1548E Gregor and the Two Painters

很好的题!

题意:给出每行权值 \(a_i\),每列权值 \(b_j\),定义点 \((i,j)\) 权值为 \(a_i+b_j\),问权值 \(\le x\) 的点组成的连通块个数。

做法:

这个题需要用到一个数连通块的技巧,我们对于每个连通块钦定一个代表元,那么我们就只用数有多少个代表元就可以了。这个题中,我们令连通块中权值最小且尽量靠左,如果相同靠左那么就靠上,这样的点为代表元。

那么考虑一个点 \((i,j)\) 如何才能成为代表元,首先要求他肯定权值要 \(\le x\),其次我们考虑 \(la_i,ra_i\),分别代表 \(a\) 序列 \(i\) 前面第一个小于等于 \(a_i\) 的位置,\(ra_i\) 是后面第一个小于的位置,类似定义 \(lb_i,rb_i\),那么为了让 \((i,j)\) 走不到 \((la_i,j),(ra_i,j),(i,lb_j),(i,rb_j)\)。可能你会疑惑为什么只需要这四个点,手完一下发现 \(x\in[la_i+1,ra_i-1],y\in[lb_i+1,rb_i-1]\) 这样的点一定不会比 \((i,j)\) 优,而这四个点是比 \((i,j)\) 优且最容易得到的。

\((la_i,j)\) 举例,我们就得要求 \(mxla = \max\limits_{t=la_i}^ia_t+b_j>x\),否则就越过去了,同理写出来四个限制,当然对于 \(a,b\) 的两个限制完全可以合在一起,这样就只有两个限制,即假设 \(va_i = \min(\max\limits_{t=la_i}^ia_t,\max\limits_{t=i}^{ra_i}a_t)\)\(vb_j\) 类似定义,那么就要求:

\[a_i+b_j\le x,a_i+vb_j>x,va_i+b_j>x \]

\(j\) 相关的全部扔到右边去,然后就是一个二位偏序,复杂度 \(O(n\log n)\)

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 5, inf = 2e9;
int n, m, x, a[maxn], b[maxn], nw;
int st[maxn][21], lg[maxn];
void init(int v[], int n) {for (int i = 1; i <= n; i++)st[i][0] = v[i];for (int j = 1; (1 << j) <= n; j++)for (int i = 1; i + (1 << j) - 1 <= n; i++)st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);lg[0] = -1;for (int i = 1; i <= n; i++)lg[i] = lg[i >> 1] + 1;
}
int query(int l, int r) {if(l == 0 || r == nw + 1)return inf;int k = lg[r - l + 1];return max(st[l][k], st[r - (1 << k) + 1][k]);
}
struct node {int x, y, id;friend bool operator<(node x, node y) {return (x.x != y.x ? x.x > y.x : x.id > y.id);}
} t[maxn];
int stk[maxn], l[maxn], r[maxn], top, tot;
void solve1() {top = 0;nw = n;stk[0] = 0;for (int i = 1; i <= n; i++) {while(top && a[stk[top]] > a[i])top--;l[i] = stk[top];stk[++top] = i;}top = 0;stk[0] = n + 1;for (int i = n; i >= 1; i--) {while(top && a[stk[top]] >= a[i])top--;r[i] = stk[top];stk[++top] = i;}for (int i = 1; i <= n; i++) {int val = min(query(l[i], i), query(i, r[i]));//	cout << i << " " << val << " " << r[i] << endl;t[++tot] = {val, a[i], 0};}
}
void solve2() {stk[0] = 0;nw = m;top = 0;for (int i = 1; i <= m; i++) {while(top && b[stk[top]] > b[i])top--;l[i] = stk[top];stk[++top] = i;}top = 0;stk[0] = m + 1;for (int i = m; i >= 1; i--) {while(top && b[stk[top]] >= b[i])top--;r[i] = stk[top];stk[++top] = i;}for (int i = 1; i <= m; i++) {int val = min(query(l[i], i), query(i, r[i]));//	cout << i << " " << val << " " << l[i] << " " << r[i] << " " << query(i, r[i]) << endl;t[++tot] = {x - b[i], x - val, 1};}
}
#define lowbit(x) (x & (-x))
struct Tree_array {int tr[maxn], n;void add(int x, int val) {while(x <= n)tr[x] += val, x += lowbit(x);}int query(int x) {int ans = 0;while(x > 0)ans += tr[x], x -= lowbit(x);return ans;}int queryseg(int l, int r) {return query(r) - query(l - 1);}
} tree;
int ans = 0;
void solve() {tree.n = x;sort(t + 1, t + tot + 1);for (int i = 1; i <= tot; i++) {//	cout << t[i].x << " " << t[i].y << " " << t[i].id << endl;if(t[i].id == 1)ans += tree.queryseg(t[i].y + 1, t[i].x);elsetree.add(t[i].y, 1);}
}
signed main() {cin >> n >> m >> x;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= m; i++)cin >> b[i];init(a, n);solve1();init(b, m);solve2();solve();cout << ans << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=20717

相关文章:

  • Gitee DevOps:重塑中国软件开发效率的新范式
  • Gitee:中国开发者生态的崛起与数字化转型新动能
  • 悟空博弈框架深度研究:从技术架构到商业应用的全景分析——声明ai研究
  • 油猴脚本-自动刷新网页
  • PostgreSQL数据库查询表是否被锁,以及解锁表的办法
  • 用信号量机制实现互斥,同步,前驱
  • 详细介绍:HDFS和MapReduce——Hadoop的两大核心技
  • 【AI 哲学思考】从大模型演进到生命隐喻:个性、极限与先天后天之问
  • 【AI 哲学思考】记忆的形态:从人脑到 AI 的存储之问
  • ISP DMA TEST
  • 三脚电感在报警器芯片里的实际作用与用法
  • 洛谷题单指南-进阶数论-P5091 【模板】扩展欧拉定理
  • jenkins maven nacos springboot profile实现多环境配置
  • RAG is really dead? 大模型和知识之间的桥梁没了? - spader
  • opencv学习记录4
  • 深入解析:Java-136 深入浅出 MySQL Spring Boot @Transactional 使用指南:事务传播、隔离级别与异常回滚策略
  • .NET操作Excel:高效材料读写与批量运行
  • Qwen-Image技术报告
  • IOS-和安卓-AR-游戏开发指南-全-
  • Winform/C# 输出到Release VS中Release模式下生成去掉生成pdb文件
  • 【OpenCV】12 图像轮廓
  • IntroJS-即时入门-全-
  • 数字设计的新篇章:前沿技术与未来趋势
  • 2025 镀锌方管厂家最新权威推荐排行榜:聚焦行业标杆与新锐品牌,镀锌方管优质厂家深度解析
  • mysql启动方式导致链接数max_connections查询的值不一致
  • cmakelist
  • 供应商协同平台:打造高效安全供应链的关键
  • 互斥锁和信号量机制
  • NSIS为当前用户安装和为所有用户安装的选择
  • 数据中台厂商选型|解决方案厂商与独立中台厂商详细解读