2021-08-11 13:00 北京大学 C++

关注

牛客多校第七场题解

B xay loves monotonicity

题意：给定两个长度为 $n$ 的序列 $\{ a_n \}$ 与 $\{ b_n \}$ ， $\forall i \in [1,n]$ ， $b_i \in \{ 0,1\}$ 。有如下的修改操作：

给定 $i$ 与 $x$ ，令 $a_i=x$ 。
给定 $l,r$ ，区间 $b[l \cdots r]$ $0,1$ 翻转。

有如下询问：给定区间 $[l,r]$ ，将 $l$ 放入集合 $S$ 中，记集合 $S$ 中最后一个元素为 $x$ ，找到 $\{ a_n \}$ 中满足 $a_y \geq a_x$ 且 $y \leq r$ 的最小的 $y$ ，并插入集合。记 $S$ 最终大小为 $m$ ，问 $b_{S_1},b_{S_2},\cdots, b_{S_m}$ 中相邻不同的个数。 $n, q\leq 1\times 10^5$ 。

解法：首先考虑如何才能统计不连续的 $b$ 序列的答案。注意到我们需要让每一次的 $a_i$ 变大，因而我们可以划定一个下界，只有 $a$ 在下界之上的才进行统计。

定义一个 cal 函数——cal(l,r,maximum)，其中 maximum 为一个 pair 类型，存放了要求的 $a$ 的下界（即左侧区间的 $a$ 的最大值）与这个 $a$ 对应的 $b$ 。其计算可以类似线段树，递归的进行。

记待查区间为 $[l,r]$ 。如果左侧区间 $[l,mid]$ 的 $a$ 的最大值不大于要求的值，则左侧区间全军覆没，直接去右侧区间去查询；反之，则在左侧区间查询，同时该大节点 $[l,r]$ 上会存储一个“在大于 $[l,mid]$ 最大值的情况下右侧区间 $[mid+1,r]$ 的答案”，累计上这一部分即可。类似的思想还在洛谷 P4198 楼房重建中有所体现，可以在此题中进一步的加强理解。因而调用一次 cal 函数的复杂度为 $O(\log n)$ 。

int cal(int place, int left, int right, pair<long long, bool> num)
{
    if(left == right)
        return t[place].maximum.first >= num.first && num.second != t[place].maximum.second;
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    if (num.first <= t[place<<1].maximum.first)
        return cal(place << 1, left, mid, num) + t[place].right_num;//右侧区间对应的答案存放在right_num中
    else
        return cal(place << 1 | 1, mid + 1, right, num);
}

因而，线段树上维护的信息就有—— $[l,r]$ 上 $a$ 的最大值与对应位置的 $b$ 的值； $b$ 区间修改的 tag；右侧区间在满足左侧区间最大值的情况下的答案 right_num。

对于两个修改操作——这个是非常常见的线段树操作。只说一下区间合并 pushup 的操作——最大值同朴素的最大值合并，最大值的答案可以直接暴力去查询。

接下来就是查询操作。由于题目的要求，左端点必取，因而先把这一位对应的 $a$ 与 $b$ 全查出来；之后将整个查询的大区间根据线段树分成 $O(\log n)$ 个区间，之后再对这些区间从左到右使用 cal 函数依次去查询对应的答案。注意向 cal 函数里传入的 maximum 需要不断的和当前区间的最大值做 max 操作。

整体复杂度 $O(q \log^2n)$ 。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct node
{
    pair<long long, bool> maximum;
    int right_num;
    int tag;
};
struct node t[800005];
long long a[200005];
bool b[200005];
void pushdown(int place,int left,int right)
{
    t[place << 1].maximum.second ^= t[place].tag;
    t[place << 1].tag ^= t[place].tag;
    t[place << 1 | 1].maximum.second ^= t[place].tag;
    t[place << 1 | 1].tag ^= t[place].tag;
    t[place].tag = 0;
}
int cal(int place, int left, int right, pair<long long, bool> num)
{
    if(left == right)
        return t[place].maximum.first >= num.first && num.second != t[place].maximum.second;
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    if (num.first <= t[place<<1].maximum.first)
        return cal(place << 1, left, mid, num) + t[place].right_num;
    else
        return cal(place << 1 | 1, mid + 1, right, num);
}
pair<long long, bool> my_max(pair<long long, bool> &a, pair<long long, bool> &b)
{
    return a.first > b.first ? a : b;
}
void pushup(int place, int left, int right)
{
    t[place].maximum = my_max(t[place << 1].maximum, t[place << 1 | 1].maximum);
    int mid = (left + right) >> 1;
    t[place].right_num = cal(place << 1 | 1, mid + 1, right, t[place << 1].maximum);
}
void build(int place,int left,int right)
{
    if(left==right)
    {
        t[place].maximum = make_pair(a[left], b[left]);
        return;
    }
    int mid = (left + right) >> 1;
    build(place << 1, left, mid);
    build(place << 1 | 1, mid + 1, right);
    pushup(place, left, right);
}
void update_a(int place,int left,int right,int start,long long x)
{
    if(left==right)
    {
        t[place].maximum.first = x;
        return;
    }
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    if(start<=mid)
        update_a(place << 1, left, mid, start, x);
    else
        update_a(place << 1 | 1, mid + 1, right, start, x);
    pushup(place, left, right);
}
void update_b(int place, int left, int right, int start, int end)
{
    if(start<=left && right<=end)
    {
        t[place].maximum.second ^= 1;
        t[place].tag ^= 1;
        return;
    }
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    if(start<=mid)
        update_b(place << 1, left, mid, start, end);
    if(end>mid)
        update_b(place << 1 | 1, mid + 1, right, start, end);
    pushup(place, left, right);
}
struct interval
{
    int place;
    int left;
    int right;
};
vector<interval> ask;
void divide(int place,int left,int right,int start,int end)//根据线段树来划分区间
{
    if(start<=left && right<=end)
    {
        ask.push_back((interval){place, left, right});
        return;
    }
    pushdown(place, left, right);//一定记得要进行pushdown操作——虽然只是分区间。但是凡是分区间的，一律pushdown
    int mid = (left + right) >> 1;
    if(start<=mid)
        divide(place << 1, left, mid, start, end);
    if(end>mid)
        divide(place << 1 | 1, mid + 1, right, start, end);
}
pair<long long,bool> query_num(int place,int left,int right,int start)
{
    if(left==right)
        return t[place].maximum;
    pushdown(place, left, right);
    int mid = (left + right) >> 1;
    if(start<=mid)
        return query_num(place << 1, left, mid, start);
    else
        return query_num(place << 1 | 1, mid + 1, right, start);
}
int n;
int query_ans(int start,int end,pair<long long,bool> num)
{
    ask.clear();
    divide(1, 1, n, start, end);
    int ans = 0;
    for (auto i : ask)//我们把对应的区间都已经存下来了，只需要一段段的去查询就可以了
    {
        ans += cal(i.place, i.left, i.right, num);
        num = my_max(num, t[i.place].maximum);
    }
    return ans;
}
int main()
{
    int q, op, l, r;
    long long x;
    scanf("%d", &n);
    for (int i = 1; i <= n;i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= n;i++)
        scanf("%d", &b[i]);
    build(1, 1, n);
    scanf("%d", &q);
    while(q--)
    {
        scanf("%d", &op);
        switch(op)
        {
            case 1:
            {
                scanf("%d%lld", &l, &x);
                update_a(1, 1, n, l, x);
                break;
            }
            case 2:
            {
                scanf("%d%d", &l, &r);
                update_b(1, 1, n, l, r);
                break;
            }
            case 3:
            {
                scanf("%d%d", &l, &r);
                if(l==r)
                {
                    printf("0\n");
                    continue;
                }
                pair<long long, bool> head = query_num(1, 1, n, l);
                printf("%d\n", query_ans(l + 1, r, head));
                break;
            }

        }
    }
    return 0;
}

F xay loves trees

题意：给定两棵有 $n$ 个节点的树，要求找到最大的点集合 $S$ ， $\forall u,v \in S,u \neq v$ ：

在第一棵树上， $u$ 是 $v$ 的祖先或者 $v$ 是 $u$ 的祖先。
在第二棵树上， $u$ 不是 $v$ 的祖先并且 $v$ 不是 $u$ 的祖先。

并且还要求这些点在第一棵树上是连续的。求最大的集合大小。

解法：如果没有连续的条件，则是原题C. Trees of Tranquillity。

容易发现，这些点在第一棵树上构成了一条连续链。因而可以考虑在第一颗树上进行尺取法——划定所属区间的深度最小的节点（下称上界）与深度最大的节点（下称下界）。判定方法可以通过欧拉序列实现，同此题的判定方法，具体的可以参看我这一篇题解题解 CF1528C Trees of Tranquillity，基于第二棵树进行窗口的滑动。

暴力的实现方法是——当前节点必须要插入，对于和当前这一位冲突的，包含冲突的和它的祖先全部删掉。但是这个在极端数据下（例如链+菊花）会退化到 $O(n^2)$ 级别。这是因为可能下移一位就导致上界要向下移动非常的多。此题可以通过这一方法通过。

其实我们只需要一个修正就可以了——下界向下移动一位时上界至多只允许移动一位，如果要移动多位则要看下界的下方最长链长能否超过现有链长。如果没有可能，那么直接放弃这棵子树——它一定不会带来更优的答案。因而均摊下来区间下界移动一位上端点也只移动一位，复杂度还是接近 $O(n \log n)$ 。

具体代码可以参看这个提交：签到题破防 F

还有一种做法——使用可持久化数据结构如主席树，记录以当前节点为上端点其下端点能延申到的最远的区间集合。复杂度 $O(n \log ^2 n)$ 。

J xay loves Floyd

题意：给定一种错误的求全源最短路的方式——中转点在最内层循环。问这样错误的求法可以得到多少个正确的最短路数对。 $n \leq 2\times 10^3$ 。

解法：首先，正确的全源最短路是一定要求出的，可以使用 $n$ 次 Dijkstra 在 $O(n^2 \log n)$ 的时间内求出。

法一：一个较为暴力的方法。我们将正确的最短路对构建成一张新的图，然后直接用题目所给的错误最短路方法去跑，如果碰到正确的就加入到这张新图中。这种方法看似暴力，其实由于大多数边并未加入，因而复杂度是可以得到保证的。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <memory.h>
#include <bitset>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
long long dis[2005][2005], ori[2005][2005];
bool vis[2005], right[2005][2005];
vector<pair<int, long long>> graph[2005];
vector<int> newgraph[2005];
struct node
{
    int id;
    long long dis;
    bool operator<(const node &b) const
    {
        return dis>b.dis;
    }
};
struct line
{
    int from;
    int to;
    long long v;
    int next;
};
struct line que[5005];
int headers[2005], n, book[2005], cnt;
void add(int from,int to,long long v)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].v = v;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
void dijkstra(int place)
{
    priority_queue <node> q;
    for (int i = 1; i <= n; i++)
    {
        book[i] = 0;
        dis[place][i] = inf;
    }
    dis[place][place] = 0;
    q.push((node){place, 0});
    while(!q.empty())
    {
        node now = q.top();
        q.pop();
        if(book[now.id])
            continue;
        book[now.id]=1;
        for (int i = headers[now.id]; i; i = que[i].next)
            if (dis[place][que[i].to] > dis[place][now.id] + que[i].v)
            {
                dis[place][que[i].to] = dis[place][now.id] + que[i].v;
                q.push((node){que[i].to, dis[place][que[i].to]});
            }
    }
}
int main()
{
    int u, v, m;
    long long w;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ori[i][j] = dis[i][j] = inf;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%lld", &u, &v, &w);
        ori[u][v] = w;//按错误最短路跑的一张图
        add(u, v, w);
    }
    for (int i = 1; i <= n; i++)
        ori[i][i] = 0;
    for (int i = 1; i <= n; i++)
        dijkstra(i);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (ori[i][j]<inf)
                newgraph[i].push_back(j);
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dis[i][j]>=inf)//正确的都已经是inf了，错误的只会更大
                ans++;
            else
                for(auto k:newgraph[i])
                    if(dis[i][j]==ori[i][k]+ori[k][j])
                    {
                        ans++;
                        newgraph[i].push_back(j);
                        ori[i][j] = dis[i][j];
                        break;
                    }
    printf("%d", ans);
    return 0;
}

法二：考虑何时会得到正确的最短路。错误的最短路错误就在于——即使正确的松弛边还没有被松弛，只要中转点被遍历完就更新完毕，以错误的答案继续更新。因而想要正确，就必须保证在更新的时候，正确的最短路中转点出现，同时对应的两条松弛边也已经被松驰过了。因而需要三组 bitset——一组是刻画横向的 $dis$ ，一组是刻画纵向的 $dis$ ，还有一组是刻画松弛点。三者取与，如果存在某一个点在三个 bitset 中都取 $1$ ，则证明这个点可以被正确的更新。整体复杂度 $\displaystyle O(\frac{1}{32}n^3)$ ，完全可以通过此题。

K xay loves sequence

题意：给定一个长度为 $n$ 的序列 $\{ a_n \}$ ，一次操作允许对区间 $[l,r]$ 的全部数在模 $k$ 意义下加一或减一。 $q$ 组询问，给出 $l,r,k$ ，问最少多少次操作能将区间 $a[l,\cdots, r]$ 清零。保证 $0 \leq a_i <k$ ， $n,q \leq 1\times 10^5$ 。

解法：首先考虑暴力做法。当 $q=1$ 的时候此题退化为【GDOI2018 day1】密码锁（lock）。此题可以在 $O(n \log n)$ 的时间内完成，若不计排序则为 $O(n)$ 。考虑每次操作是 $\{a_n \}$ 区间 $[l,r]$ 整体增加 $1$ 或减少 $1$ ——因而可以考察其差分数组 $b_i$ ，区间归零的等价于区间差分归零。每一次区间修改等价于差分数组一个增加 $x$ 而另一个减少 $x$ 。注意到 $\displaystyle \sum_{i=1}^n a_i \equiv 0 \mod k$ ，因而一个贪心的做法是对于小的数减，对于大的数加，这样的操作数一定最少。因而首先对 $\{ b_n\}$ 都限制在 $[0,k)$ 的范围——对其取模，然后排序，构造其前缀数组 $\displaystyle {\rm pre}[i]=\sum_{j=1}^{i} b_j$ ，后缀数组 $\displaystyle {\rm suf}[i]=\sum_{j=i}^{n}k-b_j$ ，这是因为对于大的数，一定是往上累加到 $k$ 的。只需要找到一个值 $x$ 满足 ${\rm pre}[x-1]={\rm suf}[x]$ ，即证明从这里分界，比 $x$ 小的数减到 $0$ ，比 $x$ 大的数配合小的数减的操作，加到 $k$ ，不会浪费次数，因而答案就是 ${\rm suf}[x]$ 。这里找到这个 $x$ 既可以 $O(n)$ 的遍历也可以 $O(\log n)$ 的二分答案——显然这个是满足单调性的。

对于这题，如果直接使用这个方法，则整体复杂度会到达 $O(qn \log n)$ ，这显然是无法接受的。但是这个方法给了我们一个借鉴——原算法 $O(n)$ 的瓶颈在于：

要 $O(n)$ 的遍历整个数组以求出 ${\rm pre}[x]$ 与 ${\rm suf}[x]$ 。
针对于不同的 $k$ ，我们都需要排序。

我们可否使用一种数据结构，能够快速的排序，并求出这个数组。后面的二分过程复杂度仅 $O(\log n)$ ，可以保留。因而我们采用了主席树。考虑我们在原算法中需要哪些东西——前缀和与后缀和、元素出现的次数（因为有 $k$ 的存在），所以主席树中也需要维护这些东西——前缀和与出现的次数。

考虑最重要的二分过程。我们会划出一条大小的分界线出来，大数取 $k-x$ 而小数取 $x$ 。我们可以将这个原本是竖着划出来的线横过来——考察当值为多少的时候取 $k-x$ 与 $x$ 。因而二分的是分界值 $y$ 。因而我们需要统计大于 $y$ 出现的数的个数与和、小于 $y$ 的出现次数与和。

考虑到此处因为 $k$ 的不同，排序出来的结果也不同。但是我们的复杂度仅允许 $O(\log n)$ 级别，甚至都不允许 $O(n)$ 的遍历负数并对其修改，因而将正数负数分开处理。对于正数，那么在排序数组中出现的就是它本身；对于负数，它在排序的数组中是以 $k-x$ 的形式出现的。那么可以考虑直接拿掉这个 $k$ ，在负数这里也划出一条线—— $y-k$ ，作为分界线。在分界线的上方， $x$ （ $x<0$ ）对答案的贡献是 $-x$ ，而在分界线下方则是 $k-x$ 。

考虑了分界线上下，再来考虑分界线上的数字——这部分数字会被分割成两部分，一部分是作为小数看待的，而另一部分则是作为大数看待的。而这一部分需要进一步的二分答案来找到真正合适的一个划分方式。

最后要注意的一点就是区间的端点。因为每次给定的是一个区间，因而差分数组的 $b_l$ 项在真正操作的时候并不能直接使用——因为修改之后的差分数组在这一项上也并非是 $0$ 而是 $-a_{l-1}$ 。因而这一项单独判断，直接用 $a_l$ 作为差分数组的起点。

整体复杂度 $O(q \log^2 n)$ ，来源于二分的界限与主席树的 $O(\log n)$ 操作。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200000;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
struct node
{
    pair<long long, int> value;
    int leftson;
    int rightson;
};
struct node t[40 * N + 5];
int positive_root[N + 5], negative_root[N + 5];
int cnt;
void update(int &place,int old,int left,int right,int num)
{
    t[place].value = t[old].value;
    if(left==right)
    {
        t[place].value.first += num;
        t[place].value.second++;
        return;
    }
    int mid = (left + right) >> 1;
    if(num<=mid)
    {
        t[place].rightson = t[old].rightson;
        t[place].leftson = ++cnt;
        update(t[place].leftson, t[old].leftson, left, mid, num);
    }
    else
    {
        t[place].leftson = t[old].leftson;
        t[place].rightson = ++cnt;
        update(t[place].rightson, t[old].rightson, mid + 1, right, num);
    }
    t[place].value.first = t[t[place].leftson].value.first + t[t[place].rightson].value.first;
    t[place].value.second = t[t[place].leftson].value.second + t[t[place].rightson].value.second;
}
pair<long long, int> query(int former, int latter, int left, int right, int start, int end)
{
    if(left>end || right<start || !latter)
        return make_pair(0, 0);
    if(start<=left && right<=end)
        return make_pair(t[latter].value.first - t[former].value.first, t[latter].value.second - t[former].value.second);
    int mid = (left + right) >> 1;
    pair<long long, int> ans = make_pair(0, 0);
    if(start<=mid)
    {
        pair<long long, int> temp = query(t[former].leftson, t[latter].leftson, left, mid, start, end);
        ans.first += temp.first;
        ans.second += temp.second;
    }
    if(end>mid)
    {
        pair<long long, int> temp = query(t[former].rightson, t[latter].rightson, mid + 1, right, start, end);
        ans.first += temp.first;
        ans.second += temp.second;
    }
    return ans;
}
long long a[N + 5], dif[N + 5];
int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    long long maximum = -inf, minimum = inf;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        dif[i] = a[i] - a[i - 1];
        minimum = min(minimum, dif[i]);
        maximum = max(maximum, dif[i]);
    }
    for (int i = 1; i <= n;i++)
    {
        if(dif[i]>=0)
        {
            negative_root[i] = negative_root[i - 1];
            positive_root[i] = ++cnt;
            update(positive_root[i], positive_root[i - 1], 0, maximum, dif[i]);
        }
        else
        {
            negative_root[i] = ++cnt;
            positive_root[i] = positive_root[i - 1];
            update(negative_root[i], negative_root[i - 1], minimum, -1, dif[i]);
        }
    }
    while(q--)
    {
        int l, r;
        long long k, ans = inf;
        scanf("%d%d%lld", &l, &r, &k);
        long long left = 0, right = k;
        while(left<=right)
        {
            long long mid = (left + right) >> 1;
            long long upper = mid, lower = mid - k;
            pair<long long, int> positive_above = query(positive_root[l], positive_root[r], 0, maximum, upper + 1, maximum);
            pair<long long, int> positive_below = query(positive_root[l], positive_root[r], 0, maximum, 0, upper - 1);
            pair<long long, int> negative_above = query(negative_root[l], negative_root[r], minimum, -1, lower + 1, -1);
            pair<long long, int> negative_below = query(negative_root[l], negative_root[r], minimum, -1, minimum, lower - 1);
            if(a[l]>mid)
            {
                positive_above.first += a[l];
                positive_above.second++;
            }
            if(a[l]<mid)
            {
                positive_below.first += a[l];
                positive_below.second++;
            }
            long long suffix = (positive_above.second * k - positive_above.first) - negative_above.first, prefix = (negative_below.second * k + negative_below.first) + positive_below.first;
            int rest = r - l + 1 - positive_above.second - positive_below.second - negative_above.second - negative_below.second;
            if(suffix<prefix)
                right = mid - 1;
            else
                left = mid + 1;
            if(rest)
            {
                int center_left = 0, center_right = rest;
                while(center_left<=center_right)
                {
                    int center_mid = (center_left + center_right) >> 1;
                    long long add_suffix = suffix - center_mid * lower;
                    long long add_prefix = prefix + (rest - center_mid) * upper;
                    ans = min(ans, max(add_prefix, add_suffix));
                    if(add_suffix<add_prefix)
                        center_left = center_mid + 1;
                    else
                        center_right = center_mid - 1;
                }
            }
            else
                ans = min(ans, max(suffix, prefix));
        }
        printf("%lld\n", ans);
    }
    return 0;
}