社区讨论
都说第10个点怎么都过,我咋就是第10个点过不了
P4093[HEOI2016/TJOI2016] 序列参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo20guom
- 此快照首次捕获于
- 2023/10/23 05:59 2 年前
- 此快照最后确认于
- 2023/11/03 06:22 2 年前
没写cdq分治,写了个线段树维护最大值,考虑其实就是要求选的位置后面的最小值大于等于前面的最大值,权值线段树维护最大值为i最长是多少,然后每次用最小值去查询,不知道为啥最后一个点WA了qwq
CPP#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, rt, tot;
int mx[maxn], mn[maxn];
int ls[maxn << 4], rs[maxn << 4], val[maxn << 4];
void modify (int &k, int l, int r, int p, int v)
{
if (!k) k = ++tot;
if (l == r) return val[k] = max(val[k], v), void();
int md = (l + r) >> 1;
if (p <= md) modify(ls[k], l, md, p, v);
else modify(rs[k], md + 1, r, p, v);
val[k] = max(val[ls[k]], val[rs[k]]);
}
int query (int &k, int l, int r, int p)
{
if (!k) return 0;
if (p >= r) return val[k];
int md = (l + r) >> 1;
int res = query(ls[k], l, md, p);
if (p > md) res = max(res, query(rs[k], md + 1, r, p));
return res;
}
int main ()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &mx[i]), mn[i] = mx[i];
int lim = 1e5 + 10;
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
mx[x] = max(mx[x], y);
mn[x] = min(mn[x], y);
}
for (int i = 1; i <= n; ++i) {
int len = query(rt, 1, lim, mn[i]) + 1;
modify(rt, 1, lim, mx[i], len);
}
printf("%d\n", val[rt]);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...