当前位置: 首页> 教育> 幼教 > 中国最厉害的网站建设公司_合肥瑶海区地图全图高清版_知乎关键词排名优化_武汉seo网络营销推广

中国最厉害的网站建设公司_合肥瑶海区地图全图高清版_知乎关键词排名优化_武汉seo网络营销推广

时间:2025/7/16 5:36:04来源:https://blog.csdn.net/Asuna666w/article/details/144143282 浏览次数:0次
中国最厉害的网站建设公司_合肥瑶海区地图全图高清版_知乎关键词排名优化_武汉seo网络营销推广

别忘了请点个赞+收藏+关注支持一下博主喵!!!!  !  !  

关注博主,更多蓝桥杯nice题目静待更新:)    

数据结构

一、修改数组

【问题描述】

        给定一个长度为N的数组A=[ A1,A2,...,AN ],数组中有可能有重复出现的整数。

        现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,..., AN。

        当修改Ai时,小明会检查Ai是否在A1∼Ai−1中出现过。如果出现过,则小明 会给Ai加上1;如果新的Ai仍在之前出现过,小明会持续给Ai加1,直到Ai没有 在A1∼Ai−1中出现过。

        当AN也经过上述修改之后,显然A数组中就没有重复的整数了。

        现在给定初始的A数组,请你计算出最终的A数组。 

【输入格式】

        第一行包含一个整数N。

        第二行包含N个整数A1,A2,...,AN。

【输出格式】

        输出N个整数,依次是最终的A1,A2,...,AN。 

【样例输入】

        

【样例输出】

        2 1 3 4 5

【评测用例规模与规定】

        对于80% 的评测用例,1⩽N ⩽10000。

        对于所有评测用例,1⩽ N ⩽ 100000 , 1⩽ Ai ⩽1000000。

解析:

        本题的题意较为清晰,我们的任务也较为明确,即从前往后依次处理数组中的每个元素。 每当数组中的某一元素Ai 与A1∼Ai−1 出现相同值时,就令Ai 的值不断加1,直至Ai 不 等同于A1∼Ai−1 的任意一项。

        单从任务的描述上来看,题目是十分简单的。如果忽略数据范围,可能绝大部分人都会想到一种极其简单的做法:双层循环+判重来尝试对问题的求解。

         双层循环+判重这一方法的解题步骤大致如下。

        (1)初始化

                 定义两个数组vis[ ]、A[ ],其中 vis[i] 用来判断值为 i 的数是否出现过(若出现过, 则vis[i] = 1,反之 vis[i] = 0),A[i] 用来存储题目给定的第 i 个元素。默认情况下, vis[ ] 中任意一项的值均为 0。

        (2)双层循环+判重

                • 第一层循环用来遍历数组A的每一个元素。对于当前所遍历到的元素(设为x), 如果vis[x] = 0(此前 x 并未出现过),则令vis[x]=1(表示数值 x 已出现过), 继续遍历;反之,让x进入第二层循环。

                • 在第二层循环中,我们令x的值不断+1,直至vis[x]=0后,令vis[x]=1 并 跳出循环。 按照以上描述编写并成功运行代码,即可完成本题最基础的求解。

参考代码如下 【时间复杂度为 O(n^{2})】

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, a[N], vis[N];signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {if (!vis[a[i]]) {vis[a[i]] = 1;} else {while (vis[a[i]]) {a[i]++;}vis[a[i]] = 1;}}for (int i = 1; i <= n; i++) {cout << a[i] << (i == n ? "\n" : " ");}return 0;
}

         由于O(n2)的做法并不足以我们通过本题,因此我们需要考虑优化该做法。

         双层循环+判重可拆分为以下3个部分。

        (1)第一层循环:依次遍历数组中的每个元素。时间复杂度为O(n)。

        (2)第二层循环:令一个元素的值不断+1,直至它的值未曾出现过。时间复杂度为O(n)。

        (3)判重:判断一个数是否出现过。时间复杂度为O(1)。

         对于第(1)部分,由于我们要依次处理每个元素,所以遍历数组A的每个元素是必要的, 暂不考虑优化。

         对于第(2)部分,我们采用了笨方法,即让元素的值通过循环不断+1,直到它的值未出 现过。显然,这么做会导致元素的值是一点一点改变的,这并不高效。倘若我们能将它的值 快速改变为它最终要变为的值,就能达到优化的目的。

         对于第(3)部分,该部分的时间复杂度为O(1),已达最优,无法更进一步优化。

         针对上述(第(2)部分)分析,我们来思考一下,对于一个元素,如何快速求出它最终 要变为的值?如下图所示。

         假设当前要改变的元素的值为x(vis[x]=1),最后要变为的元素的值为y(vis[y]=0),那么对于y,由于它是在x不断加1后出现的第一个未出现过的数,因此在x∼y−1,所有的数必然都是已经出现过的了,即vis[x],vis[x+1], ...,vis[y−1]的值均为1。

         根据这条信息,我们就能大致锁定y的范围,即如果某个大于x的整数z满足

(x∼z已出现过的数的个数)小于z−x+1(x∼z所有数的个数),则y的范围必然为 x∼z;反之,如果,,则y必然在z之后。

        既然给定一个大于x的整数z,就能锁定y的大致范围,那么不妨让我们使用二分法不断缩减y可能存在的区间,直至求出y的值。

        但有一个问题:二分法的判定条件是与 z − x + 1 的关系,可我们要如何求解 呢? 显然,求解的方法也必须要高效。如果使用遍历的方法(时间复杂度为O(n)) 来求解,那么使用二分法将毫无意义。 因此,我们需要一种能快速求解[x,z]这一区间内vis[i]之和的工具。 对于能快速求解区间和且支持修改(vis的值会改变)的方法有许多,其中在算法竞赛中 被广泛使用的有线段树、树状数组等。 与线段树相比,树状数组的码量少、常数小,于是本题使用树状数组来求解vis的区间和。

参考代码如下【时间复杂度为O(n(log n)^{2})】 

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, a[N], vis[N], tree[N];int lowbit(int x) {return x & (-x);
}void add(int pos, int val) {while (pos < N) {tree[pos] += val;pos += lowbit(pos);}
}int query(int pos) {int res = 0;while (pos) {res += tree[pos];pos -= lowbit(pos);}return res;
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {if (!vis[a[i]]) {vis[a[i]] = 1;add(a[i], 1); // 将已出现过的值插入树状数组中} else {int l = a[i], r = N, y = -1;while (l <= r) {int mid = (l + r) >> 1;// 判断区间 [a[i], mid] 的值是否小于 mid - a[i] + 1if (query(mid) - query(a[i] - 1) < mid - a[i] + 1) {r = mid - 1;y = mid;} else {l = mid + 1;}}a[i] = y;vis[y] = 1;add(a[i], 1); // 将已出现过的值插入树状数组中}}for (int i = 1; i <= n; i++) {cout << a[i] << (i == n ? "\n" : " ");}return 0;
}

        除了二分和树状数组外,还有一种在竞赛中被广泛使用的数据结构可以帮助我们快速找到一个元素最终要变为的值,它就是并查集。并查集是一种树形的数据结构,可用于处理一些没有交集的合并查询问题。

        在本题中,我们可以定义一个数组far[ ]。其中,far[i]表示当我们遍历到的元素的值为i 时,应将这个元素的值改变为far[i]。

        在开始遍历数组之前,因为还没有任何元素的值重复(不需要改变),所以初始化所有far[i]的值为i。

        接着按照顺序,开始遍历数组A。

        假设在遍历的过程中,我们当前遍历到的元素的值为x,那么根据far[x]的定义,我们要将这个元素的值改变为far[x]。

        这步没有任何问题。

        同时,在处理完这个元素后,我们需要更新far[x]的值为far[x+1],为下一次遍历值为x的元素做准备。

        这是什么意思?

        简单来说,在我们下一次遍历到一个值为x的元素时,由于x已经重复了,所以正常情 况下,我们会将x的值改变为x+1。

        但x+1也可能已经重复了,因此我们要将 x+1 改变为 far[x+1](far[x+1]的定义是,当我们遍历到的元素的值为x+1时,应将元素的值改变为far[x+1])。

所以,根据far[x]的定义,当我们表示(再次)遍历到x时,要将x改变为far[x],可得

参考代码7-1-3【时间复杂度为O(nlogn)】 

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, a[N], far[N];int find(int x) {return far[x] = (x == far[x]) ? x : find(far[x]);
}signed main() {cin >> n;// 初始化for (int i = 1; i < N; i++) {far[i] = i;}for (int i = 1; i <= n; i++) {cin >> a[i];a[i] = find(a[i]);far[a[i]] = find(a[i] + 1); // 更新far数组}for (int i = 1; i <= n; i++) {cout << a[i] << (i == n ? "\n" : " ");}return 0;
}

二、翻转括号序列

【问题描述】

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

       (1)将[Li,Ri]区间内(序列中的第Li个字符到第Ri个字符)的括号全部翻转 (左括号变成右括号,右括号变成左括号)。

       (2)求出以Li为左端点时,最长的合法括号序列对应的Ri(即找出最大的Ri使 [Li,Ri]是一个合法括号序列)。

【输入格式】

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

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

        接下来m行,每行描述一个操作。如果该行为 “ 1LiRi ”,表示第一种操作,区间 为 [Li,Ri] ;如果该行为 “ 2Li ” 表示第二种操作,左端点为Li。

【输出格式】

        对于每个第二种操作,输出一行,表示对应的Ri。如果不存在这样的Ri,请输出0。

【样例输入】

        7 5

        ((())()

        2 3

        2 2

        1 3 5

        2 3

        2 1

【样例输出】

        4

        7

        0

        0

【评测用例规模与规定】

        对于20%的评测用例,n,m⩽5000;

        对于40%的评测用例,n,m⩽30000;

        对于60%的评测用例,n,m⩽100000;

        对于所有评测用例,1⩽n⩽106,1⩽m⩽2×105。

解析:

简单概括一下题目::::

给定一个长度为n的括号序列,序列只包含“(”和“)”两种字符。

现有m个操作,操作有以下两种类型。

         •1 LR:将区间[L,R]的括号进行翻转:“(”→“)”,“)”→“(”。

        •2 L:找出(输出)最大的R,使得区间[L,R]对应的括号序列是合法的。

请你完成这m个操作。

--------------------------------------------------------------------------------------------------------

        对于一个合法的括号序列而言,其必然满足以下条件。

         (1)序列中的每一个右括号之前都有一个左括号可以与之匹配。

         (2)序列中左括号的个数等于右括号的个数。

        若光是看这两个条件,是并不利于我们分析的。好在有关判断括号序列是否合法的问题 中,我们有一个最为常用的“套路”,即将左括号视为1、右括号视为−1。这样,判断一个 括号序列是否合法就可以转换为判断以下条件。

        (1)判断序列的任意前缀和是否都大于等于0(若出现前缀小于0的情况,则不是合法 括号序列)。

        (2)判断整个序列的前缀和是否等于0(若不等于0,则不是合法括号序列)。

         回到本题,我们的任务即根据题目给定的操作1,对括号序列进行相应的修改;根据题目 给定的操作2,完成对应的查询。

        为了方便查询,我们就按“套路”所说,即将序列中的左括号视为1、右括号视为−1(用 ai表示第i个括号对应的值)。

        先从暴力的角度入手。

         对于修改操作,我们可以轻易地遍历需要翻转的区间,将其中值为1(左括号)的数改为 −1,将其中值为−1(右括号)的数改为1以完成序列的翻转。

         对于查询操作,我们可以从题目给定的左端点L开始不断向后遍历。遍历的同时记录一 个变量sum,表示从L到当前(所遍历到的)位置之间的值的和(以L为起点的前缀和)。 若出现sum=0,且在此之前不存在sum<0的情况,则更新答案为当前(所遍历到的)位 置;若出现sum<0的情况,则停止遍历,输出答案,完成查询。

参考代码如下【时间复杂度为O(n×m),可通过20%的测试数据】

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;
int n, m, a[N];
string s;signed main() {cin >> n >> m >> s;// 左括号视为1,右括号视为-1for (int i = 0; i < s.size(); i++) {if (s[i] == '(') a[i + 1] = 1;else a[i + 1] = -1;}while (m--) {int op, L, R;cin >> op;if (op == 1) {cin >> L >> R;// 翻转for (int i = L; i <= R; i++) {a[i] = -a[i];}} else {cin >> L;int sum = 0, ans = 0;for (int i = L; i <= n; i++) {sum += a[i];if (sum < 0) break; // 合法括号序列的任意前缀和都必须大于等于0if (!sum) ans = max(ans, i);}cout << ans << '\n';}}return 0;
}

        当n,m的数据范围大了之后,我们就要考虑效率更高的做法。

        有关括号序列的任意前缀和,我们可以用数组 sum[] 来存储,即用 sum[i] 表示a1+a2+ ...+ai。这样,对于区间[L,R]而言,要使其对应的括号序列合法,就必须满足以下条件。

         •∀i∈[L,R] ( sum[i] − sum[L − 1] ) ⩾ 0 :sum[i] − sum[L − 1]= aL + ... + ai → 任意前缀和 大于等于0。

        •sum[R] − sum[L − 1] = 0 :sum[R] − sum[L − 1] = aL + ... + aR → 整个序列的前缀和等于0。

        操作次数的总和为m,这是无法减免的,因此要想降低程序的计算量,我们就一定得从单次操作的方向考虑如何快速完成查询操作和如何快速完成修改操作。

1.查询操作

        如果只考虑查询操作,我们可以将查询的步骤分解为以下两个部分。

         (1)找出以L为左端点的最长的合法区间,该区间满足min(sum[i])⩾sum[L−1]。

         (2)在该区间中找到最靠右的满足sum[i]−sum[L−1]=0的端点i(i即为答案)。 对于第一部分,因为随着i的增大(区间扩大),min(sum[i])只会越来越小,也就是 min(sum[i])是满足单调性的。于是,我们就可以使用二分法,即以L为左端点、二分区间 长度len,判定区间[L,L+len]的最小值是否大于等于sum[L−1],以找出最长的合法区间 [L,L+len]。

【提示】:

判定的过程中我们需要能够快速求解区间的最小值,可以采用诸如RMQ、线段树、树 状数组等算法、数据结构来处理。本题我们选择线段树,有关线段树查询区间最小值的 操作不赘述。 

        完成了第(1)部分后,紧接着的第(2)部分就是要让我们在一段合法区间[L,L+len] (该区间内任意一个前缀和均大于等于sum[L−1])中找出满足sum[i]=sum[L−1]最靠右的i。

        该怎么找呢?

        一种常用的方法是建立一棵线段树维护两个变量:mi、val。mi表示树上节点所维护区间 的最小sum[]值(最小前缀和);叶子节点的val值表示其对应括号的值,非叶子节点的 val 值表示其对应区间的括号值之和。

        有了这样一棵树后,我们就能通过在树上二分(为了找到最长的合法区间,需要先走右子树再走左子树),轻松找出最靠右的满足mi=sum[L−1]的端点i(i即为答案)。

        事实上,在 L+len < n 的情况下,我们不建立线段树就确定答案,答案一定是L+len。

        因为我们在对len 进行二分的过程中,使用的判断条件是sum[L+len] ⩾ sum[L−1] 。 那么合法区间是[L,L+len] 而不是 [L,L+len+1] 的原因只可能是 sum[L]∼sum[L+len] 的值均大于等于sum[L−1]、sum[L+len+1] 的值小于 sum[L−1]。

         由于序列每一项的值要么为1(左括号),要么为−1(右括号),因此相邻两项前缀和的差值 的绝对值必然是1,即sum[L+len+1]=sum[L+len]+1或sum[L+len+1] = sum[L+len]−1。 再根据sum[L+len] ⩾ sum[L−1]、sum[L+len+1] < sum[L−1]可得sum[L+len] = sum[L−1]。

2. 修改操作

        分析完查询操作后,我们只要能保证修改操作不出错,即可完成解题。修改操作十分简 单,我们可以沿用查询操作建立的线段树进行分析。 假设我们翻转了区间[L,R],那么存在以下情况。

        (1)根据越大的数取反后将变得越小,越小的数取反后将变得越大可得翻转后区间[L,R] 的最小前缀和min(sum[i])(对应线段树中的 mi)将变为翻转前区间[L,R] 的最大 前缀和的相反数,即−max(sum[i])。同样地,翻转后区间[L,R]对应的max(sum[i]) 也将变为翻转前区间[L,R]的−min(sum[i])。 因此,为了维护翻转后线段树中的mi的变化,我们还需要往线段树中添加一个变 量ma,表示树上节点所维护区间的最大sum[]值(最大前缀和)。

        (2)区间[R+1,n]中每一项的前缀和sum(对应线段树中叶子节点的mi)均会增加/减 少2×([L,R] 内左括号个数 −[L,R] 内右括号个数 )。

        到这我们的分析已经结束。

         我们可以结合前文分析,对线段树中所有的变量进行相对应的修改和更新,其中lazy,add, 分别表示区间翻转、区间增加/减少的懒标记。

【提示】因为区间翻转、区间增加/减少的先后顺序是有影响的,所以每次当区间需要翻转时, add 的值也需要取反,即令add=−add。

        此外,我们所说的前缀和都是针对于整个括号序列的,因此为了不影响我们思考的逻辑, 我们可以将翻转区间[L,R]的操作置换成以下两步。

         (1)翻转区间[1,R]。

        (2)翻转区间[1,L−1]。

具体代码见参考代码如下,该参考代码实际可以通过所有测试数据。

参考代码如下【时间复杂度为O(mlog^{2}n)】

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;const int N = 1e6 + 10, inf = 0x3f3f3f3f;struct Tree {int l, r;int mi, ma, sum;int lazy, add;
} tree[N << 2];int n, m, a[N], sum[N];
char s[N];void F1(int rt) {tree[rt].add *= -1;tree[rt].lazy *= -1;tree[rt].sum *= -1;tree[rt].ma *= -1;tree[rt].mi *= -1;swap(tree[rt].ma, tree[rt].mi);
}void F2(int rt, int val) {tree[rt].add += val;tree[rt].mi += val;tree[rt].ma += val;
}void push_up(int rt) {tree[rt].ma = max(tree[rt << 1].ma, tree[rt << 1 | 1].ma);tree[rt].mi = min(tree[rt << 1].mi, tree[rt << 1 | 1].mi);tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}void push_down(int rt) {int &x = tree[rt].lazy;if (x == -1) {F1(rt << 1);F1(rt << 1 | 1);x = 1;}int &y = tree[rt].add;if (y) {F2(rt << 1, y);F2(rt << 1 | 1, y);y = 0;}
}void build(int l, int r, int rt) {tree[rt].l = l;tree[rt].r = r;tree[rt].lazy = 1;if (l == r) {tree[rt].sum = a[l];tree[rt].mi = tree[rt].ma = sum[l];return;}int mid = l + r >> 1;build(l, mid, rt << 1);build(mid + 1, r, rt << 1 | 1);push_up(rt);
}void update_change(int L, int R, int rt) {int l = tree[rt].l, r = tree[rt].r;if (L <= l && r <= R) {F1(rt);return;}push_down(rt);int mid = l + r >> 1;if (L <= mid) update_change(L, R, rt << 1);if (R > mid) update_change(L, R, rt << 1 | 1);push_up(rt);
}void update_add(int L, int R, int rt, int val) {int l = tree[rt].l, r = tree[rt].r;if (L <= l && r <= R) {F2(rt, val);return;}push_down(rt);int mid = l + r >> 1;if (L <= mid) update_add(L, R, rt << 1, val);if (R > mid) update_add(L, R, rt << 1 | 1, val);push_up(rt);
}int query_range(int L, int R, int rt) {int l = tree[rt].l, r = tree[rt].r;if (L <= l && r <= R) return tree[rt].sum;push_down(rt);int mid = l + r >> 1, res = 0;if (L <= mid) res += query_range(L, R, rt << 1);if (R > mid) res += query_range(L, R, rt << 1 | 1);return res;
}int query_min(int L, int R, int rt) {int l = tree[rt].l, r = tree[rt].r;if (L <= l && r <= R) return tree[rt].mi;push_down(rt);int mid = l + r >> 1, res = inf;if (L <= mid) res = query_min(L, R, rt << 1);if (R > mid) res = min(res, query_min(L, R, rt << 1 | 1));return res;
}int query_check(int L, int R, int rt, int val) {int l = tree[rt].l, r = tree[rt].r;if (l == r) return l;push_down(rt);int mid = l + r >> 1;if (tree[rt << 1 | 1].mi <= val) return query_check(L, R, rt << 1 | 1, val);if (L <= mid) return query_check(L, R, rt << 1, val);return 0;
}void Change(int L, int R) {int add1 = 2 * query_range(1, R, 1) * -1;update_change(1, R, 1);if (R + 1 <= n) update_add(R + 1, n, 1, add1);if (L - 1 >= 1) {int add2 = 2 * query_range(1, L - 1, 1) * -1;update_change(1, L - 1, 1);update_add(L, n, 1, add2);}
}bool check(int L, int mid, int pre) {if (query_min(L, L + mid, 1) >= pre) return true;return false;
}signed main() {cin >> n >> m >> (s + 1); // 注意这里直接读入到s+1,因为数组下标从1开始for (int i = 1; i <= n; i++) {if (s[i] == '(') {a[i] = 1;sum[i] = sum[i - 1] + 1;} else {a[i] = -1;sum[i] = sum[i - 1] - 1;}}build(1, n, 1);while (m--) {int op, L, R;cin >> op;if (op == 1) {cin >> L >> R;Change(L, R);} else {cin >> L;if (query_range(L, L, 1) == -1) { // 第L个字符是右括号,则必然不存在以它为左端点的合法括号序列cout << 0 << '\n';continue;}int pre = query_min(L - 1, L - 1, 1); // 查询前L-1个字符的前缀和(即sum[L-1])int l = 1, r = n - L, len = 0;while (l <= r) {int mid = l + r >> 1;// 二分找出最小的len,满足sum[L]~sum[L + len]的值都大于等于sum[L-1](以L为左端点的括号序列的任意前缀都大于等于0)if (check(L, mid, pre)) {l = mid + 1;len = mid;} else {r = mid - 1;}}// 如果L+len < n,则sum[L + len]必然等于sum[L-1]if (L + len < n) {cout << L + len << '\n';continue;}int ans = query_check(L, n, 1, pre);if (ans != L) cout << ans << '\n';else cout << 0 << '\n';}}return 0;
}

三、双向排序

【问题描述】

        给定序列(a1,a2,...,an) = (1,2,...,n),即 ai = i。

        小蓝将对这个序列进行m次操作,每次可能是将a1,a2,...,aqi 降序排列,或者将 aqi , aqi+1 , …, an 升序排列。

        请求出操作完成后的序列。

【输入格式】

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

        接下来m 行描述对序列的操作,其中第i行包含两个整数pi,qi 表示操作类型和参 数。当pi =0 时,表示将a1,a2,...,aqi 降序排列;当pi =1 时,表示将aqi ,aqi+1 ,...,an 升序排列。

【输出格式】

        输出一行,包含n个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的 序列。

【样例输入】

        3 3

        0 3

        1 2

        0 2

【样例输出】

        3 1 2

【样例说明】

        原序列为(1,2,3) 。

        第1 步后为(3,2,1) 。

        第2 步后为(3,1,2) 。

        第3 步后为(3,1,2) 。与第 2 步操作后相同,因为前两个数已经是降序了。

【评测用例规模与规定】

        对于30% 的评测用例,n,m⩽1000;

        对于60% 的评测用例,n,m⩽5000;

        对于所有评测用例,1⩽n,m⩽100000,0⩽pi ⩽11⩽qi ⩽n。

解析:

这里我们直接讲拿100%分数的方法:

        由于并没有什么排序算法的时间复杂度能稳定在O(n)以下,因此当n⩽105时,继续讨论排序算法将不再有意义。我们应记得及时调整切入方向,去深入研究题目(隐藏)的性质。

        在本题中,只存在两种类型的操作:升序操作和降序操作。

         既然这m次操作都源自于以上两种类型,那这其中是否会存在一些关联呢?

        我们来分析一下。

        起初,序列是升序的。

        如果一开始就进行升序操作,显然是毫无意义的(不会影响序列的排序),即无效操作。

         对于无效操作,我们理当将其忽视。待我们将所有的无效操作忽视后,首先进行的有效 操作必然会是个降序操作。

         因此,在进行了第一次的有效操作后,序列将会产生一段降序序列与升序序列,如下图 所示

        此时,若我们想对序列进行一次升序操作,则该操作可分为两种情况,如下图所示。 

        若想对序列进行一次降序操作,则该操作可分为两种情况,如下页图所示。 

        从上图不难发现,无论是进行了哪种类型的操作、产生了哪种情况,在每次操作结束后, 都总会有一个位置(设为pos)满足[1,pos] 的元素单调递减,[pos+1,n] 的元素单调递增。

         我们可以将区间[1,pos] 的数标记为0,将区间[pos+1,n] 的数标记为1,这样在所有操作结束后,从n∼1依次输出所有标记为0的数,得到的就是 答案的降序部分;从1∼n依次输出所有标记为1的数,得到的就是答案的升序部分。

         但问题来了,在上述做法中,我们是可以通过遍历区间来给数字打标记的。而在 n ⩽105 的数据范围下,遍历区间是必然不可行的。那么,要怎么为区间内的数字打标记呢? 我们接着往下思考。 由于刚开始(a1,a2,...,an) = (1,2,...,n),整个序列都是升序的,所以我们可以在初始 化的时候将所有数的标记都置为1(或者可以将a1单独视为一个递减序列,将a2∼an视为 递增序列,这样数字1的标记就为0,数字2∼n的标记就为1)。 为了方便描述,我们可以将递减的序列译为集合A,将递增的序列译为集合B,那么区 间[1,pos] 的元素就属于集合 A,区间[pos+1,n] 的元素就属于集合 B,如下图所示.

        对于某次升序操作,若其对应的升序区间为[x,n],则会存在以下两种情况。

        (1)pos ⩽x:由于 [pos,n] 是升序的,即 [x,n] 也是升序的,所以本次操作是个无效操 作,无须处理。

        (2)pos > x:此时 [pos,n] 是升序的,但 [x,pos−1] 还是降序的,所以我们需要将区 间[x,pos−1] 内的数的标记改为 1。

        在进行情况2中所说的处理之前,我们需要先知道区间[x,pos−1] 内的数分别是什么 (它们有什么样的性质、特点)。

        根据集合A是降序的可得,[x,pos−1]内的数其实就是标记为0的、最小的pos−x个 数。可我们要如何将这标记为0的、最小的pos−x的标记快速修改为1呢? 不妨让我们从数据结构的角度思考。 我们需要一种能够存储信息(每个数的标记值),同时能够快速、批量地修改多个数的信 息的数据结构。这时就非常适合用线段树。 

        我们可以建立一棵权值线段树,树的每个叶子节点的值对应每个数字的标记值,树的每 个节点维护其对应区间内的标记为0的数的个数。 这样处理之后,若想将标记为0的、最小的pos−x个数的标记值改为1,就只要在整 棵树上二分(先找左子树再找右子树)修改标记为0的数的个数即可。

        对于某次降序操作,其对应情况和处理方式与升序操作相似,这里就不再过多赘述。

         在处理完所有操作后,从n∼1依次输出所有标记为0的数,再从1∼n依次输出所有 标记为1的数,即可完成解答。

参考代码如下【时间复杂度为

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n, m, op, pos;struct Tree {int l, r, sum, lazy;
} tree[N << 2];void push_up(int rt) {tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}void push_down(int rt) {int &x = tree[rt].lazy;if (~x) {int len1 = tree[rt << 1].r - tree[rt << 1].l + 1;int len2 = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;tree[rt << 1].sum = len1 * x;tree[rt << 1 | 1].sum = len2 * x;tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = x;x = -1;}
}void build(int l, int r, int rt) {tree[rt].l = l;tree[rt].r = r;tree[rt].lazy = -1;if (l == r) {tree[rt].sum = 1;return;}int mid = l + r >> 1;build(l, mid, rt << 1);build(mid + 1, r, rt << 1 | 1);push_up(rt);
}void update1(int L, int R, int rt, int cnt) {if (!cnt) return;if (tree[rt].sum == cnt) {tree[rt].sum = tree[rt].lazy = 0;return;}push_down(rt);if (cnt < tree[rt << 1].sum) {update1(L, R, rt << 1, cnt);} else {update1(L, R, rt << 1 | 1, cnt - tree[rt << 1].sum);tree[rt << 1].sum = 0;tree[rt << 1].lazy = 0;}push_up(rt);
}void update2(int L, int R, int rt, int cnt) {if (!cnt) return;int len = tree[rt].r - tree[rt].l + 1;if (len - tree[rt].sum == cnt) {tree[rt].sum = len;tree[rt].lazy = 1;return;}push_down(rt);int cnt1 = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].sum;if (cnt < cnt1) {update2(L, R, rt << 1, cnt);} else {update2(L, R, rt << 1 | 1, cnt - cnt1);tree[rt << 1].sum = tree[rt << 1].r - tree[rt << 1].l + 1;tree[rt << 1].lazy = 1;}push_up(rt);
}int query(int L, int R, int rt) {int l = tree[rt].l, r = tree[rt].r;if (L <= l && r <= R) return tree[rt].sum;push_down(rt);int mid = l + r >> 1, res = 0;if (L <= mid) res += query(L, R, rt << 1);if (R > mid) res += query(L, R, rt << 1 | 1);return res;
}signed main() {cin >> n >> m;build(1, n, 1);while (m--) {cin >> op >> pos;if (!op) {int cnt0 = n - tree[1].sum; // 整个序列中0的个数int cnt = max(0, pos - cnt0); // 1 ~ pos中0的个数update1(1, n, 1, cnt); // 将最大的cnt个0改为1} else {int cnt1 = tree[1].sum;int cnt = max(0, n - pos + 1 - cnt1); // 同上update2(1, n, 1, cnt);}}for (int i = n; i >= 1; i--) {if (!query(i, i, 1)) cout << i << " "; // 输出集合A}cout << "\n";for (int i = 1; i <= n; i++) {if (query(i, i, 1)) cout << i << " "; // 输出集合B}cout << "\n";return 0;
}

        

关键字:中国最厉害的网站建设公司_合肥瑶海区地图全图高清版_知乎关键词排名优化_武汉seo网络营销推广

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: