集训队论文-基础排序算法

AK-dream

发布于：2020年1月26日

1. 排序的简单应用

一些题目需要排序用来辅助解决问题

std::sort就完事了不需要手写而且肯定比你手写跑得快

放一个手动快速排序的代码及注释

void quicksort(int l, int r) {
	if (l >= r) return;
	int i = l, j = r, base = a[l]; //取最左边的数为基准数(取哪个都行);
	while (i < j) {
		while (i < j && a[j] >= base) j--; //找到右起第一个小于基准数的数 
		while (i < j && a[i] <= base) i++; //找到左起第一个大于基准数的数 
		if (i < j) swap(a[i], a[j]); //交换两数 
	}
	swap(a[l], a[i]); //把基准数换到中心 此时[l,r]内基准数左边的所有数小于基准数 基准数右边的所有数大于基准数
	quicksort(l, i - 1); quicksort(i + 1, r); //分别向左右递归 
}

平均复杂度$O(n\ log\ n)$最坏复杂度$O(n^2)$

想到一个很经典的利用排序辅助解决问题的算法：莫队

模板例题 #240 小Z的袜子

简单来说就是暴力维护双指针指向当前查询区间的左右端点每次左或右指针可以向左或向右移动一格同时更新当前区间的答案

可以给询问排序如果直接先按左端点排再按右端点排依然容易被卡掉

比如询问[2,2][3,1000][4,4][5,2000][6,6] 如果按照[2,2][4,4][6,6][3,1000][5,2000]的顺序查询显然右指针会少移动很多次

所以这个暴力的思路就是给左端点分块左端点在同一个$\sqrt{n}$块中的询问优先按右端点排序否则才是优先按左端点排序

这样显然会更容易得到上面那个例子中的第二种排序复杂度有所降低据说这个复杂度是大约$O(n\sqrt{n})$的足以通过此题

只是在这里介绍一下莫队算法这个题具体怎么用莫队维护神犇们肯定一眼就看出来了 (突然发现OJ里已经有这题了)

此题代码实现

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

ll read() {
	ll x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
	return x * f;
}

struct query{
	ll l, r, id;
} q[50005];

ll n, m, bl;
ll c[50005];
ll cnt[50005], ans, nl, nr;
ll ansx[50005], ansy[50005];

inline bool cmp(query a, query b) {
	return a.l / bl == b.l / bl ? a.r < b.r : a.l < b.l;
}

inline void add(ll x) {
	cnt[x]++;
	if (cnt[x] > 1) ans = ans - (cnt[x]-1) * (cnt[x]-2) + (cnt[x]) * (cnt[x]-1);
}

inline void del(ll x) {
	cnt[x]--;
	if (cnt[x] > 0) ans = ans - (cnt[x]) * (cnt[x]+1) + (cnt[x]-1) * (cnt[x]); 
}

inline void update(ll l, ll r) {
	while (nl < l) del(c[nl++]);
	while (nl > l) add(c[--nl]);
	while (nr < r) add(c[++nr]);
	while (nr > r) del(c[nr--]);
}

inline void getans(ll x, ll y, ll id) {
	if (x == 0) {
		ansx[id] = 0; ansy[id] = 1;
		return;
	}
	ll gcd = __gcd(x, y);
	x /= gcd; y /= gcd;
	ansx[id] = x; ansy[id] = y;
}

int main() {
	n = read(); m = read();
	bl = sqrt(n);
	for (ll i = 1; i <= n; i++) {
		c[i] = read();
	}
	for (ll i = 1; i <= m; i++) {
		q[i].l = read(); q[i].r = read();
		q[i].id = i;
	}
	sort(q+1, q+m+1, cmp); nl = q[1].l, nr = q[1].r;
	for (ll i = q[1].l; i <= q[1].r; i++) {
		add(c[i]);
	}
	getans(ans, (nr-nl+1)*(nr-nl), q[1].id);
	for (ll i = 2; i <= m; i++) {
		update(q[i].l, q[i].r);
		getans(ans, (nr-nl+1)*(nr-nl), q[i].id);
	}
	for (ll i = 1; i <= m; i++) {
		printf("%lld/%lld\n", ansx[i], ansy[i]);
	}
	return 0;
}

由此可以看出通过排序改变询问顺序有时候可以辅助解题

排序也经常用于数据离散化

感觉扯得有点多了跑题了

2.逆序对

逆序对定义为序列$a[1\dots n]$中的一对下标$(i,j)$满足$1\le i < j \le n$且$a[i] > a[j]$。逆序对和排序算法有着密切关系。

例题1 #804 北冥有鱼

这道题我们就可以从逆序对的角度考虑

发现每次交换$a[i]$与$a[i+1]$只有这两个元素的相对顺序发生了变化

根据逆序对的定义只有两个元素的相对顺序发生了变化才有可能新产生或减少逆序对

所以每次交换可能导致3种结果:
1.$a[i]<a[i+1]$逆序对增加1
2.$a[i]>a[i+1]$逆序对减少1
3.$a[i]=a[i+1]$逆序对数量不变

所以我们得到一个最优的交换策略每次找到一对$a[i]>a[i+1]$并交换
使逆序对减少1

容易发现当找不到这样一对$a[i]>a[i+1]$时数组必已有序

因为每次交换使逆序对数量-1 所以最小交换次数就是原数组的逆序对数量

如何求逆序对数量？

1.树状数组
将数组离散化，枚举$a[1\sim n]$，每次查询现在树状数组中有多少个元素大于$a[i]$，然后将$a[i]$放进树状数组。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;
typedef long long ll;

ll n, a[500005], srt[500005], mx, ans;
ll tr[500005];

inline void update(ll ind, ll x) {
	while (ind <= n) {
		tr[ind] += x; ind += lowbit(ind);
	}
}

inline ll getsum(ll ind) {
	ll ret = 0;
	while (ind) {
		ret += tr[ind]; ind -= lowbit(ind);
	}
	return ret;
}

int main() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]); srt[i] = a[i];
	}
	sort(srt+1, srt+n+1); mx = unique(srt+1, srt+n+1)-srt-1;
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(srt+1, srt+mx+1, a[i])-srt;
	}
	for (int i = 1; i <= n; i++) {
		ans += getsum(mx) - getsum(a[i]);
		update(a[i], 1);
	}
	printf("%lld\n", ans);
	return 0;
}

2.归并排序
不再阐述见代码

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

int n, a[500005], tmp[500005];
long long ans; 

void merge_sort(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	merge_sort(l, mid); merge_sort(mid+1, r);
	int i = l, j = mid + 1, k = l;
	while (i <= mid && j <= r) {
		if (a[i] <= a[j]) {
			tmp[k++] = a[i++];
		} else {
			tmp[k++] = a[j++];
			ans += mid - i + 1;
		}
	}
	while (i <= mid) tmp[k++] = a[i++];
	while (j <= r) tmp[k++] = a[j++];
	for (i = l; i <= r; i++) a[i] = tmp[i];
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	merge_sort(1, n);
	printf("%lld\n", ans);
	return 0;
}

时间复杂度均为$O(n\ log_2 n)$。

例题2 #805 巨神JZC暴力切题

发现$q$比较小，$m$则比较巨大

$10^6$次排序很有可能在前$100$次后整个数组就基本有序后面的每次排序如果还是用$O(n\ log\ n)$的时间处理一段可能已经有序的区间会浪费很多时间

所以想到可以像#804 北冥有鱼一样用消除逆序对的方法来排序

每次找到$[l_i,r_i]$区间内所有的$a[i-1]>a[i]$将每一对互换

因为逆序对的数量最多有$\frac{n(n-1)}{2}$个所以总的互换次数不会超过$n^2$此题$n\le 1500$绰绰有余总比$O(m\cdot n\ log\ n)$要好

如何快速找到区间内的$a[i-1]>a[i]$?

维护一个平衡树或std::set，每次询问初始时扫描一遍将所有$a[i-1]>a[i]$的位置放入其中每次排序操作时只需要一直查找第一个大于等于$l_i$的位置(如果该位置已经大于$r_i$就可以结束此次排序) 互换这个位置上的$a[i-1],a[i]$，然后检查$a[i-2],a[i-1]$及$a[i],a[i+1]$的大小关系并在set中更新

最后如果set为空，则表示$a$数组已不存在逆序对，输出Accepted，否则输出Wrong Answer。

时间复杂度$O(q(m+n^2)\cdot \log_2 n)$

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

int n, m, q;
int a[2005], l[1000005], r[1000005]; 
set<int> s;

int main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &l[i], &r[i]); l[i] = max(l[i], 1); r[i] = min(r[i], n);
	}
	for (int i = 1; i <= q; i++) {
		s.clear();
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[j]);
			if (a[j-1] > a[j]) {
				s.insert(j-1);
			}
		}
		
		for (int j = 1; j <= m; j++) {
			int pos = 0; set<int>::iterator it; 
			do {
				it = s.lower_bound(l[j]); pos = *it;
				if (it == s.end() || pos >= r[j]) break;
				swap(a[pos], a[pos+1]); s.erase(pos);
				if (pos >= 2) {
					if (a[pos-1] <= a[pos]) {
						s.erase(pos-1);
					} else {
						s.insert(pos-1);
					}
				}
				if (pos <= n - 2) {
					if (a[pos+1] <= a[pos+2]) {
						s.erase(pos+1);
					} else {
						s.insert(pos+1);
					}
				}
			} while (1);
		}
		if (!s.empty()) {
			puts("Wrong Answer");
		} else puts("Accepted");
	}
	return 0;
}

3. 01序列

01序列是指序列元素都为$0$或$1$的序列。这种序列有一些美♂妙性质可以帮助我们解题。

例题1 #807 苦练七十二变，笑对八十一难

和上面那道 #805 巨神JZC暴力切题有点像也是多次排序直接暴排肯定TLE

很遗憾，对于这题$n,m\le 50000$，消逆序对的处理速度依然不够快。

有什么东西处理区间操作比较快呢？当然是我们的线段树$Segment\ Tree$啦！

然而$Segment\ Tree$并不会区间排序呢

但是如果序列中只存在$0$或$1$，线段树还是可以做到的

以升序排序为例，具体地说，每次查询区间中共有多少个$1$(区间求和)，记为$num$，然后将区间后$num$个修改成$1$，前面剩下的修改成$0$(区间修改)。就相当于给区间内的$0,1$做了升序排序了

而且线段树修改有着极其优秀的时间复杂度$O(log\ n)$，比std::sort的$O(n\ log\ n)$比起来不知道快到哪里去了，和倍增谈笑风生。

所以对于这题我们可以得到一个极其诡异的解法：

二分答案$mid$(这也能二分？)，将原数组中小于mid的设成$0$，剩下的设成$1$。然后用线段树来排这$m$次序，排完后看看第$k$个是$0$还是$1$，如果是$0$表示$mid$大了，否则是$mid$小了。

时间复杂度$O(n\ log\ n\ +\ m\ log^2\ n)$;

p.s.最好再加个离散化 ~~不然会被我卡掉~~

#include <bits/stdc++.h>
#define lson ind<<1
#define rson ind<<1|1
using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
	return x * f;
}

int t, n, m, k, a[100005], srt[100005], mx, tp[100005], le[100005], ri[100005], tmp[100005]; 

namespace Segtree{
	//线段树自己写去
}

using namespace Segtree;

bool check(int x) {
	for (int i = 1; i <= n; i++) tmp[i] = (a[i] >= x);
	build(1, 1, n); 
	for (int i = 1; i <= m; i++) {
		int num = query(1, le[i], ri[i]);
		if (!tp[i]) {
			update(1, le[i], ri[i]-num, 0); update(1, ri[i] - num + 1, ri[i], 1);  
		} else {
			update(1, le[i], le[i] + num - 1, 1); update(1, le[i] + num, ri[i], 0);  
		}
	}
	return query(1, k, k) == 1;
}

int main() {
	t = read();
	while (t--) {
		n = read(); m = read();
		for (int i = 1; i <= n; i++) a[i] = srt[i] = read();
		for (int i = 1; i <= m; i++) tp[i] = read(), le[i] = read(), ri[i] = read();
		k = read();
		sort(srt+1, srt+n+1); mx = unique(srt+1, srt+n+1)-srt-1;
		for (int i = 1; i <= n; i++) a[i] = lower_bound(srt+1, srt+mx+1, a[i])-srt;
		int l = 1, r = mx, mid, ans = 0;
		while (l <= r) {
			mid = (l + r) >> 1;
			if (check(mid)) {
				ans = mid; l = mid + 1;
			} else r = mid - 1;
		}
		printf("%d\n", srt[ans]);
	} 
	return 0;
}

这道题的这个思想似乎经常用于中位数有关的题目

又加了一道这个思路的题#808 孔明の金字塔

先存一下相似问题
[CQOI2009]中位数

例题2 #806 巨神JZC巧妙切题

先普及一下像题目这样的，对一个序列依次进行$m$次这种比较交换操作叫做一个 比较网络 。一个总能给$n$个元素正确排序的 比较网络 叫做一个 排序网络 。

这道题其实就是给你一个比较网络，问你对于一个随机的$n$排列，它有多大几率不能正确排序。

先来思考一下如何判定一个比较网络是否是一个排序网络。

如果暴力枚举排列时间复杂度是$O(n\cdot n!)$的，还可以优化一下

实际上只需要枚举$2^n$种01序列判断是否能被这个比较网络成功排序就行了

简单的证明：假设有一个$n$排列不能被成功排序，则操作后必然存在至少一组逆序对$i<j,a[i]>a[j]$。

设$a[j]=x$，将排列中所有大于$x$的数设为$1$，小于等于的设为$0$。将原排列按这样变换，得来的01序列作为输入，则输出$a[i]$的位置上会是$1$，$a[j]$的位置上会是$0$。

所以当这个排列变换得来的01序列不能够被成功排序时，这个排列也一定不能被成功排列。

实际上，每个$n$排列对应着$n$个01序列(把$a[1\sim n]$中任意一个设为$x$都能得到一个)，当且仅当这$n$个01序列都能被这个比较网络成功排序时，这个$n$排列能被成功排序。

如何求有多少$n$排列不能被排序？

预处理出所有可以被排序的01序列，一个可以被排序的$n$排列实际上就对应着一条从$00\dots0$到$11\dots1$的路径，其间只能经过那些可以被排序的01序列。

这条路径上每个点的意义是什么呢？假设$n=5$，从$00000$到$01000$就意味着将数字$5$放在了排列的第二位，$01000$就代表着$x=4$($x$的意义见上文)时变换得来的01序列。同理，从$01000$到$01100$就意味着将数字$4$放在了排列的第三位。这样一直到$11111$就对应了一个$n$排列。

这个计数问题显然可以用$O(n\cdot 2^n)$的时间复杂度内用一个状压DP解决

~~想改改这题题面竞标中~~

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
	return x * f;
} 

int n, m, l[30], r[30];
ll dp[2000005], wa, tot;
bool ok[2000005];

inline void getnum(int x, int *num) {
	for (int i = 1; i <= n; i++) {
		num[i] = (x >> (n - i)) & 1;
	}
}

inline ll fpow(ll x, ll t) {
	ll ret = 1;
	for (; t; x = x * x % mod, t >>= 1) if (t & 1) ret = ret * x % mod;
	return ret;
}

inline bool check(int x) {
	int num[30] = {0};
	getnum(x, num);
	for (int i = 1; i <= m; i++) {
		if (num[l[i]] > num[r[i]]) swap(num[l[i]], num[r[i]]);
	}
	for (int i = 2; i <= n; i++) {
		if (num[i] < num[i-1]) {
			return false;
		}
	}
	return true;
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		l[i] = read(); r[i] = read(); 
	}
	for (int i = 0; i <= (1 << n) - 1; i++) {
		ok[i] = check(i); 
	}
	dp[0] = tot = 1; 
	for (int i = 1; i <= n; i++) tot = tot * i % mod; 
	for (int i = 1; i <= (1 << n) - 1; i++) {
		if (!ok[i]) continue;
		for (int j = 1; j <= n; j++) {
			if (i & (1 << (j-1))) {
				dp[i] = (dp[i] + dp[i-(1<<(j-1))]) % mod;
			}
		} 
	} 
	wa = (tot - dp[(1<<n)-1] + mod) % mod;
	printf("%lld\n", wa * fpow(tot, mod-2) % mod);
	return 0;
}

在遇到一个排序问题不知道怎么做时，不妨试着从逆序对或01序列的角度思考一下

然后我们现在再回去看看#805 巨神JZC暴力切题

第8个点只有0和1 看一下怎么做

设$S_i$表示一个01序列的集合其中的每个01序列$p\in S_i$经过第$i+1\sim m$次排序都能被完全排好序

这个集合似乎是无比巨大的但是我们还是考虑下怎么递推得到每个$S_i$

首先$S_m$中肯定只有一个序列就是那个被完全排好序的然后$S_0$就代表着所有能被这$m$次操作完全排好序的01序列的集合要是求出这个回答询问就只需要判断一个询问序列在不在$S_0$里就行了

有哪些元素经过第$m$次排序能得到那个完全排好的序列，即$S_{m-1}$有哪些元素呢

显然把$S_m$里那个唯一的序列记为$P$那么随机打乱$p[l_i\dots r_i]$得到的所有序列都属于$S_{m-1}$

扩展到每个$i$那么对于每个$p\in S_i$如果$p[l_i\dots r_i]$有序那么就把随机打乱$p[l_i\dots r_i]$得到的所有结果加入$S_{i-1}$

这个的大小是指数级的我们要想办法用更小的空间表示这些集合

定义两个01序列之间的大小关系为它们字典序的大小关系

即$p<q$当且仅当$\forall i \in [1,k)\ p[i]=q[i]$且$p[k]<q[k]$

我们想要给每个$S_i$找到一个有代表性的01序列$a_i$使得$\forall p \in S_i$都有$p\le a_i$即$a_i$是$S_i$中最大的01序列

下面证存在这样的$a_i$并且对于所有$p\le a_i$都有$p\in S_i$

定义$f(p,l,r)$为将$p[l\dots r]$升序排序得到的新序列，$g(p,l,r)$为将$p[l\dots r]$降序排列得到的新序列

~~不妨通过结论推过程~~ 由于$S_m$就一个元素所以$a_m$就是那个元素对于剩下的$a_i$有$a_i=g(a_{i+1},l_{i+1},r_{i+1})$

性质1：$f(p,l,r)\le p$，$p\le g(p,l,r)$

性质2：令$b=f(a,l,r),c=g(a,l,r)$则$g(a,l,r)=g(b,l,r)=g(c,l,r)$，$f(a,l,r)=f(b,l,r)=f(c,l,r)$

性质3：若$a\le b$那么$f(a,l,r)\le f(b,l,r)$，$g(a,l,r)\le g(b,l,r)$

都很容易得到吧。。。

证明1：如果$p\in S_i$那么$p\le a_i$

如果$p\in S_i$设$q=f(p,l_{i+1},r_{i+1})$为$p$经过第$i+1$次排序得到的结果有$q\in S_{i+1}$

那么有$q\le a_{i+1}$

根据性质2有$g(p,l_{i+1},r_{i+1})=g(q,l_{i+1},r_{i+1})$记它为$r$根据性质1有$p\le r$

根据性质3 因为$q\le a_{i+1}$所以有$r=g(q,l_{i+1},r_{i+1})\le g(a_{i+1},l_{i+1},r_{i+1})$

由定义得$g(a_{i+1},l_{i+1},r_{i+1})$其实就是$a_i$所以$r\le a_i$

又因为$p\le r$所以$p\le a_i$证毕

证明2：如果$p\le a_i$那么$p\in S_i$

设$q=f(p,l_{i+1},r_{i+1})$为$p$经过第$i+1$次排序得到的结果设$r=f(a_i,l_{i+1},r_{i+1})$

根据性质3 因为$p\le a_i$所以$q=f(p,l_{i+1},r_{i+1})\le r=f(a_i,l_{i+1},r_{i+1})$

又因$a_i=g(a_{i+1},l_{i+1},r_{i+1})$根据性质2得$r=f(a_{i+1},l_{i+1},r_{i+1})$再根据性质1得$r\le a_{i+1}$所以$q\le r\le a_{i+1}$所以$q\in S_{i+1}$

也就是说$q$经过第$i+2\sim m$次排序能被完全排好序又因为$q$就是$p$经过第$i+1$次排序得来的所以$p$经过第$i+1\sim m$次排序也能被完全排好序

所以$p\in S_i$证毕

那么我们现在就知道了集合$S_i$正好由小于等于$a_i$的所有01序列构成所以我们只需要按照上面说的递推$a_i$的方法求出$a_0$

然后对于每个询问判断输入的01序列是否小于等于$a_0$即可这个显然是可以$O(n)$的

预处理$a_0$需要$m$次降序排序这个用线段树搞一搞或者用上面40分做法的消除逆序对都可以

时间复杂度$O((m+n^2)\log n + qn)$

打了这些基础之后就可以来推出满分算法了

不妨假设询问给出的数组$b$是一个$n$排列如果不是的话离散化一下就好了显然不会对答案造成影响

定义$h_k(b)$表示把$b$这个$n$排列中$\ge k$的数全部设为$1$其余设为$0$得到的01序列

那么这$m$次操作必须把$k\in [2,n]$的每个$c_k$都成功排序才一定能把$b$完全排好序

先看看怎么求得刚才第8个点算法里的$a_0$

看起来我们要对于每个$k$算1次$a_0$了但是其实不需要

我们可以做一件等价的事情

把一个初始时为$1,2,3,\dots,n$的序列$p$按照$m\dots 1$的顺序每次将$p[l_i\dots r_i]$降序排序，就和上题一样

然后最后$h_k(p)$就是$k$对应的$a_0$了

那么一个询问序列$b$可以被排序的条件就是对于$k\in [1,n]$都有$h_k(b)\le h_k(p)$

再来看看刚才我们对于01序列定义的小于运算

换个表示方法两个01序列$x,y$有$x\le y$当且仅当对于每个$i\in [1,n]$都有$\sum\limits_{j=1}^{i}x[j]\le \sum\limits_{j=1}^{i}y[j]$

即$\sum\limits_{j=1}^{i}y[j] - \sum\limits_{j=1}^{i}x[j]\ge 0$很显然吧就不多解释了

现在我们要判断是否对于$k\in [1,n]$都有$h_k(b)\le h_k(p)$

注意到$h_k(b)$到$h_{k+1}(b)$只有一个$1$变成了$0$$h_k(p)$到$h_{k+1}(p)$也是所以我们可以用线段树维护这个东西

线段树存储$h_k(b),h_k(p)$两个01序列前缀和的差那么$k$增大$1$每次就是进行两次区间修改然后再查一下最小值判断所有前缀和是否都非负即可

预处理$p$还是要用上面消逆序对的方法

时间复杂度$O(n^2+m+qn)\log n$

题解很毒瘤代码很简短

(由于是自己乱写的也不知道有没有写错欢迎巨佬来hack我)

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

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
	return x * f;
} 

int n, m, q;
int a[1505], b[1505], posa[1505], posb[1505], le[1000005], ri[1000005];
set<int> s;

void my_sort() {
	for (int j = m; j >= 1; j--) {
		int pos = 0; set<int>::iterator it; 
		do {
			it = s.lower_bound(le[j]); pos = *it;
			if (it == s.end() || pos >= ri[j]) break;
			swap(a[pos], a[pos+1]); s.erase(pos);
			if (pos >= 2) {
				if (a[pos-1] >= a[pos]) {
					s.erase(pos-1);
				} else {
					s.insert(pos-1);
				}
			}
			if (pos <= n - 2) {
				if (a[pos+1] >= a[pos+2]) {
					s.erase(pos+1);
				} else {
					s.insert(pos+1);
				}
			}
		} while (1);
	}
}

struct Segtree{
	struct segtree{
		int l, r, mn, tag;
	} tr[100005];
	#define lson ind<<1
	#define rson ind<<1|1
	
	void build(int ind, int l, int r) {
		tr[ind].l = l, tr[ind].r = r, tr[ind].tag = 0, tr[ind].mn = 0;
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(lson, l, mid); build(rson, mid+1, r);
	}	
	
	void pushdown(int ind) {
		if (!tr[ind].tag) return;
		int v = tr[ind].tag; tr[ind].tag = 0;
		tr[lson].mn += v; tr[rson].mn += v;
		tr[lson].tag += v; tr[rson].tag += v; 
	} 
	
	void update(int ind, int x, int y, int v) {
		int l = tr[ind].l, r = tr[ind].r;
		if (x <= l && r <= y) {
			tr[ind].mn += v; tr[ind].tag += v;
			return;
		}
		pushdown(ind);
		int mid = (l + r) >> 1;
		if (x <= mid) update(lson, x, y, v);
		if (mid < y) update(rson, x, y, v);
		tr[ind].mn = min(tr[lson].mn, tr[rson].mn);
	}
}T;

pair<int, int> tmp[1505];

inline void init() {
	for (int i = 1; i <= n; i++) tmp[i] = make_pair(b[i], i);
	sort(tmp+1, tmp+n+1);
	for (int i = 1; i <= n; i++) b[tmp[i].second] = i;
	for (int i = 1; i <= n; i++) posb[b[i]] = i;
}

int main() {
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		le[i] = read(); ri[i] = read();
	}
	for (int i = 1; i <= n; i++) a[i] = i;
	for (int i = 1; i < n; i++) s.insert(i);
	my_sort();
	for (int i = 1; i <= n; i++) posa[a[i]] = i;
	for (int i = 1; i <= q; i++) {
		for (int j = 1; j <= n; j++) b[j] = read();
		init();
		T.build(1, 1, n);
		bool ok = 1;
		for (int j = 2; j <= n; j++) {
			T.update(1, posb[j-1], n, 1);
			T.update(1, posa[j-1], n, -1);
			if (T.tr[1].mn < 0) {
				ok = 0;
				break;
			}
		}
		if (ok) puts("Accepted");
		else puts("Wrong Answer");
	}
	return 0;
}

完结撒花！

更新于：2020年10月8日

随机序列[SHOI2018]

【题目描述】你的面前有$n$个数排成一行，分别为$a_1, a_2, \dots, a_n$。你打算在每相邻的两个$a_i$ 和$a_{i+1}$间都插入一个加号、减号或者乘号。那么一共有$3^...

字符串树「JSOI2015」

【题目描述】萌萌买了一颗字符串树的种子，春天种下去以后夏天就能长出一棵很大的字符串树。字符串树很奇特，树枝上都密密麻麻写满了字符串，看上去很复杂的样子。字符串树本质上还是一棵树，即N个节点N-1...