某岛

… : "…アッカリ~ン . .. . " .. .
March 23, 2020

Codeforces Global Round 7

E

哇,这个 rmq 还是有点巧妙的。。。

给定一个排列 P,排列的某些位置放有炸弹。我们按照顺序把排列 P 的元素插入集合,如果当前插入的位置有炸弹,就在插入之后删除集合中最大的元素。
对于一组炸弹分布情况,它的得分是集合中最后剩下来最大的元素(如果不是所有位置都有炸弹的话)。现在给定另一个排列 Q,对于每一个 i,输出当炸弹分布为 Q[0..i-1] 时的得分。
显然结果单调递减。没有炸弹的时候答案肯定是 n,然后我们观察第一个不是 n 的解出现在哪里,这个只要找到第一个把 n 炸掉的炸弹即可,似乎可以用 rmq 来统计。
但是我们发现随着时间的推进,由于后面的炸弹在序列中更靠前的位置插入,前面的炸弹影响的位置可能会变。

进一步思考,我们把增加炸弹看成攻击,减小答案看成防御(增加挡板,有了更多的缓冲),
当前状态不合法,当且仅当对于所有位置,它的防御值(右边的挡板)都不多于它的攻击值(右边的炸弹)。
这个时候所有的挡板都被炸毁,我们需要放宽限制,以增加更多的挡板。于是就变成了一个支持前缀加减,以及全局询问最值的 rmq 问题。
(啊。。这个类比。。不禁让我想起了 CF #87 的 E 题

const int N = int(3e5) + 9;

int P[N], Q[N], pos[N], n;

namespace SGT{
#define lx (x<<1)
#define rx (lx|1)
#define ml (l+r>>1)
#define mr (ml+1)
#define lc lx, l, ml
#define rc rx, mr, r
#define root 1, 1, n

    int T[N*4], D[N*4];
    int a, b, d;

    void upd(int x) {
        T[x] = max(T[lx], T[rx]);
    }

    void add(int x, int d) {
        T[x] += d; D[x] += d;
    }

    void rls(int x) {
        if (D[x]) {
            add(lx, D[x]); add(rx, D[x]);
            D[x] = 0;
        }
    }

    void Modify(int x, int l, int r){
        if (r < a || b < l) return;
        if (a <= l && r <= b){
            add(x, d);
        } else {
            rls(x);
            Modify(lc); Modify(rc);
            upd(x);
        }
    }
} using namespace SGT;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
   // freopen("out.txt", "w", stdout);
#endif

    while (~scanf("%d", &n)) {
        REP_1(i, n) pos[RD(P[i])] = i;
        REP_1(i, n) RD(Q[i]);

        RST(T); RST(D);

        int z = n; a = 1; b = pos[n]; d = 1; Modify(root);

        REP_1(i, n-1) {
            printf("%d ", z);
            a = 1; b = Q[i]; d = -1; Modify(root);

            while (T[1] <= 0) {
                a = 1; b = pos[--z]; d = 1; Modify(root);
            }
        }
        printf("%d\n", z);
    }
}

F

暴力 DP 的话在 TSP 的基础上再状压一维,记录路径的 01 值。
但是这样就要压两个集合,你甚至开不下那么大的数组,(小数据范围就 MLE 了)。
一个简单易懂的时间换空间策略是 DP 一半,然后拼起来。事实上我猜测小数据就是这么过的。

虽然,比赛时我 死活卡不过去。。。由于我的代码实在很优雅,我一直没能放弃这个思路推倒重来!。。。
(后来看一下 Tourist 的代码,先再外面枚举了一下左边的一半子集,就轻轻松松的卡过去了啊!! Orz)。

考虑更优的解法。继续看 Tourist 的代码。我们略微修改状态的定义,现在 1 表示联通,而 0 表示可联通可不联通,那么显然我们最后可以容斥得到原问题的解。
关键是,通过这样修改状态的定义之后,我们发现 dp[s] 的值,只和 s 的划分有关!!这样就可以搜索划分就可以了。实现是需要用各种位运算的技巧优化常数。