题解：P11080 [ROI 2019 Day 1] 拍照

· · 题解

提供一篇做法较为不同的题解。

题意

给定 m 个位置和 n 个颜色，再给出一个操作后的序列。构造一组合法的操作使得一个无色序列能变成这个序列。

思路

考虑到每种颜色只能用一次，所以一种颜色 c 的覆盖区间一定是 [s_c, e_c]，其中 s_c 表示颜色 c 最初出现的位置，e_c 表示颜色 c 最后出现的位置。

那么按照这样划分可以得到若干个区间，不难发现它们要么相离要么包含。

简单证明一下：如果有相交的情况的话那么一个区间一定会覆盖另一个区间的一部分，此时会回到相离的情况。

那么这就好做了，按左端点从小到大排序，查询当前区间之前是否被染过色，再将区间的端点加进颜色段中即可。

区间查询单点修改，BIT 可以胜任。

代码：

for(int i = 1 ; i <= cnt ; ++ i) {
    if(ask(l[i].l, l[i].r)) return cout << -1, 0;

    add(l[i].l, l[i].val), add(l[i].r, l[i].val);

    if(l[i].l == l[i].r) add(l[i].l, -l[i].val);
}

然后你会发现被样例 #2 卡爆了。

看到样例 #2，你发现这个数据十分巧妙的规避了你的构造。

于是在 BIT 加点之后，我们还需要判断这种构造在操作后是否符合给定的序列。

然后你想到是不是可以用 SGT 暴力模拟覆盖操作，但这么想就没有我这个另类的题解了（

发现 BIT 加点后的值总是成对存在的，很像一个括号序列。

于是就可以用栈维护，比 SGT 好写得多，常数更小得多。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e5 + 5;
int n, m, cnt, a[N], T[N], s[N], e[N];
struct Node {
    int l, r, val;
    Node(int ll = 0, int rr = 0, int vval = 0) {
        l = ll, r = rr, val = vval;
    }
} l[N];
stack<int> S;

inline bool cmp(Node a, Node b) {
    return a.l < b.l;
}

namespace BIT {
    int t[N];

    inline int lowbit(int x) {
        return x & -x;
    }

    inline void add(int x, int k) {
        for( ; x <= m ; x += lowbit(x))
            t[x] += k;

        return ;
    }

    inline int query(int x) {
        int res = 0;

        for( ; x ; x -= lowbit(x))
            res += t[x];

        return res;
    }

    inline int ask(int l, int r) {
        return query(r) - query(l - 1);
    }
}

using namespace BIT;

signed main() {
    freopen("1180.in", "r", stdin);
    freopen("1180.out", "w", stdout);

    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> m >> n;
    for(int i = 1 ; i <= m ; ++ i)
        cin >> a[i];

    for(int i = 1 ; i <= m ; ++ i) {
        if(! s[a[i]]) s[a[i]] = i;

        e[a[i]] = i;
    }

    for(int i = 1 ; i <= n ; ++ i)
        if(s[i] && e[i]) l[++ cnt] = Node(s[i], e[i],1 i);

    sort(l + 1, l + 1 + cnt, cmp);

    for(int i = 1 ; i <= cnt ; ++ i) {
        if(ask(l[i].l, l[i].r)) return cout << -1, 0;

        add(l[i].l, l[i].val), add(l[i].r, l[i].val);

        if(l[i].l == l[i].r) add(l[i].l, -l[i].val);
    }

    for(int i = 1 ; i <= m ; ++ i)
        T[i] = ask(i, i);

    for(int i = 1 ; i <= m ; ++ i) {
        if(! S.empty() && T[i] == S.top()) S.pop();
        else if(T[i]) {
            if(e[T[i]] - s[T[i]]) S.push(T[i]);

        }
        else if(! S.empty() && a[i] != S.top()) return cout << -1, 0;
    }

    cout << cnt << '\n';

    for(int i = 1 ; i <= cnt ; ++ i)
        cout << l[i].val << ' ' << l[i].l << ' ' << l[i].r << '\n';

    return 0;
}