E - Paint

我都见到这题三次了。

考虑正难则反，操作逆序。

此时你先涂的颜色后面不能更改了。

但是显然的你可以知道现在有多少行多少列被涂过了。

那么你把剩下的加进答案就好了。

然后这题有个很逆天的 corner case 是一开始全是颜色 $0$。如果这个 corner case 判错了也会寄的。

typedef long long ll;
int h, w, q;
struct Query
{
    int op, data, col;
} Q[200020];
ll cnt[200020];
int r, c;
bool R[200020];
bool C[200020];
set<int> s;
ll sum;
int main()
{
    read(h, w, q);
    r = h, c = w;
    sum = 1LL * h * w;
    for (int i = 1; i <= q; i++)
        read(Q[i].op, Q[i].data, Q[i].col);
    reverse(Q + 1, Q + q + 1);
    s.insert(0);
    for (int i = 1; i <= q; i++)
    {
        auto [op, d, col] = Q[i];
        if (op & 1) // coloring row
        {
            if (R[d] || !c)
                continue;
            R[d] = 1;
            cnt[col] += c;
            if (col)
                sum -= c;
            r--;
            s.insert(col);
        }
        else
        {
            if (C[d] || !r)
                continue;
            C[d] = 1;
            cnt[col] += r;
            if (col)
                sum -= r;
            c--;
            s.insert(col);
        }
    }
    if (!sum)
        s.erase(0);
    cout << s.size() << endl;
    for (int i : s)
        cout << i << " " << (!i ? sum : cnt[i]) << '\n';
    return 0;
}

F - SSttrriinngg in StringString

首先，最大化答案，一眼二分答案。

然后考虑 check。这个 check 我只能说是大家都会口胡吧。

你就考虑你现在指针跑到哪里了，已经过了几轮。整轮能跳的显然要 $\mathcal O(1)$ 维护过了几轮。

然后不满一轮的判断也是很简单的，但是要注意不满一轮也可能要新开一轮的。这个大家实现的时候自己对着样例调一下就行。

另外如果样例 3 挂了调不出来可以拍一下 $N=5,|S|,|T|\leq 5,\alpha \leq 3$ 的点，其中 $\alpha$ 表示字符集大小。其实不需要几组就能拍出小 hack 的，我拍了一个小数据很快就调过去了。

typedef long long ll;
typedef __int128 LL;
int n, m;
ll k;
string s, t;
int pre[26][100020];
int pos[26][100020];
bool check(ll x)
{
    int p = 0;
    ll round = 1;
    for (int i = 1; i <= m; i++)
    {
        if (round > k)
            return 0;
        char c = t[i];
        ll need = x;
        if (pre[c - 'a'][n] - pre[c - 'a'][p] >= need)
        {
            int preHave = pre[c - 'a'][p];
            int newPos = pos[c - 'a'][preHave + need];
            p = newPos;
            continue;
        }
        need -= pre[c - 'a'][n] - pre[c - 'a'][p];
        ll can_per_round = pre[c - 'a'][n];
        if (!can_per_round)
            return !need && round <= k;
        ll need_round = need / can_per_round;
        round += need_round;
        need -= can_per_round * need_round;
        if (need)
            round++, p = pos[c - 'a'][need];
        else
            p = pos[c - 'a'][can_per_round];
    }
    return round <= k;
}
int main()
{
    cin >> k >> s >> t;
    n = s.size(), m = t.size();
    s = ' ' + s, t = ' ' + t;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 26; j++)
            pre[j][i] = pre[j][i - 1];
        pos[s[i] - 'a'][++pre[s[i] - 'a'][i]] = i;
    }
    ll L = 0, R = 1e18, ans = 0;
    while (L <= R)
    {
        ll mid = L + R >> 1;
        if (check(mid))
            L = (ans = mid) + 1;
        else
            R = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

另外这题根据实现的不同可能有的方法会炸 long long，自己注意一下。但是我的写法是不会的。~~尽管我写了个 typedef。~~

G - Alone

考虑到你的序列长 $[\tt T,{\color{red}{x}},T,T,T,{\color{red}{x}},T,T,T,T,{\color{red}{x}},T,T,T,{\color{red}{x}},T,T,T]$ 这样子。

其中 $\tt\color{red}x$ 表示某个颜色相同的数，$\tt T$ 表示其他数。

那么你对于 $[\tt T_1,T_2,T_3,{\color{red}{x_4}},T_5,T_6,T_7]$ 这样的一个序列（下标表示在序列中的位置），你如果想要得到一组合法的 $[L,R]$ 就需要满足 $L\in [1,3],R\in [5,7]$，也就是要分布在这个 $x$ 的两侧。

但是这个会导致计算重复的 $[L,R]$。不是很好处理。

考虑把数对 $(L,R)$ 映射到平面直角坐标系上，$x$ 轴表示左端点，$y$ 轴表示右端点，那么你的每个 $(L,R)$ 都会成为平面上第一象限的一个点。

而你的 $L$ 和 $R$ 都是有取值范围的，每个 $x$ 贡献的所有 $L$ 和 $R$ 对应点会组成一个矩形。若干个 $x$ 就组成若干矩形，但是有交。

那么题目就变成了平面直角坐标系中若干矩形求面积并，这是扫描线板子。

int n, w, h;
struct Seg
{
    int x, yd, yu, c;
};
vector<Seg> a;
vector<int> v;
struct SegTree
{
    struct node
    {
        int len, lzy;
    } t[200020 << 2];
#define ls id << 1
#define rs id << 1 | 1
    void push_up(int id, int l, int r) { t[id].len = (t[id].lzy ? v[r] - v[l - 1] : (l == r ? 0 : t[ls].len + t[rs].len)); }
    void build(int id = 1, int l = 1, int r = n)
    {
        if (l == r)
            return t[id].len = t[id].lzy = 0, void();
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
    }
    void add(int ql, int qr, int k, int id = 1, int l = 1, int r = n)
    {
        if (r < ql || l > qr)
            return;
        if (ql <= l && r <= qr)
            return t[id].lzy += k, push_up(id, l, r);
        int mid = l + r >> 1;
        add(ql, qr, k, ls, l, mid);
        add(ql, qr, k, rs, mid + 1, r);
        push_up(id, l, r);
    }
} T;
int Q(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }
int arr[200020];
void add(int xl, int yd, int xr, int yu)
{
    if (xl > xr || yd > yu)
        return;
    v.push_back(yd), v.push_back(yu);
    a.push_back({xl, yd, yu, 1});
    a.push_back({xr, yd, yu, -1});
}
vector<int> col[200020];
int main()
{
    read(n);
    for (int i = 1; i <= n; i++)
        col[i].push_back(0);
    for (int i = 1; i <= n; i++)
        read(arr[i]), col[arr[i]].push_back(i);
    for (int i = 1; i <= n; i++)
        col[i].push_back(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j + 1 < col[i].size(); j++)
            add(col[i][j - 1] + 1, col[i][j] - 1, col[i][j] + 1, col[i][j + 1] - 1);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    sort(a.begin(), a.end(), [&](Seg a, Seg b)
         { return a.x ^ b.x ? a.x < b.x : a.c > b.c; });
    n = v.size() - 1;
    T.build();
    ll ans = 0;
    for (int i = 0; i + 1 < a.size(); i++)
    {
        auto [x, yd, yu, c] = a[i];
        T.add(Q(yd), Q(yu) - 1, c);
        ans += 1LL * T.t[1].len * (a[i + 1].x - x);
    }
    cout << ans << '\n';
    return 0;
}

ABC346 EFG 简单题解