CF2096 题解

CF2096C Wonderful City

给你一个 \(n\times n\) 的矩阵 \(h\)，你可以花费 \(a_i\) 的代价将第 \(i\) 行的所有数字增加 \(1\)，或者花费 \(b_j\) 的代价将第 \(j\) 列的所有数字增加 \(1\)，使得最后矩阵中不存在两个四联通相邻的数字相等。一行或一列最多操作一次。问最小代价。

\(n\le 1000\)

我开始想错了，越转化问题越强，然后根本做不了。

设 \(x_i\) 表示第 \(i\) 行是否操作，\(y_i\) 同理，取值 \(\{0,1\}\)。每相邻两个数都会给它们所在的相邻两行/两列提供 0~1 个限制，形如 \(x_i\ne x_{i+1}\) 或者 \(x_i\le x_{i+1}\)，\(x_i\ge x_{i+1}\) 等。不难发现行和列是独立的。

然后分别对行和列进行 dp 即可。时间复杂度 \(O(nm)\)，瓶颈在于找到限制。

CF2096D Wonderful Lightbulbs

在平面直角坐标系的每一个整点上都有一个灯泡。初始时，有且仅有一个灯泡是点亮的。每次操作，你选择一个位置 \((x,y)\)，然后将 \((x,y),(x,y+1),(x+1,y),(x+1,y-1)\) flip。

给定最终局面（\(n\) 个点亮的点），问哪个灯泡是初始点亮的。保证有解。

\(n\le 2\times 10^5\)，给定的点的坐标的绝对值 \(\le 10^8\)

首先题目给定的形状非常不规则。但是发现可以通过对坐标系的变换 \((x,y)\to (x,x+y)\) 使得其变为 \(2\times 2\) 的正方形。

由于值域很大，不难构造出一种操作次数 \(10^{13}\) 量级的最终局面，因此不能尝试构造方案。虽然但是，操作可以简化为对任意一个 \(2\times 2\) 的子矩阵（任选两行两列相交得到的 \(4\) 个点）进行操作，也不知道后面能不能做。

考察每次操作哪些量是不变的。注意到每行点数的奇偶性和每列点数的奇偶性不会改变。因此找出和为奇数的行以及和为奇数的列即可。

CF2096E Wonderful Teddy Bears

给定一个长为 \(n\) 的 01 串 \(s\)。每次你可以选择 \(s\) 一个长为 \(3\) 的连续子段，然后将其排序。问将整个串排好序的最少操作次数。

\(n\le 2\times 10^5\)

操作分为 \(4\) 种：

可以用逆序对来衡量数组的排序程度。注意到 \(1,2\) 可以减少两个逆序对，而 \(3,4\) 只能减少一个。我们希望最大化 \(1,2\) 操作的次数。

注意到 \(1,2\) 操作本质是交换了间隔一个数的两个数字，而 \(3,4\) 操作是交换了相邻两个数字。考察操作本质上改变了什么、没改变什么。由于 \(1,2\) 操作总是在对奇偶性相同的两个格子进行操作，因此不会改变奇（偶）格子内 \(1\) 或 \(0\) 的数量。相反，\(3,4\) 操作一定会改变。

由于我们知道最终局面，因此也知道最终的时候奇数下标有多少个 \(0\)。由此我们能够算出 \(3,4\) 操作最少执行多少次，剩下的逆序对都靠 \(1,2\) 处理即可。

CF2096F Wonderful Impostors

有一个长为 \(n\) 的 01 串 \(s\) 和 \(m\) 条命题，每条命题形如“区间 \([l,r]\) 全都是 \(0\)”或“区间 \([l,r]\) 存在一个 \(1\)”。

有 \(q\) 次询问，每次询问给定一个区间 \([l,r]\)，问编号在 \([l,r]\) 的命题是否能同时满足。

\(n,m,q\le 2\times 10^5\)

只有一次询问的判定问题是好做的。将所有第一种命题在线段树上 -1，所有第二种命题就在线段树上查一下最大值即可。为了方便叙述，称第一种命题为操作一，第二种命题为操作二。

考虑一些处理区间询问的算法。题目询问的信息显然不好用线段树维护。考虑莫队，发现也不太好维护。注意到询问的区间具有单调性，可以预处理出每个右端点对应的最长区间。考虑双指针，它相比莫队可以保证只在合法时操作。

新增一个操作二：直接在线段树上查一下即可；
新增一个操作一：先找到当前操作所在的极长负数连续段，然后看看有没有操作二被包含在内；

如果不合法就 l++，直到合法之后再 r++。

代码

#include<iostream>
#include<queue>
using namespace std;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;

struct Qr {
    int tp, l, r;
} qr[N];

int T, n, m, q;
int ans[N];

namespace SegT1 {
    int mx[4 * N], tag[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
    inline void move_tag(int p, int tg) { mx[p] += tg; tag[p] += tg; }
    inline void push_down(int p) { if(tag[p]) { move_tag(lc(p), tag[p]); move_tag(rc(p), tag[p]); tag[p] = 0; } }
    inline void clear() { for(int i = 0; i <= 4 * n; i++) mx[i] = tag[i] = 0; }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) { move_tag(p, v); return; }
        int mid = (l + r) >> 1; push_down(p);
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    int query_mx(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return mx[p];
        int mid = (l + r) >> 1; push_down(p);
        if(qr <= mid) return query_mx(lc(p), l, mid, ql, qr);
        if(mid < ql) return query_mx(rc(p), mid + 1, r, ql, qr);
        return max(query_mx(lc(p), l, mid, ql, qr), query_mx(rc(p), mid + 1, r, ql, qr));
    }
    int query_l(int p, int l, int r, int qr) {
        if(l > qr) return 0;
        if(mx[p] < 0) return 0;
        if(l == r) return l;
        int mid = (l + r) >> 1; push_down(p);
        int res = query_l(rc(p), mid + 1, r, qr);
        if(res) return res;
        return query_l(lc(p), l, mid, qr);
    }
    int query_r(int p, int l, int r, int ql) {
        if(r < ql) return n + 1;
        if(mx[p] < 0) return n + 1;
        if(l == r) return l;
        int mid = (l + r) >> 1; push_down(p);
        int res = query_r(lc(p), l, mid, ql);
        if(res != n + 1) return res;
        return query_r(rc(p), mid + 1, r, ql);
    }
}

namespace SegT2 {
    int mx[4 * N];
    priority_queue<int> que[N], del[N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) { mx[p] = max(mx[lc(p)], mx[rc(p)]); }
    inline void clear() {
        for(int i = 0; i <= 4 * n; i++) mx[i] = 0;
        for(int i = 0; i <= n + 5; i++) {
            while(!que[i].empty()) que[i].pop();
            while(!del[i].empty()) del[i].pop();
            que[i].push(-INF);
        }
    }
    void modify(int p, int l, int r, int q, int v) {
        if(l == r) { mx[p] = v; return; }
        int mid = (l + r) >> 1;
        if(q <= mid) modify(lc(p), l, mid, q, v);
        else modify(rc(p), mid + 1, r, q, v);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return mx[p];
        int mid = (l + r) >> 1;
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        return max(query(lc(p), l, mid, ql, qr), query(rc(p), mid + 1, r, ql, qr));
    }
    inline void insert(int l, int r) {
        que[r].push(l);
        while(!del[r].empty() && que[r].top() == del[r].top()) { que[r].pop(); del[r].pop(); }
        modify(1, 1, n, r, que[r].top());
    }
    inline void erase(int l, int r) {
        del[r].push(l);
        while(!del[r].empty() && que[r].top() == del[r].top()) { que[r].pop(); del[r].pop(); }
        modify(1, 1, n, r, que[r].top());
    }
    inline bool check(int l, int r) {
        return query(1, 1, n, l, r) >= l;
    }
}

bool check(Qr x) {
    int l = x.l, r = x.r;
    if(x.tp == 0) {
        int el = SegT1::query_l(1, 1, n, l - 1) + 1;
        int er = SegT1::query_r(1, 1, n, r + 1) - 1;
        return !SegT2::check(el, er);
    } else return SegT1::query_mx(1, 1, n, l, r) == 0;
}

void insert(Qr x) {
    int l = x.l, r = x.r;
    if(x.tp == 0) {
        SegT1::add(1, 1, n, l, r, -1);
    } else {
        SegT2::insert(l, r);
    }
}

void erase(Qr x) {
    int l = x.l, r = x.r;
    if(x.tp == 0) {
        SegT1::add(1, 1, n, l, r, 1);
    } else {
        SegT2::erase(l, r);
    }
}

void clear() {
    SegT1::clear();
    SegT2::clear();
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> T;
    while(T--) {
        cin >> n >> m;
        clear();
        for(int i = 1; i <= m; i++) {
            cin >> qr[i].tp >> qr[i].l >> qr[i].r;
        }
        for(int i = 1, j = 1; i <= m; i++) {
            while(j < i && !check(qr[i])) erase(qr[j++]);
            insert(qr[i]);
            ans[i] = j;
        }
        cin >> q;
        while(q--) {
            int l, r;
            cin >> l >> r;
            cout << (ans[r] <= l ? "yEs\n" : "nO\n");
        }
    }

    return 0;
}