首页 > 其他分享 >[蓝桥杯 2021 国 AB] 翻转括号序列(线段树上二分)

[蓝桥杯 2021 国 AB] 翻转括号序列(线段树上二分)

时间:2023-04-07 13:34:53浏览次数:44  
标签:pre AB int pos mid 蓝桥 括号 2021 query

[蓝桥杯 2021 国 AB] 翻转括号序列

题目描述

给定一个长度为 \(n\) 的括号序列,要求支持两种操作:

  1. 将 \(\left[L_{i}, R_{i}\right]\) 区间内(序列中的第 \(L_{i}\) 个字符到第 \(R_{i}\) 个字符)的括号全部翻转(左括号变成右括号,右括号变成左括号)。

  2. 求出以 \(L_{i}\) 为左端点时,最长的合法括号序列对应的 \(R_{i}\) (即找出最大的 \(R_{i}\) 使 \(\left[L_{i}, R_{i}\right]\) 是一个合法括号序列)。

输入格式

输入的第一行包含两个整数 \(n, m\),分别表示括号序列长度和操作次数。

第二行包含给定的括号序列,括号序列中只包含左括号和右括号。

接下来 \(m\) 行,每行描述一个操作。如果该行为 1 L R, 表示第一种操作,区间为 \(\left[L, R\right]\);如果该行为 2 L 表示第二种操作,左端点为 \(L\) 。

对于所有评测用例,\(1 \leq n \leq 10^{6}, 1 \leq m \leq 2 \times 10^{5}\) 。

Solution

分析一下操作二

看到这两个操作不难想到这个问题大概可以用线段树解决,不难想到我们可以把左括号看成1,右括号看成-1。这个时候的合法序列就应该是

\[legal\;sequence\iff sum(l\cdots r) = 0 \;and\; \forall_{k\in \{l\cdots r\}}sum(l\cdots k) \ge 0 \]

那如果用线段树直接去维护区间和,然后每次去查询\(l\)右侧是否有这样一个点是很困难的,所以要把它转化成前缀和形式

\[legal\;sequence\iff pre(r) = pre(l - 1) \;and\; \forall_{k\in \{l\cdots r\}}pre(k) \ge pre(l - 1) \]

所以对于每一个\(l\)我们要找的是\(l - 1\)右侧最后一个符合上述式子的位置即可。

对于操作一的实现

而对于翻转区间操作,如果翻转的区间的\(l = 1\),我们可以知道就是直接把\(l\cdots r\)全都取相反数而对于\([r + 1\cdots n]\)的区间应该全都减去某一个数

\[pre(r + 1) = pre(r) + sum(r + 1),\; pre(r + 2) = pre(r) + sum(r + 1) + sum(r + 2) \cdots \]

所以当\(pre(r) \rightarrow -pre(r)\)时,\([r + 1\cdots n]\)的区间应该全都减去原来的\(2 * pre(r)\),由于是区间操作,我们需要一个懒惰标记,记为\(lazy\_add\)。

像这种区间翻转一个很套路的做法就是

\[reverse(l\cdots r) \iff reverse(1\cdots r)\; + \; reverse(1\cdots l-1) \]

在线段树上翻转区间我们只要维护区间最大值和区间最小值,每次翻转就是交换最大最小值并且取负数,由于是区间操作,我们需要一个懒惰标记,记为\(lazy\_rev\)。

//假设p是我们当前操作区间的节点id
tmp1 = mx[p], tmp2 = mn[p];
mx[p] = (~tmp2) + 1;//取反加1就是取相反数
mn[p] = (~tmp1) + 1;
lazy_rev[p] ^= 1;

对于操作二的实现

很显然右端点所在的位置是可以二分的,那我们先考虑直接进行二分,我们每次去二分一个位置\(pos\)然后验证区间\([l\cdots pos]\)的最小值是否小于\(pre(l - 1)\),小于我们就去左侧区间,否则就去右侧区间,但是我们要注意如果右侧区间最小值大于\(pre(l - 1)\)其实也是没有答案的,因为我们要找的右端点\(pre(r) = pre(l - 1)\)

int now = query_po(1, 1, n, l - 1);//单点查询pre(l - 1)
int L = l, R = n;
int ans = 0;
while (L <= R) {
    int mid = L + R >> 1;
    int k = query(1, 1, n, l, mid);//查询区间(l, mid)最小值
    if (k < now || k >= now && query(1, 1, n, mid, n) > now) {//保证满足上述条件,其实可以不用第二个query
        R = mid - 1;
    } else {
        L = mid + 1;
        ans = mid;
    }
}

这个做法时间复杂度是\(O(m\log^2n)\),像我写法不太好就可能被卡掉,要常数非常小才有可能通过。所以我们得考虑把这个二分的过程搬到线段树上去,线段树的很多操作本质上就是在做二分,我们可以利用这个二分的过程。

基于朴素二分的优化

先看一下我一开始错误的二分方式

int query(int p, int l, int r, int pos, int val) {//pos代表题目中的l, val代表pre(l - 1)
    if (l == r) {
        if (mn[p] == val) return l;//要和val相等
        else return 0;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (pos > mid) return query(p << 1 | 1, mid + 1, r, pos, val);//pos在右侧我们直接去右儿子   (1)
    int ans = 0;
    if (mn[p << 1] < val) return query(p << 1, l, mid, pos, val);//如果左侧最小值小于val就得去左儿子  (2)
    if (mn[p << 1 | 1] <= val) ans = max(ans, query(p << 1 | 1, mid + 1, r, pos, val));//否则我们贪心先去右儿子,但右边最小值要<=val否则找不到val,为什么小于也可行,因为上一行代码已经保证了左侧最小值>=val,每一个括号只能产生1 or -1的贡献所以是连续的,所以右侧就一定会出现val (3)
    ans = max(ans, query(p << 1, l, mid, pos, val));//可能会返回0,所以再去左侧看看有没有答案
    return ans;
}

其实有很显然的错误

在(2)处,虽然我们保证了当前的\(pos \le mid\)但是\(l\)(线段树的区间的\(l\))依旧可能在\(pos\)的左侧,这就导致了mn[p << 1] < val这个语句会出错,我们要精确地找到这个\(pos\)右侧的最小值通过这一个\(query\)是不太可行的(至少我好像实现不了)。我们可以发现如果\(pos\)的右侧有一个最小值小于\(val\)那就一定是第一个小于\(val\)的左侧点(因为\(pre\)数组具有连续性且这个点是第一个小于val的点)。所以我们直接去二分\(pos\)右侧第一个小于\(val\)的点即可

int query_l(int p, int l, int r, int pos, int val) {
    if (l == r) return l;
    push_down(p);
    int mid = l + r >> 1;
    int ans = 0;
    if (mn[p << 1] < val && pos <= mid) ans =  query_l(p << 1, l, mid, pos, val);//pos在左侧区间并且最小值小于val
    if (ans) return ans;//如果已经有值直接返回就行,因为我们要找的是第一个
    if (mn[p << 1 | 1] < val) ans = query_l(p << 1 | 1, mid + 1, r, pos, val);//右侧要有<val的点才行
    return ans;
}

但是我们发现还有问题,比如这样一个序列((())),他的\(pre\)数组就全都\(\ge (pre(l - 1) = 0)\)也就是不存在小于\(pre(l - 1)\)的点,此时我们就得再去二分一次,去找到\(l\)右侧最后一个等于\(pre(l - 1)\)的点

int query_r(int p, int l, int r, int pos, int val) {
    if (l == r) return l;
    push_down(p);
    int mid = l + r >> 1;
    int ans = 0;
    if (mn[p << 1 | 1] <= val) ans = query_r(p << 1 | 1, mid + 1, r, pos, val);//由于前一次二分我们已经保证了pos右侧所有pre全都>=val所以有小于等于就是等于。还是贪心的先去右边
    if (ans) return ans;
    if (mn[p << 1] <= val && pos <= mid) ans =  query_r(p << 1, l, mid, pos, val);
    return ans;
}

然后还要在注意一下\(pos\)处是\()\)的情况。

LAZY标记!!!

最后,还有最关键的一点也是线段树区间修改最需要注意的地方也就是这种多个\(lazy\)标记的相互影响,打上\(lazy\_add\)标记不会对\(lazy\_rev\)产生影响, 但是打上\(lazy\_rev\)会对\(lazy\_add\)产生影响,由于\(lazy\_rev\)是区间取反,所以要把\(lazy\_add\)也取反。

CODE

\(O(n\log n)\)

bool lazy_rev[maxn << 2];
int mn[maxn << 2], mx[maxn << 2];
int lazy_add[maxn << 2];
string s;
int pre[maxn];
int n, q;
int tmp1, tmp2, tmp3, tmp4;

void build(int p, int l, int r) {
    if (l == r) {
        mn[p] = pre[l];
        mx[p] = pre[l];
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}

void push_down(int p) {
    if (lazy_rev[p]) {
        tmp1 = mn[p << 1], tmp2 = mn[p << 1 | 1];
        tmp3 = mx[p << 1], tmp4 = mx[p << 1 | 1];
        mn[p << 1] = (~tmp3) + 1;
        mx[p << 1] = (~tmp1) + 1;
        mn[p << 1 | 1] = (~tmp4) + 1;
        mx[p << 1 | 1] = (~tmp2) + 1;
        lazy_rev[p << 1] ^= 1;
        lazy_add[p << 1] = (~lazy_add[p << 1]) + 1;
        lazy_rev[p << 1 | 1] ^= 1;
        lazy_add[p << 1 | 1] = (~lazy_add[p << 1 | 1]) + 1;
        lazy_rev[p] = 0;
    }
    if (lazy_add[p]) {
        mx[p << 1] += lazy_add[p];
        mx[p << 1 | 1] += lazy_add[p];
        mn[p << 1] += lazy_add[p];
        mn[p << 1 | 1] += lazy_add[p];
        lazy_add[p << 1] += lazy_add[p];
        lazy_add[p << 1 | 1] += lazy_add[p];
        lazy_add[p] = 0;
    }
}

void update(int p, int l, int r, int ql, int qr) {
    if (ql > qr) return ;
    if (ql <= l && r <= qr) {
        tmp1 = mx[p], tmp2 = mn[p];
        mx[p] = (~tmp2) + 1;
        mn[p] = (~tmp1) + 1;
        lazy_add[p] = (~lazy_add[p]) + 1;
        lazy_rev[p] ^= 1;
        return ;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr);
    if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}

void update(int p, int l, int r, int ql, int qr, int val) {
    if (ql > qr) return ;
    if (ql <= l && r <= qr) {
        mx[p] += val;
        mn[p] += val;
        lazy_add[p] += val;
        return ;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr, val);
    if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr, val);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}

int query_po(int p, int l, int r, int pos) {
    if (pos < 1) return 0;
    if (l == r) return mn[p];
    push_down(p);
    int mid = l + r >> 1;
    if (pos <= mid) return query_po(p << 1, l, mid, pos);
    else return query_po(p << 1 | 1, mid + 1, r, pos);
}

int query_l(int p, int l, int r, int pos, int val) {
    if (l == r) return l;
    push_down(p);
    int mid = l + r >> 1;
    int ans = 0;
    if (mn[p << 1] < val && pos <= mid) ans =  query_l(p << 1, l, mid, pos, val);
    if (ans) return ans;
    if (mn[p << 1 | 1] < val) ans = query_l(p << 1 | 1, mid + 1, r, pos, val);
    return ans;
}

int query_r(int p, int l, int r, int pos, int val) {
    if (l == r) return l;
    push_down(p);
    int mid = l + r >> 1;
    int ans = 0;
    if (mn[p << 1 | 1] <= val) ans = query_r(p << 1 | 1, mid + 1, r, pos, val);
    if (ans) return ans;
    if (mn[p << 1] <= val && pos <= mid) ans =  query_r(p << 1, l, mid, pos, val);
    return ans;
}

void solve(int cas) {
    cin >> n >> q >> s;
    for (int i = 1; i <= n; ++i) {
        pre[i] = (s[i - 1] == '(' ? 1 : -1);
        pre[i] += pre[i - 1];
    }
    build(1, 1, n);
    while (q--) {
        int op, l, r; cin >> op;
        if (op == 1) {
            cin >> l >> r;
            int delta = query_po(1, 1, n, l - 1);
            update(1, 1, n, 1, l - 1);
            update(1, 1, n, l, n, (~(delta << 1)) + 1);
            delta = query_po(1, 1, n, r);
            update(1, 1, n, 1, r);
            update(1, 1, n, r + 1, n, (~(delta << 1)) + 1);
        } else {
            cin >> l;
            int now;
            now = query_po(1, 1, n, l - 1);
            int pos = query_l(1, 1, n, l, now);
            if (pos - 1 > l) cout << pos - 1 << '\n';
            else if (pos) cout << 0 << '\n';
            else cout << query_r(1, 1, n, l, now) << '\n';
        }
    }
}

\(O(n\log^2n)\)

bool lazy_rev[maxn << 2];
int mn[maxn << 2], mx[maxn << 2];
int lazy_add[maxn << 2];
string s;
int pre[maxn];
int n, q;

void build(int p, int l, int r) {
    if (l == r) {
        mn[p] = pre[l];
        mx[p] = pre[l];
        return ;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}

void push_down(int p) {
    if (lazy_rev[p]) {
        swap(mn[p << 1], mx[p << 1]);
        swap(mx[p << 1 | 1], mn[p << 1 | 1]);
        mn[p << 1] = -mn[p << 1];
        mx[p << 1] = -mx[p << 1];
        mn[p << 1 | 1] = -mn[p << 1 | 1];
        mx[p << 1 | 1] = -mx[p << 1 | 1];
        lazy_rev[p << 1] ^= 1;
        lazy_add[p << 1] *= -1;
        lazy_rev[p << 1 | 1] ^= 1;
        lazy_add[p << 1 | 1] *= -1;
        lazy_rev[p] = 0;
    }
    if (lazy_add[p]) {
        mx[p << 1] += lazy_add[p];
        mx[p << 1 | 1] += lazy_add[p];
        mn[p << 1] += lazy_add[p];
        mn[p << 1 | 1] += lazy_add[p];
        lazy_add[p << 1] += lazy_add[p];
        lazy_add[p << 1 | 1] += lazy_add[p];
        lazy_add[p] = 0;
    }
}

void update(int p, int l, int r, int ql, int qr) {
    if (r < l || ql > qr) return ;
    if (ql <= l && r <= qr) {
        swap(mx[p], mn[p]);
        mx[p] = -mx[p];
        mn[p] = -mn[p];
        lazy_add[p] *= -1;
        lazy_rev[p] ^= 1;
        return ;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr);
    if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}

void update(int p, int l, int r, int ql, int qr, int val) {
    if (r < l || ql > qr) return ;
    if (ql <= l && r <= qr) {
        mx[p] += val;
        mn[p] += val;
        lazy_add[p] += val;
        return ;
    }
    push_down(p);
    int mid = l + r >> 1;
    if (ql <= mid) update(p << 1, l, mid, ql, qr, val);
    if (mid < qr) update(p << 1 | 1, mid + 1, r, ql, qr, val);
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
}

int query_po(int p, int l, int r, int pos) {
    if (pos < 1) return 0;
    if (l == r) return mn[p];
    push_down(p);
    int mid = l + r >> 1;
    if (pos <= mid) return query_po(p << 1, l, mid, pos);
    else return query_po(p << 1 | 1, mid + 1, r, pos);
}

int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return mn[p];
    push_down(p);
    int mid = l + r >> 1;
    int ans = INF;
    if (ql <= mid) ans = min(ans, query(p << 1, l, mid, ql, qr));
    if (mid < qr) ans = min(ans, query(p << 1 | 1, mid + 1, r, ql, qr));
    return ans;
}

void solve(int cas) {
    cin >> n >> q >> s;
    for (int i = 1; i <= n; ++i) {
        pre[i] = (s[i - 1] == '(' ? 1 : -1);
        pre[i] += pre[i - 1];
    }
    build(1, 1, n);
    while (q--) {
        int op, l, r; cin >> op;
        if (op == 1) {
            cin >> l >> r;
            int delta = query_po(1, 1, n, l - 1);
            update(1, 1, n, 1, l - 1);
            update(1, 1, n, l, n, -2 * delta);
            delta = query_po(1, 1, n, r);
            update(1, 1, n, 1, r);
            update(1, 1, n, r + 1, n, -2 * delta);
        } else {
            cin >> l;
            int now;
            now = query_po(1, 1, n, l - 1);
            int L = l, R = n;
            int ans = l - 1;
            while (L <= R) {
                int mid = L + R >> 1;
                int k = query(1, 1, n, l, mid);
                if (k < now || k >= now && query(1, 1, n, mid, n) > now) R = mid - 1;
                else {
                    L = mid + 1;
                    ans = mid;
                }
            }
            if (ans < l) cout << 0 << '\n';
            else cout << ans << '\n';
        }
    }
}

标签:pre,AB,int,pos,mid,蓝桥,括号,2021,query
From: https://www.cnblogs.com/Fighoh/p/17295843.html

相关文章

  • 瓴羊Quick BI连续入选魔力象限ABI报告,实至名归
    经常听到周围有人说,自己的公司准备落地商业智能BI工具了,但市面上这些年层出不穷的BI工具实在太多,作为非专业人士很容易就挑花了眼,不知如何是好。在我看来,国际权威信息技术研究和分析公司Gartner每年出具的魔力象限ABI报告值得大家作为参考。其中,连续三年均入选魔力象限ABI报告的瓴......
  • ABB DSSR122 4899001-NK 执行各种各样的信号处理运营
    ABBDSSR1224899001-NK执行各种各样的信号处理运营数字信号处理(死后无子女。)的用途是数字处理例如通过计算机或更专门的数字信号处理器,执行各种各样的信号处理运营。这数字信号以这种方式处理的是一系列数字,它们表示样品的连续变量在时间、空间或频率等领域。在…里数字电子学......
  • 迁移学习《Efficient and Robust Pseudo-Labeling for Unsupervised Domain Adaptatio
    论文信息论文标题:EfficientandRobustPseudo-LabelingforUnsupervisedDomainAdaptation论文作者:HochangRhee、NamIkCho论文来源:2019——ICML论文地址:download 论文代码:download视屏讲解:click1摘要问题:无监督域适应传统方法将超过一定置信度阈值的数据视为目标域......
  • CentOS7安装zabbix-agent
    一:系统要求1.centos72.zabbix服务器端5.0版本 二:安转和配置zabbix1.安装zabbix存储库#rpm-Uvhhttps://repo.zabbix.com/zabbix/5.0/rhel/7/x86_64/zabbix-release-5.0-1.el7.noarch.rpm#yumcleanall2.安装zabbix代理#yuminstallzabbix-agent3.启动zabb......
  • Server Error `defineOptions()` in <script setup> cannot reference locally declar
    这个错误提示是因为在<scriptsetup>标签中使用了defineOptions()函数,并且该函数中引用了一个本地声明的变量(比如COMPONENT_NAME)。由于<scriptsetup>中的代码会被自动包装在setup()函数内部执行,而defineOptions()函数会被提升到setup()函数外部执行,因此就会出现该错误。为了解决......
  • 常用的ControlNet以及如何在Stable Diffusion WebUI中使用
    上一次我们已经介绍了如何通过代码的方式使用ControlNet,StableDiffusionWebUI里面包含了很详细的使用设置,我们可以直接在上面进行操作,所以本文将介绍如何以傻瓜的方式直接使用ControlNet。如果你用过StableDiffusion,可能已经注意到图像的输出有无限的结果可能性,就像在赌博一样......
  • SAP ABAP 初学者编程 – 在线培训
    SAPABAP初学者编程–在线培训与PeterMoxon一起学习SAPABAP编程。帮助学习以获得认证–终身访问+更新!课程英文名:sap-abap-programming-for-beginners此视频教程共1.22GB,中英双语字幕,画质清晰无水印,源码附件全课程地址:https://xueshu.fun/1468演示地址:https://w......
  • 纯电动汽车动力性经济性开发程序 Matlab AppDesigner 汽车性能开发工具
    纯电动汽车动力性经济性开发程序MatlabAppDesigner汽车性能开发工具电动汽车动力性计算电动汽车动力总成匹配写在前面:汽车动力性经济性仿真常用的仿真工具有AVLCruise、ameSIM、matlabsimulink、carsim等等,但这些软件学习需要付出一定时间成本,有很多老铁咨询有没有方便入......
  • bp神经网络交叉验证算法和确定最佳隐含层节点个数matlab 程序
    bp神经网络交叉验证算法和确定最佳隐含层节点个数matlab程序,直接运行即可。数据excel格式,注释清楚,效果清晰,一步上手。YID:6859628310735572......
  • labview视觉检测,一个相机,两个相机,抓边,找圆
    labview视觉检测,一个相机,两个相机,抓边,找圆,一套代码任意切换采用halcon模板匹配YID:33166640852673233......