ICPC小米邀请赛E题 Phone Network 线段树上二分+线段树优化DP

ACM算法日常

发布于 2020-12-15 09:48:43

4020

发布于 2020-12-15 09:48:43

文章被收录于专栏：ACM算法日常

题意

题目链接：见原文链接

有一个长度为

的序列，每个点权值为在范围

[1,m]

内，保证每个值都出现过。对每个

i(1\le i\le m)

询问包含权值

[1,i]

的区间最小长度。

1\le 1\le m\le n\le 200000

思路

咋一看这个题可能完全没有思路，这么多询问怎么写呢？其实不然，我们先想一个暴力的

解法。

暴力

O(n^2)

的写法：

dp[i][j]

表示以

为左端点的区间包含权值

[1,j]

的最小右端点。

先从小到大枚举

，然后枚举

每依次出现的位置，状态转移就是：

记在第

个位置右边最近的

出现的位置为

lasJ

：

dp[i][j]=max(dp[i][j-1],lasJ)

;

右边没有

的赋值为无穷大：

dp[i][j]=INF

考虑用线段树维护

的状态转移：

还是从小到大枚举

，然后更新

个点的

值。线段树每个节点维护两个值：

sum[rt]

代表在线段树中

节点子树内

dp[i][j]

的最大值，

ans[rt]

表示子树内的答案即

(dp[i][j]-i+1)

的最小值。

一个显然的性质：对于任何

1\le a\le b\le n

满足

dp[a][j]\le dp[b][j]

，即

dp[i][j]

有一个单调性。对于某一段区间的更新是区间

sum[rt]

与

lasJ

取最大值的操作。因为

dp[i][j]

具有单调性，显然需要更新的是一段前缀，当然也可以先二分出右端点再区间覆盖。

但是线段树本来就是一个二分的结构，在线段树执行update函数的时候，左子树区间一定会向下走的，只有当左儿子区间的最大值小于需要更新的val时才会更新右儿子

来更新区间

sum[rt]

，这样复杂度少一个

log

。当

sum[rt]

被更新时，

ans[rt]

复制为

sum[rt] - r + 1

即可，因为最小值肯定在右端点取嘛。

时间复杂度：

O(nlog(n))

空间复杂度：

O(\alpha *n)

over!

AC代码

#include <bits/stdc++.h>
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MXN = 2e5 + 5;
int n, m;
int ar[MXN], sum[MXN<<2], sumfg[MXN<<2], ans[MXN<<2];
vector<int> num[MXN];
void push_up(int rt) {
    sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
    ans[rt] = min(ans[rt << 1], ans[rt << 1 | 1]);
}
void push_down(int rt, int l, int mid, int r) {
    if(sumfg[rt] == 0) return;
    sumfg[rt << 1] = max(sumfg[rt << 1], sumfg[rt]);
    sumfg[rt << 1 | 1] = max(sumfg[rt << 1 | 1], sumfg[rt]);
    if(sum[rt << 1] < sumfg[rt]) {
        ans[rt << 1] = sumfg[rt] - mid + 1;
        sum[rt << 1] = sumfg[rt];
    }
    if(sum[rt << 1 | 1] < sumfg[rt]) {
        ans[rt << 1 | 1] = sumfg[rt] - r + 1;
        sum[rt << 1 | 1] = sumfg[rt];
    }
    sumfg[rt] = 0;
}
void update(int L, int R, int v, int l, int r, int rt) {
    if(sum[rt] < v && L <= l && r <= R) {
        ans[rt] = v - r + 1;
        sum[rt] = v;
        sumfg[rt] = max(sumfg[rt], v);
        return;
    }
    if(l == r) return;
    int mid = (l + r) >> 1;
    push_down(rt, l, mid, r);
    if(L > mid) update(L, R, v, mid + 1, r, rt << 1 | 1);
    else if(R <= mid) update(L, R, v, l, mid, rt << 1);
    else {
        if(sum[rt << 1] < v) update(mid + 1, R, v, mid + 1, r, rt << 1 | 1);
        update(L, mid, v, l, mid, rt << 1);
    }
    push_up(rt);
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m;
    rep(i, 0, m + 1) num[i].eb(0);
    rep(i, 1, n + 1) {
        cin >> ar[i];
        num[ar[i]].eb(i);
    }
    rep(qj, 1, m + 1) {
        rep(j, 1, SZ(num[qj])) {
            int l = num[qj][j-1], r = num[qj][j];
            update(l + 1, r, num[qj][j], 1, n, 1);
        }
        if(num[qj].back() + 1 <= n) {
            update(num[qj].back() + 1, n, INF, 1, n, 1);
        }
        printf("%d%c", ans[1], " \n"[qj == m]);
    }
    return 0;
}

暴力O(n^2)算法

#include <bits/stdc++.h>
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
const int INF = 0x3f3f3f3f;
const int MXN = 2e4 + 5;
int n, m;
int ar[MXN], dp[MXN][MXN];
vector<int> num[MXN];
int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m;
    rep(i, 0, m + 1) num[i].eb(0);
    rep(i, 1, n + 1) {
        cin >> ar[i];
        num[ar[i]].eb(i);
    }
    rep(qj, 1, m + 1) {
     int ans = INF;
        rep(j, 1, SZ(num[qj])) {
            int l = num[qj][j-1], r = num[qj][j];
            rep(i, l + 1, r + 1) {
             dp[i][qj] = max(dp[i][qj - 1], r);
    ans = min(ans, dp[i][qj] - i + 1);
   }
        }
        rep(i, num[qj].back() + 1, n + 1) {
            dp[i][qj] = INF;
        }
        printf("%d%c", ans, " \n"[qj == m]);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-28，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度