Codeforces Round 793

發表於 更新於 分類於 ， Disqus： 文章字數： 3.7k 所需閱讀時間 ≈ 12 分鐘
E(排序,排列,拓扑排序,数学,无代码)F(网络流,二分图,排序,树状数组,扫描线, 前缀和,离线,差分)

E

题目

https://codeforces.com/contest/1682/problem/E

给一个不含重复数字的1~n的排列数组a

然后有人通过m次交换,让数组有序, 每次交换记录了被交换数字的坐标(i,j)

其中交换次数是最小次数

现在把交换的坐标对的顺序打乱了给你, 问怎么把交换数组重排序让它恢复, 保证合法

范围

n 2e5

m <= n-1

ai <= n

2s

256MB

题解

我的思路

先考虑自己会怎么交换,能够最小的次数

如果给你的数组, 有多个坐标和值构成环 , 那么最小次数 = (这些环长-1)的和

而每次交换一定让一个位置跑到合法的位置上,并且跑到合法以后不会再动这个位置

因此两个位置只会出现一次不会重复

或者从环的角度看,一次操作,就是 让环的一条边没了连接环的两端

所以考虑类似做拓扑排序, 每次选择一个 交换后有合法产生且能让 目标不再被操作的进行处理

问题在比赛时重复添加的bug没考虑清楚, 但即使修复了重复添加 依然wa5

官方

还好wa5数据小(当然比赛时看不了数据

1
2
3
4
5
4 3
2 3 4 1
1 2
2 4
3 4

果然我想的交换 虽然次数上表述是对的,但是操作上不一定是删了环上的边,

而是可以交换环上任意两点, 这样的话, 如果是环边,就是环-1

如果不是环边实际上是把环切割成两个小环,而总代价不会减少

而如果是这样,上面的实现当然也不对了,不再是交换后不会再交换了

举一个例子来说

a->b->c->d->e->f->a: 意思是位置a的值应该要去位置b, 位置b的值应该要去位置c …

那么如果交换了位置a和位置e

那么新的来说 位置e的值需要去位置b

也就是说当发生(位置i,位置j) 交换以后

i和j就不再属于同一个环了, 并且它们分别属于它们的来源的环

再去掉无关的抽象一次 x0->x1->....->y0->y1->..., 如果(x1,y1)交换, 则得到这样两个环 x0->x1) (....->y0->y1) (...

这样于是就有了 假设x和多个y换,如(x,y0),(x,y1)

x->....->y0->...->y1->...,

那么对于x来说,它和这些y的顺序一定是按箭头方向从近到远的

因为 如果先换了y1,就会变成x) (...->y0->...->y1) (..., 这样x都和y0不在同一个环上,再交换会合并环而不是拆环了

那么对于有x的所有交换就有了拓扑关系, 因为交换的对称性, 所有的交换序列都有了拓扑关系, 然后建立个拓扑图, 随便拓扑排序一下就好了

实现要素

找环, vis数组 + dfs 随便搞

把交换和环一起处理, vector<int> [idx] = 发生了的交换

环上可以做的是值 -> 下标

建立拓扑, 再从环中提取这些交换 并建立拓扑, 判断前后就是 (下标差 + 环长)% 环长 就知道前后了

拓扑排序, 维护入度计数 和 入度为0的点的数组

代码

无(鸽子)

F

题目

https://codeforces.com/contest/1682/problem/F

长n 数组a, 非严格递增排序

长n 数组b, bi != 0

一共q组询问,每次询问l,r, 保证sum(b[l..r]) == 0

b[l..r] 中 小于0的点作为左侧点, 大于0的点作为右侧点, 建立二分图

左侧点i 向 右侧点j 有一条 无限容量,每单位flow代价 为 abs(ai - aj) 的边

源点S, 汇点T

S->左侧i, cost = 0, 容量|bi|

右侧j->T, cost = 0, 容量|bj|

问你, 图的最大流的最小cost为多少, 答案 mod 1e9+7

范围

n 2e5

q 2e5

ai [0,1e9]

bi [-1e9,1e9], bi != 0

3s

256mb

题解

我的思路

而如果和为零,其实也就是说 负数和 = 正数和

那么建立的图,左右侧点连接的边都是无限容量, 而和源点汇点的边容量为 |bi|

所以其实最大流显然是 abs|负数和/或正数和|

换句话说 不需要S和T

就是每个左侧点发出|bi|的流量,每个右侧点接受|bi|的流量, 然后 左侧i到右侧j, 的无线容量的边,每单位流量 = |ai-aj|的代价

问最小代价

如果单次, 贪心

是不是左侧按照ai大小排序,右侧也按照ai大小排序

然后每次最小未输的左侧和右侧点进行1单位flow

证明, 如果有交差(左小到右大,右小到左大)那么必然交换1单位结果更小,而唯一不存在交叉的就是都按照ai排序

代价 = ai排序后 对应输送

或者看成所有的 |bi|个ai 进行排序分别得到l数组和r数组

然后答案 = sum{abs(r[i] - l[i])}

这样如果是单次查询就没啥东西

题目条件中说了ai非严格单调递增

因此不需要自己去排序了

但我并不知道怎么维护,能进行多次查询

官方

上面我的思路的结论是没问题的,但是在计算代价时实际上可以变成 不是去排序

初始化, 大于零和小于零bi绝对值和都为0, 分别记作 S+, S-,

然后遍历i从l到r, 每次遍历后更新S+,S-

如果 当前bi > 0 且 S+ >= S-, 那么说明 这一部分的ai在计算绝对值时全部取负号,因为它要和比它大的ai配

所以贡献为 -ai * |bi|

如果 当前bi > 0 且 S+ < S-, 那么说明 这一部分的ai在计算绝对值时, 有min((S-) - (S+), |bi|)个取负号, 剩下的取负号,因为它一部分和前面配对,一部分和后面配对

所以贡献为 ai * min((S-) - (S+),|bi|) - ai * (|bi| - min((S-)-(S+),|bi|)) = ai * (2min((S-)-(S+),|bi|) - |bi|)

如果 当前bi < 0 且 S+ <= S-, 那么说明 这一部分的ai在计算绝对值时全部取负号,因为它要和比它大的ai配

所以贡献为 -ai * |bi|,和上面同理

bi<0, S+ > S- 也是一样的

综上 都需要ai乘, 那么变化的是ai的贡献的次数, 而这个次数相关的就是 [b[l]..b[i-1]] 的正负绝对值和的差, 再和bi的大小关系

显然 这样的思考方式比我排序依次减和绝对值求和的效率高,因为对于每个i是O(1)的,总代价就是O(r-l), 而我的那样需要O(sum(|b[l..r]|))

而上面的 (S+)-(S-) 其实 等于 sum{b[l..i-1]}

后缀 变形(也可以前缀变形,同理, 计算[0..i]

如果按上述的方法,计算了 [i..n] 的结果, 记录为 res[i]

那么对于查询[l..r], 且 sum{b[l..r]} == 0, 那么答案就是 res[l] - res[r+1], 因为 [l..r]为0了, 所以从r+1开始向后运算时, 一定是正负绝对值差是0

当然这个直接暴力计算res的代价是$O(n^2)$

反过来从贡献角度考虑

a[i] 要 贡献给 res[j], j<=i

与 ai,bi, sum{b[j..i-1]} = pre[i-1] - pre[j-1] 有关

而对于具体的i, ai,bi,pre[i-1]是常量, pre[j-1]随着j变化

pre[i-1]-pre[j-1] 根据上面的推论, 有两头段会让a[i] 常数贡献, 中间一段与pre[j-1]线性关系

考虑 {pre[j-1],j } 二元组排序, 注意 j<=i 的范围限制

然后就变成 区间贡献统计, 区间线性贡献统计, 上树状数组或者线段树?

具体一点

前缀和$p_i = \sum_{k=1}^{i} b_k$

$j \le i$

$b_i > 0$ 时

若 $p_{i-1} - p_{j-1} \ge 0$, 有 $res_j += a_i * -b_i $

若 $p_{i-1} - p_{j-1} \le -b_i$, 有 $res_j += a_i * b_i $

若 $-b_i < p_{i-1} - p_{j-1} < 0$, 有 $res_j += a_i * ( 2p_{j-1} - 2p_{i-1} - b_i ) $

$b_i < 0$ 时

若 $p_{i-1} - p_{j-1} \le 0$, 有 $res_j += a_i * -b_i $

若 $p_{i-1} - p_{j-1} \ge - b_i$, 有 $res_j += a_i * b_i $

若 $ 0 < p_{i-1} - p_{j-1} < - b_i $, 有 $res_j += a_i * ( 2p_{j-1} - 2p_{i-1} - b_i ) $

问题是, 不只是需要 满足 大小关系, 还需要范围, 而且p的排序后下标就不再连续

先不考虑$j \le i$

建立个 下标数组, 按照$p_i$ 大小排序

那么 对于i 来说, 它对三个连续范围内每个贡献 常数($a_i \cdot -b_i$ 或 $ a_i \cdot b_i $ 或 $ a_i \cdot (-2p_{i-1} - b_i) $) / 线性函数的系数 $2a_i$

这样 当你要求具体 查一个位置的时候, 就树状数组 求点值

而这个操作 可以通过 差分数组+树状数组完成, 范围增加 = 范围起始点差值+, 范围结束点差值-, 单点值 = 前缀和

剩下的问题是如何控制$j \le i$

考虑扫描指针,先让所有点都贡献,然后 随着扫描指针从1到n,增加它的反贡献 相当于去掉它的贡献

这样的话我们就能算出每个res[i] = 单点常数 + 单点线性系数$\cdot p_{i-1}$

最后所有询问 直接 res[l] - res[r+1]

jiangly

似乎jiangly的比官方题解更简单, 他做了a数组的差分, 直接用差分和前缀b算的, 没有再用原始的b和a了

在白板上画了一下jiangly老哥的代码

发现jiangly老哥的想法其实 有点牛顿积分->勒贝格积分的味道

$i \in [l,r]$

我们以a[i]-a[i-1] 这段间隔贡献的长度来看

发现, 假设以j开头,那么这段的贡献的长度为$|p_{i-1} - p_{j-1}|$

鹅妹子嘤!!!!!

这直接和单个bi没关系,也不用大于零小于零分类和范围分类讨论了, 只和b前缀和 与 a差分相关了

而且简洁到 对ans[l..r]贡献就是$(a[i] - a[i-1]) * |p_{i-1} - p_{l-1}|$

注意这里和题解也不一样, 不需要先后缀数组res, 再去求差, 直接算每个位置对答案的贡献

剩下的就一样了

为了解决绝对值的问题, 对$p_i$排序

因为对于一个具体的查询来说 j是给定值,所以 你需要的是$(a[i] - a[i-1]) * p_{i-1}$的和 与 $a[i] - a[i-1]$ 的和

对于 $p_{i-1} > p_{j-1}$ 的 正贡献,而 $p_{i-1} < p_{j-1}$ 的负贡献

所以计算答案时, 从$p_i$ 从小到达算, 并且根据$p_i$的指针更新 每个位置i 贡献的正负

代码

https://codeforces.com/contest/1682/submission/158828392

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <bits/stdc++.h>
// jiangly
// https://codeforces.com/contest/1682/submission/158055817
// power 和 norm 和std有冲突
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
// 基于 mod P 的整数, structZ
constexpr int P = 1000000007;
// assume -P <= x < 2P
int mynorm(int x) {
  if (x < 0) {
    x += P;
  }
  if (x >= P) {
    x -= P;
  }
  return x;
}
template<class T>
T mypow(T a, ll b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}
struct Z {
  int x;
  Z(int x = 0) : x(mynorm(x)) {}
  Z(ll x) : x(mynorm(x % P)) {}
  int val() const {
    return x;
  }
  Z operator-() const {
    return Z(mynorm(P - x));
  }
  Z inv() const {
    assert(x != 0);
    return mypow(*this, P - 2);
  }
  Z &operator*=(const Z &rhs) {
    x = ll(x) * rhs.x % P;
    return *this;
  }
  Z &operator+=(const Z &rhs) {
    x = mynorm(x + rhs.x);
    return *this;
  }
  Z &operator-=(const Z &rhs) {
    x = mynorm(x - rhs.x);
    return *this;
  }
  Z &operator/=(const Z &rhs) {
    return *this *= rhs.inv();
  }
  friend Z operator*(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res *= rhs;
    return res;
  }
  friend Z operator+(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res += rhs;
    return res;
  }
  friend Z operator-(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res -= rhs;
    return res;
  }
  friend Z operator/(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res /= rhs;
    return res;
  }
  friend istream &operator>>(istream &is, Z &a) {
    ll v;
    is >> v;
    a = Z(v);
    return is;
  }
  friend ostream &operator<<(ostream &os, const Z &a) {
    return os << a.val();
  }
};
 
// 树状数组 0-index
template <typename T>
struct Fenwick {
  const int n;
  vector<T> a;
  Fenwick(int n) : n(n){
    a.resize(n);
  }
  // [x] += v
  void add(int x, T v) {
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1] += v;
    }
  }
  // [0..x)
  T sum(int x) {
    T ans = 0;
    for (int i = x; i > 0; i -= i & -i) {
      ans += a[i - 1];
    }
    return ans;
  }
  // [l,r)
  T rangeSum(int l, int r) {
    return sum(r) - sum(l);
  }
};
 
int main() {
 
  int n = read(), q = read();
 
  vector<int> a(n);
  vector<ll> b(n + 1);
  rep(i,0,n) a[i] = read();
  // 倒序做差分
  per(i,1,n) a[i] -= a[i - 1];
  rep(i,1,n+1) {
    b[i] = read();
    // 前缀和
    b[i] += b[i - 1];
  }
  // 离线
  vector<array<ll, 4>> qry(q); // 查询 按照 {b[l-1],l-1,r,qidx} 排序
  rep(i,0,q) {
    int l = read()-1, r = read();
    qry[i] = {b[l], l, r, i};
  }
  sort(qry.begin(), qry.end());
 
  // https://en.cppreference.com/w/cpp/algorithm/ranges/iota
  // https://www.cplusplus.com/reference/numeric/iota/
  // 按照bi 前缀和 大小排序下标
  vector<int> p(n);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int i, int j) { return b[i] < b[j]; });
 
  Fenwick<Z> s(n), c(n);
 
  rep(i,0,n) {
    // 先全部正贡献
    s.add(i, Z(b[i]) * a[i]);
    c.add(i, a[i]);
  }
  vector<Z> ans(q);
 
  int j = 0;
  for (auto [v, l, r, i] : qry) {
    while (j < n && b[p[j]] <= v) { // 根据 bi 前缀大小 决定贡献正负
      int k = p[j++];
      // 树状数组不支持修改, 只支持增量 ,实际是改成负贡献
      s.add(k, -2*Z(b[k]) * a[k]);
      c.add(k, -2*a[k]);
    }
 
    ans[i] = s.rangeSum(l, r) - c.rangeSum(l, r) * v;
  }
 
  for (auto x : ans) {
    printf("%d\n",x.val());
  }
  return 0;
}

总结

E 的关键在于

不只有相邻的可以换, 不相邻的同环上也可以换(Wa5, 这点还是应该枚举稍微大一点的, 其实wa5 的点数才4

交换同环 = 拆环, 交换异环 = 合环

而交换两点,** 这两点分别属于它们前个点的环** 从而推得 同点和其它点多次交换时的先后顺序

有了先后顺序的逻辑,后面拓扑就无脑做了

F

简化的部分做了

但是 在排序对应 相减 取 绝对值 求和的部分, 没有想到怎么转换成 正负号标记, 还是说明绝对值相关知识点不够熟练

而即使看题解时 知道了这样转化, 也没有变成后缀来求的思路, 还在想分治

而且后缀的思路也是提供一个叫 无效答案同规则的差是可以得到有效答案的, 就像函数补充中间点一样

看jiangly的代码, 一个是 基于mod的 struct,可以让逻辑代码里完全不需要写mod 也不用担心写掉, 减少心智负担

第二个是 没有 using namespace std 减少碰撞

iota 可以填数组, sort+lambda 简化排序

另外就是 using namespace std; 是个坏习惯, 比如这里norm和power就有冲突

参考

官方

jiangly