【2021年省赛B组】试题I: 双向排序

题解

80pts:

调用sort()函数。 对于每个操作， 直接对相应区间使用sort()函数即可。 时间复杂度$O(nmlogn)$。

这里的代码来源于这位用户# Lost_Memory

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];

int main()
{
    int n, m;
    cin>>n>>m;

    for(int i = 1; i <= n; i ++ )
        a[i] = i;

    while(m -- )
    {
        int p,q;
        cin>>p>>q;
        if(!p)
        {
            sort(a + 1, a + q + 1, greater<int>());
        }
        else
        {
            sort(a + q, a + n + 1);
        }
    }

    for(int i = 1; i <= n; i ++ )
        cout<<a[i]<<" ";
}

90pts:

使用权值数组的做法： 举个例子：

• 对于降序序列操作，设它需要排序的区间为$[1， pos]$。那么我们可以先将$[1, pos]$内的每个数字打上标记，然后从$n$~$1$开始遍历每个数字。如果$i$数字是第1个被打上标记的数字，那么我们就令它插进入到第一个位置（即$a[1]=i$）， 如果是第2个被打上标记的数字，我们就让它插入到第二个位置（即$a[2]=i$）$\cdots$， 依次插入每个数，直到插完$[1, pos]$的所有位置。
• 对于升序操作操作同理。 时间复杂度$O(nm)$。

提交代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], flag[N];

void solve()
{
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) a[i] = i;
	for(int i = 0; i < m; i++)
	{
		int op, pos;
		cin >> op >> pos;
		if(op == 0)
		{
			for(int i = 1; i <= n; i++) flag[i] = 1;
			for(int i = 1; i <= pos; i++) flag[a[i]] = 0;
			int k = 0;
			for(int i = n; i >= 1; i--)
			{
				if(flag[i] == 0)
				{
					a[++k] = i;
				}
			}
		}
		else
		{
			for(int i = 1; i <= n; i++) flag[i] = 0;
			for(int i = pos; i <= n; i++) flag[a[i]] = 1;
			int k = pos - 1;
			for(int i = 1; i <= n; i++)
			{
				if(flag[i] == 1)
				{
					a[++k] = i;
				}
			}
		}
	}	
	
	for(int i = 1; i <= n; i++)
	{
		cout << a[i] << " \n"[i == n];
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

100pts:

分享两种做法：权值线段树和思维+栈

1.权值线段树

显然，每次操作结束后，总会有一个位置$pos$， 满足$[1, pos]$的元素单调递减，$[pos+1, n]$的元素单调递增。我们若将$[1, pos]$区间的数标记为0， $[pos+1, n]$的数标记为1， 那么在所有操作结束后，要怎么确定序列呢？

可以按照$90pts$的做法： 定义容器vec1, vec2。先从$n$~$1$遍历一遍， 若第$i$个数的标记为0，则将它存入$vec1$中；再从$1$~$n$遍历一遍，若第$i$个数字的标记为1， 则将它插入到$vec2$中， 那么最后依次输出$vec1, vec2$即为我们要的序列。

那怎么对数字打标记呢？

我们可以建立一棵权值线段树，树的每个叶子节点对应每个数字的标记。

由于刚开始$(a_1, a_2, \cdots, a_n) = (1, 2, \cdots, n)$, 真个序列是单调递增的，所以所有的数的标记都为1， （或者可以令$a_1$单独作为一个递减序列， $a_2$~$a_n$作为递增序列， 这样数字1的标记就为0， 数字$2$~$n$的标记为1）

我们就爱那个递减的序列设为集合$A$， 递增的序列设为集合$B$, 于是必然存在一个位置$pos$，使得$[1, pos]$的元素为$A$, $[pos+1, n]$的元素为$B$。

• 对于升序操作,设其对应的区间为$[x, n]$, 那么一共需要排序的数就有$cnt=n - x + 1$个。设集合$B$的大小为$size$， 则存在以下情况：
• • cnt $\leqslant$ size： 可得$pos\leqslant x$。由于$[pos,n]$是升序的了，即$[x, n]$也是升序的了， 所以本次操作作废。
• • cnt $>$ size: 可得$pos>x$。此时$[pos, n]$是升序的了，而$[x, pos - 1]$还是降序的， 所以我们需要将$[x, pos - 1]$区间内的数标记改为1。那么$[x, pos - 1]$的数有什么特点呢？它们属于集合$A$的末尾元素，而集合$A$又是降序的，所以$[x, pos- 1]$对应了标记为0的最小的$pos - x$个数， 我们只要将这几个数的标记改为1， 即实现一个支持区间覆盖的线段树即可。
• 对于降序操作同上。 时间复杂度$O(mlogn)$

提交代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct segTree
{
	int sum[N << 2], lazy[N << 2];
	segTree()
	{
		memset(lazy, -1, sizeof lazy);
		memset(sum, 0, sizeof sum);
	}
	void pushup(int o)
	{
		sum[o] = sum[o << 1] + sum[o << 1 | 1];
	}
	void pushdown(int o, int len1, int len2)
	{
		if(lazy[o] != -1)
		{
			sum[o << 1] = len1 * lazy[o];
			sum[o << 1 | 1] = len2 * lazy[o];
			lazy[o << 1] = lazy[o << 1 | 1] = lazy[o];
			lazy[o] = -1;
		}
	}
	void build(int o, int l, int r)
	{
		if(l == r)
		{
			sum[o] = 1;
			return;
		}
		int mid = l + r >> 1;
		build(o << 1, l, mid);
		build(o << 1 | 1, mid + 1, r);
		pushup(o);
		
	}
	void modify1(int o, int l, int r, int cnt)
	{
		if(cnt == 0) return;
		if(l > r) return;
		if(sum[o] == cnt)
		{
			sum[o] = 0;
			lazy[o] = 0; 
			return;
		}
		int mid = l + r >> 1;
		pushdown(o, mid - l + 1, r - mid);
		if(cnt < sum[o << 1])
		{
			modify1(o << 1, l, mid, cnt);
		}
		else
		{
			modify1(o << 1 | 1, mid + 1, r, cnt - sum[o << 1]);
			sum[o << 1] = 0;
			lazy[o << 1] = 0;
		}
		pushup(o);
	}	
	void modify2(int o, int l, int r, int cnt)
	{
		if(cnt == 0) return;
		if(l > r) return;
		
		int cnt0 = r - l + 1 - sum[o];
		if(cnt == cnt0)
		{
			sum[o] = r - l + 1;
			lazy[o] = 1;
			return;
		}
		int mid = l + r >> 1;
		pushdown(o, mid - l + 1, r - mid);
		cnt0 = mid - l + 1 - sum[o << 1];
		if(cnt < cnt0)
		{
			modify2(o << 1, l, mid, cnt);
		}
		else
		{
			modify2(o << 1 | 1, mid + 1, r, cnt - cnt0);
			sum[o << 1] = mid - l + 1;
			lazy[o << 1] = 1;
		}
		pushup(o);
	}
	int query(int o, int l, int r, int L, int R)
	{
		if(L <= l && r <= R) return sum[o];
		int mid = l + r >> 1;
		pushdown(o, mid - l + 1, r - mid);
		int res = 0;
		if(L <= mid)
		{
			res += query(o << 1, l, mid, L, R);
		}
		if(R > mid) res += query(o << 1 | 1, mid + 1, r, L, R);
		return res;
	}
};

void solve()
{
	segTree tree;
	int n, m; cin >> n >> m;
	tree.build(1, 1, n);
	for(int i = 0; i < m; i++)
	{
		int op, pos;
		cin >> op >> pos;
		if(op == 0)
		{
			int cnt0 = n - tree.sum[1];
			int cnt = max(0, pos - cnt0); 
			tree.modify1(1, 1, n, cnt);
		}
		else
		{
			int cnt1 = tree.sum[1];
			int cnt = max(0, n - pos + 1 - cnt1);
			tree.modify2(1, 1, n, cnt);
		}
	}
	for(int i = n; i >= 1; i--)
	{
		if(tree.query(1, 1, n, i, i) == 0)
		{
			cout << i << " ";
		}
	}
	for(int i = 1; i <= n; i++)
	{
		if(tree.query(1, 1, n, i, i) == 1)
		{
			cout << i << " ";
		}
	}
	cout << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

2.思维+栈

思维题目，我们可以通过把操作读入，去掉那些没有用的操作，达到剪枝的操作。 预处理维护一个栈，满足如下性质：

1. 栈中的元素操作1和操作2交替分布，
2. 并且后出现的操作1右区间比先出现的操作1右区间要小，后出现的操作2左区间比先出现的操作2左区间要小，为了维护这个特性，需要用到栈的后进先出的特性。 为什么需要维护这样一个序列，可以考虑一下，对于同种操作，例如操作1，连续的多个操作，只需要考虑多个操作中的最大的右区间， 同理对应操作2，考虑最小的左区间，所以维护的序列是操作交替的，由此可以得到如下图的栈：

还有一个重要的性质：我们维护性质2时候，对于操作1，如果后来的操作1的右区间比之前的操作1的右区间大，那么两个操作1夹杂的操作2和前面的操作1都可以删去， 如下图1所示,S1段是之前操作1调整的区间，我们由图可以知道最大右区间的那个线段的操作既可以实现操作1小的右区间的降序，又能将和中间交替夹杂的操作2的升序操作的重叠部分降序，由于不重叠部分本来之前是升序的，所以相当于操作2可以不用做了，小的右区间的操作1也可以不用做了。对于图2同理。

那么最后的答案如何获得呢？我们再次回到第一个图，获得答案有点类似于双指针，当我们维护好一个满足上面条件的栈时，我们可以分析一下，是不是对于操作1，在栈中的右区间是单调递减的，所以我们可以根据前面的操作1最大能到的右区间，那么再往右的区间就是固定的升序了，并且一开始一定是n结尾的，以第一个操作1的右区间的值开始的，步长为1的一个序列 ，同理对于操作2同理，第二行的黄色方块，这次之后的操作2也一定到不了比这次还靠前的位置，所以从1开始到操作2的左区间的轴值也是固定下来了，注意这里是降序剩下的序列，所以这里的值从上一个操作1的右区间开始递减。我们可以通过l和r的双指针去实现这个过程。

只要操作1和操作2的区间有重合的地方，就一定确定不下来，当前后两个完全没有重叠的地方，那么所有数的最终值都已固定，则是答案。但是如果最后还是有重合的地方，但是没有操作了，也就是以最后一次的操作为准，也就是只需要判断top值，即栈的元素个数，如果是奇数，也就是说最后一个操作是操作1，是需要降序的，也就是执行ans[l++] = k--;直到l > r。

如果是偶数，那么剩下的一段一定是升序剩下的，也就是执行ans[r--] = k--;直到l>r。

• 比较重要的点是k值是一直减小的，它的减小都是伴随着一些位置数的固定。

时间复杂度$O(n + m)$​

提交代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1e5 + 10;
typedef pair<int,int> PII;

void solve()
{
	int n, m; cin >> n >> m;
	PII stk[N];
	int ans[N];
	int top = 0;
	for(int i = 0; i < m; i++)
	{
		int op, pos;
		cin >> op >> pos;
		if(op == 0)
		{
			while(top && stk[top].x == 0)
			{
				pos = max(pos, stk[top--].y);
			}
			while(top >= 2 && stk[top - 1].y <= pos) 
			{
				top -= 2;
			}
			stk[++top] = {0, pos};
		}
		else if(top)
		{
			while(top && stk[top].x == 1)
			{
				pos = min(pos, stk[top--].y);
			}
			while(top >= 2 && stk[top - 1].y >= pos) 
			{
				top -= 2;
			}
			stk[++top] = {1, pos};
		}
	}
	
	int k = n, l = 1, r = n;
	for(int i = 1; i <= top; i++)
	{
		if(stk[i].x == 0)
		{
			while(r > stk[i].y && l <= r) ans[r--] = k--;
		}
		else 
		{
			while(l < stk[i].y && l <= r) ans[l++] = k--;
		}
		if(l > r) break;
	}
	
	if(top % 2 == 1)
	{
		while(l <= r) ans[l++] = k--;
	}
	else
	{
		while(l <= r) ans[r--] = k--;
	}
	for(int i = 1; i <= n; i++)
	{
		cout << ans[i] << " \n"[i == n];
	}
	
}	
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

80~90分做法

直接想到使用STL sort进行排序。 考虑数据本身有序，STL sort遇见的极端情况较多，考虑使用其他排序优化，如希尔排序

/*                     _ooOoo_
                      o8888888o
                      88" . "88
                      (| -_- |)
                       O\ = /O
                   ____/`---'\____
                 .   ' \\| |// `.
                  / \\||| : |||// \
                / _||||| -:- |||||- \
                  | | \\\ - /// | |
                | \_| ''\---/'' | |
                 \ .-\__ `-` ___/-. /
              ___`. .' /--.--\ `. . __
           ."" '< `.___\_<|>_/___.' >'"".
          | | : `- \`.;`\ _ /`;.`/ - ` : | |
            \ \ `-. \_ __\ /__ _/ .-` / /
    ======`-.____`-.___\_____/___.-`____.-'======
                       `=---='                      */
#include <bits/stdc++.h>

using namespace std;
using i128 [[maybe_unused]] = __int128;

std::istream &operator>>(std::istream &is, i128 &value) {
    value = 0;
    bool isNegative = false;
    int c = is.get();
    while (c < '0' or c > '9') {
        if (c == '-')
            isNegative = true;
        c = is.get();
    }
    while (c >= '0' and c <= '9') {
        value = (value << 3) + (value << 1) + (c ^ '0');
        c = is.get();
    }
    if (isNegative)
        value = -value;
    return is;
}

std::ostream &operator<<(std::ostream &os, i128 value) {
    if (value < 0) {
        value = ~value + 1;
        os.put('-');
    }
    static char sta[40];
    char top = 0;
    for (; value; value /= 10)
        sta[top++] = static_cast<char>(value % 10);
    for (; top--;)
        os.put(static_cast<char>(sta[top] ^ '0'));
    return os;
}

using i64 [[maybe_unused]] = long long;
template<typename T, class comparer = greater<T>>
using heap [[maybe_unused]] = priority_queue<T, vector<T>, comparer>;
template<typename T1, typename T2>
using hash_map [[maybe_unused]] = unordered_map<T1, T2>;
template<typename T>
using hash_set [[maybe_unused]] = unordered_set<T>;
const char &ln = '\n';

template<typename T, typename V>
T as [[maybe_unused]](const V &val) { return static_cast<T>(val); }

template<typename T, class Begin, class End>
void println [[maybe_unused]](Begin begin, End end, const char *c = " ") {
    copy(begin, end, ostream_iterator<T>(cout, c));
    cout.put('\n');
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, p, q;
    cin >> n >> m;
    auto &&shell_sort = [](int *begin, const int *end, auto &&cmp) {
        int h = 1;
        i64 length = end - begin;
        while (h < length / 3)
            h = 3 * h + 1;
        for (; h >= 1; h /= 3) {
            for (int i = h; i < length; i++)
                for (int j = i; j >= h and cmp(begin[j], begin[j - h]); j -= h)
                    swap(begin[j], begin[j - h]);
        }
    };
    int arr[n];
    iota(arr, arr + n, 1);
    while (m--) {
        cin >> p >> q;
        if (p)
            shell_sort(arr + q - 1, arr + n, less<>());
        else
            shell_sort(arr, arr + q, greater<>());
    }
    println<int>(arr, arr + n);
    return 0;
}

100分做法，参考队长的题解，改为STL实现

/*                     _ooOoo_
                      o8888888o
                      88" . "88
                      (| -_- |)
                       O\ = /O
                   ____/`---'\____
                 .   ' \\| |// `.
                  / \\||| : |||// \
                / _||||| -:- |||||- \
                  | | \\\ - /// | |
                | \_| ''\---/'' | |
                 \ .-\__ `-` ___/-. /
              ___`. .' /--.--\ `. . __
           ."" '< `.___\_<|>_/___.' >'"".
          | | : `- \`.;`\ _ /`;.`/ - ` : | |
            \ \ `-. \_ __\ /__ _/ .-` / /
    ======`-.____`-.___\_____/___.-`____.-'======
                       `=---='                      */
#include <bits/stdc++.h>

using namespace std;
using i128 [[maybe_unused]] = __int128;

std::istream &operator>>(std::istream &is, i128 &value) {
    value = 0;
    bool isNegative = false;
    int c = is.get();
    while (c < '0' or c > '9') {
        if (c == '-')
            isNegative = true;
        c = is.get();
    }
    while (c >= '0' and c <= '9') {
        value = (value << 3) + (value << 1) + (c ^ '0');
        c = is.get();
    }
    if (isNegative)
        value = -value;
    return is;
}

std::ostream &operator<<(std::ostream &os, i128 value) {
    if (value < 0) {
        value = ~value + 1;
        os.put('-');
    }
    static char sta[40];
    char top = 0;
    for (; value; value /= 10)
        sta[top++] = static_cast<char>(value % 10);
    for (; top--;)
        os.put(static_cast<char>(sta[top] ^ '0'));
    return os;
}

using i64 [[maybe_unused]] = long long;
template<typename T, class comparer = greater<T>>
using heap [[maybe_unused]] = priority_queue<T, vector<T>, comparer>;
template<typename T1, typename T2>
using hash_map [[maybe_unused]] = unordered_map<T1, T2>;
template<typename T>
using hash_set [[maybe_unused]] = unordered_set<T>;
const char &ln = '\n';

template<typename T, typename V>
T as [[maybe_unused]](const V &val) { return static_cast<T>(val); }

template<typename T, class Begin, class End>
void println [[maybe_unused]](Begin begin, End end, const char *c = " ") {
    copy(begin, end, ostream_iterator<T>(cout, c));
    cout.put('\n');
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, p, q;
    cin >> n >> m;
    int arr[n + 1];
    deque<pair<int, int>> sta;
    while (m--) {
        cin >> p >> q;
        if (not p) {
            for (; not sta.empty() and sta.back().first == 0; sta.pop_back())
                q = max(q, sta.back().second);
            for (; sta.size() >= 2 and next(sta.rbegin())->second <= q; sta.pop_back())
                sta.pop_back();
            sta.emplace_back(0, q);
        } else if (not sta.empty()) {
            for (; not sta.empty() and sta.back().first == 1; sta.pop_back())
                q = min(q, sta.back().second);
            for (; sta.size() >= 2 and next(sta.rbegin())->second >= q; sta.pop_back())
                sta.pop_back();
            sta.emplace_back(1, q);
        }
    }
    int k = n, l = 1, r = n;
    for (auto &&[x, y]: sta) {
        if (x == 0)
            while (r > y && l <= r)
                arr[r--] = k--;
        else
            while (l < y && l <= r)
                arr[l++] = k--;
        if (l > r)
            break;
    }
    if (sta.size() & 1)
        while (l <= r)
            arr[l++] = k--;
    else
        while (l <= r)
            arr[r--] = k--;
    println<int>(arr + 1, arr + n + 1);
    return 0;
}