题目内容

(题目内容改编自群友分享内容）

塔子哥最近学会了一种新的排序算法：X排序。

X排序算法的描述如下：首先，算法需要按某种规则选择该数列上至多X个位置，将其对应的数抽出来，其他的数都往左对齐，之后这X个数排好序之后依次放在原数列未尾，以上过程算作一次操作。

例如，对于数列 [ 1 , 3 , 5 , 4 , 2 ] [1,3,5,4,2] [1,3,5,4,2] ，当X＝2时可以选样数字5和4，之后数列变成 [ 1 , 3 , 2 , 4 , 5 ] [1,3,2,4,5] [1,3,2,4,5] 。

塔子哥现在得到了一个数组 a，但是他现在很忙，需要你帮忙计算出最少需要多少次上述操作，使得整个数列从小到大排好序？

# 输入描述

第一行一个正整数T，表示有T组数据。

对于每一组数据，第一行输入两个正整数 n n n , x x x ;

第二行输入 n n n 个数 a 1 , a 2 , … , a n a_1,a_2,\dots ,a_n a1​,a2​,…,an​, 该序列是一个 1~n 的排列。

对于所有数据： 1 ⩽ x ⩽ n ⩽ 1 0 5 , 1 ⩽ a t ⩽ n , a i ≠ a j , 1 ⩽ T ⩽ 5 1\leqslant x \leqslant n \leqslant 10^5,1\leqslant a_t \leqslant n, a_i \neq a_j, 1 \leqslant T \leqslant 5 1⩽x⩽n⩽105,1⩽at​⩽n,ai​=aj​,1⩽T⩽5

输出描述

对于每一组数据，输出一行一个整数，表示答案。

样例

输入

25 11 2 3 4 55 21 3 5 4 2

输出

02

样例解释

第一组数据，原数列已经排好序，则无需进行任何操作；

第二组数据，操作如下：

[ 1 , 3 , 5 , 4 , 2 ] [1,3,5,4,2] [1,3,5,4,2] -> [ 1 , 5 , 4 , 2 , 3 ] [1,5,4,2,3] [1,5,4,2,3]

[ 1 , 5 , 4 , 2 , 3 ] [1,5,4,2,3] [1,5,4,2,3] -> [ 1 , 2 , 3 , 4 , 5 ] [1,2,3,4,5] [1,2,3,4,5]

思路:二进制拆位 + 离线处理 + 妙用set

​ 0.这道题的一眼做法是开20个线段树，然后区间覆盖的板子。但是这里我给出一个稍微有意思的做法。这个问题的本质是可离线的序列上的区间覆盖问题

​ 1.观察到我们是所有操作都做完，最后做一次询问，而不是边操作边询问，所以可以使用离线技巧。

离线:说简单点，就是不按他读入的顺序来处理这些操作。我们可以自由的对操作进行排序来处理

​ 2.又观察到它所给的操作是位运算+覆盖，所以考虑按二进制的每一位去做:把序列的某一个二进制位摘出来排成数组，那么这些操作等价于在01数组上反复做区间覆盖。然后又可以离线，所以我们不难想到按时间倒着扫描这些操作。

​ 从倒着扫描这个角度来看，我们其实可以发现每个点最终的结果只会被最晚的cover这个点的那次操作给影响。所以可以想到搞一个set把数字1~n塞到set里。然后对于区间 [ l , r ] [l,r] [l,r] ， 我们不停的在set里二分找 i ∈ [ l , r ] i \in [l,r] i∈[l,r] 的点，覆盖，然后删除即可. 最后，我们将这些二进制位结果合并一下作为十进制整数输出即可。

​ 由于我们涉及到了比较多的二进制操作，可以使用bitset来缩短编码。

怎么样，大概理清思路了吗？先别急着看下面的标程，试着自己动手敲一下，然后来我们的OJ上提交一发试试看吧

代码 + 注释

#include<bits/stdc++.h>using namespace std;const int maxn = 100005;int l[maxn] , r[maxn];// bitset学习资料:/magisk/p/8809922.htmlbitset<40> a[maxn] , x[maxn] , res[maxn];int main (){int n;// 输入cin >> n;for (int i = 1 ; i <= n ; i++) {int g; cin >> g;a[i] = g;}int q;cin >> q;for (int i = 1 ; i <= q ; i++) {int g; cin >> g;l[i] = g;}for (int i = 1 ; i <= q ; i++) {int g; cin >> g;r[i] = g;}string op_str;cin >> op_str;op_str = '#' + op_str;for (int i = 1 ; i <= q ; i++) {int g; cin >> g;x[i] = g;}// 按位计算for (int d = 0 ; d <= 21 ; d++){// 离线处理，并把问题变成序列上的区间覆盖// {l , r , 0/1} 代表将区间[l,r]覆盖成0/1vector<tuple<int , int , int >> op_arr;for (int i = 1 ; i <= q ; i++){char op = op_str[i];int nowx = x[i][d];if (op == '='){op_arr.push_back(make_tuple(l[i] , r[i] , nowx));}else if (op == '&'){if (nowx == 0)op_arr.push_back(make_tuple(l[i] , r[i] , 0));}else {if (nowx == 1)op_arr.push_back(make_tuple(l[i] , r[i] , 1));}}// 建立set,一开始所有点都待处理set<int> rest;for (int i = 1 ; i <= n ; i++) rest.insert(i);// 倒着扫，因为每个点只会被最晚的覆盖它的操作影响reverse(op_arr.begin() , op_arr.end());for (auto &op : op_arr){int l = get<0>(op);int r = get<1>(op);int v = get<2>(op);int cnt = 0;// 不停的找元素属于[l,r] ， 直到没有....while (rest.size()){auto it = rest.lower_bound(l);if (it == rest.end() || *it > r) break;a[*it][d] = v;rest.erase(it);}}}// 输出for (int i = 1 ; i <= n ; i++){cout << a[i].to_ulong();if (i == n) cout << endl;else cout << " "; }return 0;}

更多大厂笔试真题与题解，尽在塔子哥学算法的OJ！