AK-dream

1. 排序的简单应用

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

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

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

1
2
3
4
5
6
7
8
9
10
11
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里已经有这题了)

此题代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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]$放进树状数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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.归并排序
不再阐述 见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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.最好再加个离散化 不然会被我卡掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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$排列不能被成功排序,则操作后必然存在至少一组逆序对$ia[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解决

想改改这题题面 竞标中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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我)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#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;
}

完结撒花!


 评论