社区讨论

都说第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 条回复,欢迎继续交流。

正在加载回复...