YeXiaoRain Blog

發表於 更新於 分類於 Disqus： 文章字數： 781 所需閱讀時間 ≈ 3 分鐘
P5.MINXORSEG(XOR,fenwick)

MINXORSEG

评分 3087, tourist 也没做出

给你长度n数组, q个询问,每次问区间[l,r]中任意两个数的异或的最小值

范围

n 2e5

q 2e5

ai 2^30

3s

400MB

题解

离线, 按查询的右端点排序

简单的扫描加入 是n方?

x=a[l]^a[r]

假设x最高位1在p位,那么高于p的bit,a[l]和a[r]一样

如果[l..r] 之间有同样的高于p的bit和它们一样的t,那么(l,r)这一对一定不是最小值,因为 (l,t) 或 (t,r) 比它小

如果区间有3个高w位一样,那么答案至少是高w位为0, 所以答案最小的只存两个高w一样,或者存在两个相等的数

这个观察很神奇,也就是说如果ai和aj高w位相同,那么要让它们可能是答案的必要条件是,它们中间没有高w位和它们相同的

换句话说, a[i]如果和它前面某个a[j]高w相同,贡献了最小xor,那么a[i]的w相同的前面最近的就是a[j]

所以直接记录每个数前面和它高0,1,2,3..位相同的最近的下标即可, 这可以简单的排序记录

最后扫描+fenwick一下

其中把每对的左点为index,异或和为值,做后缀min fenwick 就可以了, 这样每次询问就是[l… 中的最小值

代码

https://www.codechef.com/viewsolution/67421139

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const ll INF = 0x3f3f3f3f3f3f;

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll a[200010];
int idxs[200010];

struct fenwick_tree {
  vector<ll> bit;
  int n;
  fenwick_tree(int n) : n(n) {
    bit = vector<ll> (n + 1, INF); // 后缀min fenwick
  }
  void update(int u, ll v) {
    for (u++; u > 0; u -= u & -u) bit[u] = min(bit[u], v);
  }

  int query(int u) {
    ll r = INF;
    for (u++; u <= n; u += u & -u) r = min(r, bit[u]);
    return r;
  }
};

int main() {
  int n = read();
  int q = read();
  vector<vector<int>> lst(n);
  vector<vector<pair<int, int>>> que(n);
  rep(i,0,n) a[i] = read();
  rep(b,0,30+1) { // 低位到高位
    // 按高 30-p 位排序
    iota(idxs,idxs+n,0);
    sort(idxs,idxs+n,[=](int i,int j){return make_pair((a[i] >> b),i) < make_pair((a[j] >> b),j); });
    rep(i,1,n) {
      if ((a[idxs[i]] >> b) == (a[idxs[i-1]] >> b)) { // 高位相同,建立可能对最小值贡献的关系
        lst[idxs[i]].push_back(idxs[i-1]);
      }
    }
  }
  vector<int> ans(q);
  rep(i,0,q) {
    int l = read() - 1;
    int r = read() - 1;
    que[r].push_back({l, i});
  }
  fenwick_tree fen(n);
  rep(i, 0, n) {
    for (int v : lst[i]) fen.update(v, a[v] ^ a[i]);
    for (auto [l, ind] : que[i]) ans[ind] = fen.query(l);
  }
  for(auto v:ans) printf("%d\n", v);
}

// n 2e5 个数
// q询问,2e5
// 查区间内 最小的两个值的 xor

代码

总结

MINXORSEG

这个观察最小的可能贡献很厉害啊, 应该属于xor的一个神奇的知识点了?

另一个就是, 这种非统计的, 最大最小也是可以从”可能贡献”的角度去思考,这个我没有思路过,学到了

fenwick这个还有后缀写法,不需要做颠倒原数组的动作

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 745 所需閱讀時間 ≈ 2 分鐘
总体观察,数学,贪心

E(总体观察,数学),F(贪心)

E

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

给你一个矩阵,每个数字都不相同

然后让你依次取1,2,3,4,… 取完所有

取的块需要和之前取过的至少一个4临

直接可取输出0

需要还是交换两个位置(可以不相邻)后可取,输出1 方案数

还是都不行输出2

范围

矩阵大小4e5

2s

256MB

题解

我的思路

0很好判断,vis染色+bfs

其实就是1的时候怎么算个数

不妨设按找上述方法最开始失败的是x

意味着, 小于x的连在一起了,

那么有两种方案

  1. 交换x和小于x的外边界,这样小于等于x就连在一起了,
  2. 交换小于x的某一个和x的四临

但是这两种如果一个一个检验是时间复杂度会炸掉的

考虑可交换的,对于第一种没有什么思路

对于第二种,你可以考察每个依赖于它的是否仅依赖于它, 但也不一定

1
2
3
4
145
2.6
3?7
.8.

比如上面这样,7仅依赖于6,而6也可以移动

不知道怎么搞了

题解

不要看一步一步,看总览性质

如果一个位置，它的四个邻居有比他小的，那么它就能连到小于它的数。矩阵为可遍历当且仅当所有点（除了1）的四个邻居都有比他小的。

这归纳法可证明

所以判断可行,也不再需要vis+bfs, 而直接判断count(badpos)== 0

所以badpos 需要交换它或者它的邻居

两两不相同,显然badpos不相邻, 因为badpos需要小于4临, 说明4临都不是badpos

两两不同,说明交换以后的两个位置,一个比原来大,一个比原来小,

比原来大的位置4邻之前一定不是badpos,

比原来小的本身一定不是badpos

综上, badpos最多5个, 一个中心一个4临

5x5x4, 种

代码

无

F

题目

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

2 * n 的01矩阵,两个

每次交换第一个中相邻位置的01,求最小次数得到第二个矩阵

范围

n 2e5

1s

256mb

题解

我的思路

写了个假的

两个变量记录未匹配的,然后进入则+,退出则-

发生 一正一负则消耗1抵消

竟然官方数据弱还过了system test

然后有错误样例

1
2
3
4
5
0 1 0
1 0 0

0 1 0
0 0 1

我的匹配会

1
2
3
4
5
0 b 0
a 0 0

0 a 0
0 0 b

代价为4, 最小的是2

官方

直接可配消耗掉即可…….

代码

无

总结

E

这个总体观察没想到, 一直在想细节的步, 总体只想到vis+bfs 而不是这个充分性质

jiangly 也TLE了好像

F

贪心细节还是没想到啊

参考

官方

發表於 更新於 分類於 Disqus： 文章字數： 434 所需閱讀時間 ≈ 1 分鐘

D https://ac.nowcoder.com/acm/contest/11201/D

总思路没问题, dijkstra不能带log, 2s时间卡时限了

没有log的也800ms, 稍微一个3倍都过不了

所以需要的是点的值要么是初始的要么是推导(当前最大值-定值k)生成的, 双队列+指针实现

没过这题也能+3

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
#define pb push_back
#define c(a,b) ((a)*(m)+(b))

int read(){int r; scanf("%d", &r);return r;} // read

int a[500010];
int n,m,k;

bool vis[500010];

const int di[] = {-1,1,0,0,-1,1};
const int dj[] = {0,0,-1,1,1,-1};

vector< array<int,3> > startvij;

ll cost(int diff){
  fill(vis,vis + n*m,false);
  vector< array<int,3> > vp = {}; // 优先队列等含有log的会TLE
  ll sk = 0 ;
  vp = {};
  int i0 = 0;
  int i1 = 0;
  while(i0 < startvij.size() || i1 < vp.size()){
    int v = 0;
    int i = -1;
    int j = -1;
    if(i0 < startvij.size() && i1 < vp.size()){
      if(startvij[i0][0] >= vp[i1][0]){
        v = startvij[i0][0];
        i = startvij[i0][1];
        j = startvij[i0][2];
        i0++;
      }else{
        v = vp[i1][0];
        i = vp[i1][1];
        j = vp[i1][2];
        i1++;
      }
    }else if(i0 < startvij.size()){
      v = startvij[i0][0];
      i = startvij[i0][1];
      j = startvij[i0][2];
      i0++;
    }else {
      v = vp[i1][0];
      i = vp[i1][1];
      j = vp[i1][2];
      i1++;
    }
    if(vis[c(i,j)])continue;
    vis[c(i,j)] = true;
    sk += v - a[c(i,j)];
    rep(w,0,6){
      int ni = i + di[w];
      int nj = j + dj[w];
      if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
      if(a[c(ni,nj)] == -1) continue;
      if(vis[c(ni,nj)]) continue;
      if(v - diff > a[c(ni,nj)]){
        vp.pb({v - diff,ni,nj});
      }
    }
  }
  return sk;
}

int main(){
  n = read();
  m = read();
  k = read();

  rep(i,0,n){
    rep(j,0,m){
      a[c(i,j)] = read();
      if(a[c(i,j)] != -1) startvij.pb({a[c(i,j)],i,j});
    }
  }
  sort(startvij.begin(), startvij.end(), greater<array<int,3>>());

  int l = 0;
  int r = 1000;
  int ans = 1000;
  while(l <= r){
    int mid = (l+r)/2;
    if(cost(mid) <= k){
      ans = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }
  cout<<ans<<endl;
  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 4.1k 所需閱讀時間 ≈ 14 分鐘
C(反向dijkstra)D(DP,数学,贡献)E(标记,延后处理,贪心,树状数组)F(0/1串,数学)

D

https://codeforces.com/contest/1693/problem/D

给你一个排列

问多少个子区间 可以表示成 增序列和减序列合成的, 称作Decinc

范围

n 2e5

2s

512MB

题解

我的思路

如果是判断一个是否合法

考虑

inc[i] 表示i在增序列, 减序列的最大值

dec[i] 表示i在减序列, 增序列的最小值

然后dp一下O(n) 就做了

然后这里考虑有没有办法转移

因为如果[i..j] 是decinc的,那么它的所有子区间也是

考虑有没有办法dp然后做转移, 发现并没有办法转移

题解

AmShZ

一样的, 但是说是可以证明均摊更新是常数倍?

对于给定i, 找最大的j, 使得 j < i, a[j] > a[j+1]

注意到a[j],a[j+1] 不会都在增序列里,必定一个在减序列里

情况1 a[j+1] 在增序列的话 => a[j] 在减序列

情况2 a[j+1] 在减序列

且因为它是最大的j, 所以a[j] > a[j+1], 且a[j+1] < a[j+2] < a[j+3] < ... < a[i]

inc[i] = a[j](情况1) or a[j+1](情况2) or 0

而对于inc[i]初始化是是inf, 而对于a[j+1]..a[i]这一段都是inf

所以每个位置的值只会有4种情况

dec对称关系同理

换句话说

l从大到小,

每轮从小到大, 如果更新才会去算下一个位置, 否则提前退出

这里还有一点是就是 运算时,当给定l的时候, dp[i]仅依赖于dp[i-1]和a[i], 所以说如果dp[i]没有更新,则i以后的也不会更新, 所以更新的一定是连续的区间

所以sum 遍历 = sum 更新次数 = sum变化次数 = O(n)

Koosha_Mv

一个由升序和降序列合成的序列,当且仅当它不含 3412 也不含 2143

显然包含则不满足

怎么证明不满足一定包含这样的呢

回到dp的过程, 如果刚好在i不满足,

那么, 如果 a[i-1] < a[i], (a[i-1] > a[i] 对称同理

显然a[i-1] 在增序列不合法, (如果a[i-1] 在增序列有合法方案,那么把a[i]放到增序列即可

a[i-1]在减序列, 且 增序列最小值 > a[i]

所以 存在a[j] > a[i] > a[i-1], j < i-1

所以原序列是由

增序列 ..... a[j] 和 减序列.... a[i-1]合成的

因为a[j] 是满足的最小的a[j]

也就是, a[j] 不能放进减序列里(如果可以则能得到更小的增序列值

那么 不妨设下标 w(可能不存在) < j < k ,且 a[k] 在减序列中, a[w] 在减数列中

那么a[j] < a[k] (j k i-1 i => 3 4 1 2) 或 a[j] > a[w](a[j] 左侧至少一个

考虑把a[j]左侧分成三部分讨论, 大于a[j]的, a[i]到a[j]之间的, 小于a[i]的

如果a[i]到a[j]之间存在(3 4 1 2)`, 否则完全不存在, 且 小于a[i] 至少一个

如果大于a[j]的存在,则一定全属于减序列

如果小于a[i]的有不只1个, 那么一旦有其中两个递减 => (? ? j i) => (2 1 4 3) 即它的对称状态

小于a[i]的一定是升序列

总上可以重组 升序列a[j] 左侧,小于a[i], 包含a[w] .... a[j], 降序列a[j]左侧大于a[j]...a[j]右侧原减序列

注意到这样重组以后, a[j] 可以被放入减序列, 而增序列最小值将不再是a[j]

性质充要得证

如何实现

注意到3412和2143是对称的,所以a[i] = n+1-a[i] ,再跑一次3412就行

那么如何计算3412

考虑计算的结果是对于当前位置i作为3,min_r[i]表示最近的2让3412出现

给定3以后,4要是最近的,如果有2,那么1是离2最近的

所以先预处理每个位置后面和它最近的比它大的,以及每个位置前面最近的比它小的的位置

但是记录并不是[3]->4, [2] -> 1

考虑反着来4-> array{3}, 1->array{2}

为什么要这么样做呢,因为除了大小关系还有顺序,1 需要在4的右侧

那么我们倒着遍历4的位置

我们可以用fenwick记录i右侧, (1,2) 存在的[值]->2的坐标

这样我们对于每个3, 去fenwick上查, 值 < 3的值中存在的最大坐标, 就算出答案了

代码

https://codeforces.com/contest/1693/submission/160996027

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
#include <bits/stdc++.h>
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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N = 2e5 + 10;

int n;
int a[N]; // 数组
int inc0[N]; // a[i] 在增数组时, 减数组的最大值
int dec0[N]; // a[i] 在减数组时, 增数组的最小值
int f[N]; // f[i] = 该轮次的计算中,当前点i到 以l为起点的终点 的距离
ll ans;

void udec0(int i){
  if (n >= i){
    // 就硬算
    int inc1 = max( (dec0[i - 1] < a[i]?a[i - 1]:0), (a[i - 1] < a[i] ? inc0[i - 1]: 0));
    int dec1 = min( (a[i] < inc0[i - 1]?a[i - 1]:n+1), (a[i] < a[i - 1] ? dec0[i - 1]: n+1));
    if (!(inc1 == inc0[i] && dec1 == dec0[i])){ // 更新的一定是连续的区间, sum(遍历) = sum(更新) = sum(变化)
      inc0[i] = inc1;
      dec0[i] = dec1;
      f[i] = 0; // 结束点 距离为0
      if (dec1 <= n || inc1) udec0(i+1);
    }
  }
  f[i - 1] = f[i] + 1; // 到结束点距离+1
}

int main(){
  n = read();
  rep(i,1,n+1) a[i] = read();
  per(i,1,n+1) { // 倒序l
    inc0[i] = n + 1;
    dec0[i] = 0;
    udec0(i + 1);
    ans += f[i];
  }
  printf("%lld\n", ans);
  return 0;
}

3412,2143的

https://codeforces.com/contest/1693/submission/161132167

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
#include <bits/stdc++.h>
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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N = 2e5 + 10;


int INF = 0x3f3f3f3f;

// 前缀最小值fenwick
struct Fenwick {
  const int n;
  vector<int> a;
  Fenwick(int n) : n(n), a(n, INF) {}
  // 支持 [0..n) 更新最大值
  void setMin(int x, int v) {
    for (int i = x + 1; i <= n; i += i & -i) a[i - 1] = min(a[i - 1], v);
  }
  // 获得 [0,x) 最大值
  int get(int x) {
    int ans = INF;
    for (int i = x; i > 0; i -= i & -i) ans = min(ans, a[i - 1]);
    return ans;
  }
};


int n;
int a[N]; // 数组
int min_r[N];
ll ans;
stack <int> sk;
vector <int> vec[2][N];

// 如果指定3和2的位置,所以你需要的是3后面最近的4, 和2前面最近的1
void find_3412(){
  Fenwick f(n+10); // 下标是值, 前缀表示小于某个值的出现的最小坐标
  rep(i,0,2) fill(vec[i]+1,vec[i]+n+1,vector<int>());

  // vec[0][i] = vector<int> {j,...}, 表示 j 前面最近的比j小的是i, sk中保留单增的值对应的下标
  sk = {};
  rep(i,1,n+1) {
    while (!sk.empty() && a[i] < a[sk.top()]) sk.pop();
    if (!sk.empty()) vec[0][sk.top()].push_back(i);
    sk.push(i);
  }
  // 倒着做一边, sk中保持值单调递减, vec[1][i] = {j...} , j后面最近的比a[j]大的是a[i]
  sk = {};
  per(i,1,n+1) {
    while (!sk.empty() && a[sk.top()] < a[i]) sk.pop();
    if (!sk.empty()) vec[1][sk.top()].push_back(i);
    sk.push(i);
  }
  // 倒着做
  per(i,1,n+1){
    // f在遍历过程中,存的是(1,2) 的下标都>=i, 然后[2的值] = 位置
    // i=>1, ind=>2
    for (auto ind : vec[0][i]) f.setMin(a[ind], ind); // (i,ind) 构成增序列
    // 这次就是 i=>4, ind => 3, 因为如果确定了3,那么4就最近最好, 所以查询的是(1,2)位置在(以后,且值小于3的,结束位置的最小值),
    // 这里遍历过程之所以i=>4 而不是3,主要因为 保证(1,2)在当前位置右侧
    for (auto ind : vec[1][i]) min_r[ind] = min(min_r[ind], f.get(a[ind]));
    // 得到的是min_r[3的位置] = 最近的2的位置能构成3 4 1 2
    // 在反转过程中 min_r 直接取min,而f是清空
  }
}

int main(){
  n = read();
  INF = n+1;
  rep(i,1,n+1) a[i] = read();
  fill(min_r, min_r + n + 2, INF);
  find_3412();
  rep(i,1,n+1) a[i] = n + 1 - a[i]; // 做对称, 因为对称不影响答案, 而3412和2143是对称的
  find_3412();
  per(i,1,n+1) {
    min_r[i] = min(min_r[i], min_r[i + 1]);
    ans += min_r[i] - i;
  }
  printf("%lld\n", ans);
  return 0;
}

E

题目

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

n+2 长度数组a

首尾元素值为0

最小操作次数让 所有值 = 0

每次操作可以任选以下一种

  1. 最左的最大值=它的左侧的最大值
  2. 最右的最大值=它的右侧的最大值

范围

n 2e5

2s

256mb

题解

我的思路

值挺友好,给你的是[0,n]的范围,(就算很大也可以手动离散

没思路了

ecnerwala

官方的代码实在太长了

ecnerwala 有个超短的代码

https://codeforces.com/contest/1693/submission/160890042

有点延后判断, 贪心选最小值的意味

1
2
3
4
5
6
7
8
9
10
11
12
0 1 4 2 4 0 2 0
. . . . . . . . // 初始
. . ? . ? . . . // 最大的标记为?, 贡献 +2, 意义是第一轮处理2个

. . . x x x x . // 准备处理2的也就是x覆盖区间的, 把区间左侧问号标成 <(表示这个?位置的值比当前小,和左侧的最值相等, 右侧标成 > (同理
. . < . ? . . . // 标记
. . < ? ? . ? . // 对2处理, 贡献 +3

. . ? > > . > . // 同理对于1, 但注意到 1右侧的 < 会变成? 因为
. ? ? > > . > . // 贡献+2

// 0 不需要处理

总贡献是2+3+2 = 7

样例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 1 3 5 4 2 0
. . . . . . .

. . . ? . . . // +1

. . . < . . . // 
. . . < ? . . // +1

. . . ? > . . //
. . ? ? > . . // +2

. . < < ? . . //
. . < < ? ? . // +2

. . ? ? > > . //
. ? ? ? . . . // +3

1+1+2+2+3 = 9

再补充一个例子 1 2 3

1
2
3
4
5
6
7
8
9
10
0 1 2 3 0
. . . . .

. . . ? . // +1

. . . > . // 
. . ? > . // +1

. . > > . // 
. ? > > . // +1

1+1+1 = 3

总的来说, 每轮最大值,确定覆盖区间

区间左侧:

1
2
? 变 <
> 变?

区间内部

1
2
< 变 ?
> 变 ?

区间右侧

1
2
? 变 >
< 变 ?

最后最大值的所有点都是? , 统计?个数即可

实现

并不需要真的像上面思路那样维护4种 . , ? , > , <的状态

发现其实只需要统计?的个数

那么?个数有多少呢

区间内,所有大于它的都变成了问号, 所以区间内就是大于它的个数

区间左侧, 可能有 >,?,<

但 注意到一旦出现 > ,说明上一轮 > 的左侧有?, 如果出现 < 说明上一轮右侧有 ?

引理, 每轮结束后 除开.的情况,剩下的一定是 < ? > 形状的

归纳法可证明

因此, 你需要统计的是

  1. 相交关系
1
2
3
4
5
    ?   ?      // 上一轮结果
<  [l...r] >   // 上一轮结果
     [l...r]   // 本轮
      ?   ?    // 本轮
   < [l...r]>  // 结果
  1. 非相交关系
1
2
3
4
5
    ?   ?                 // 上一轮结果
<  [l...r] >              // 上一轮结果
                [l...r]   // 本轮
                 ?   ?    // 本轮
        < [l      ...r]>  // 结果

有

1
2
newl = min(l, lastr)
newr = max(r, lastl)

区间统计点 = 前缀差 = 树状数组维护

代码

ecnerwaia https://codeforces.com/contest/1693/submission/160890042

基于修改+注释+自己格式+bit改为fenwick: https://codeforces.com/contest/1693/submission/161139663

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
#include <bits/stdc++.h>
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
 
int main() {
  int n = read();
  vector<vector<int> > idxs(n+1); // [值] = 下标数组
  rep(i,1,n+1) idxs[read()].push_back(i);
 
  vector<int> fenwick(n); // 树状数组, 大于等于当前的点记为1
 
  ll ans = 0;
  int lo = 1, hi = n + 1; // 左闭右开, [lo,hi)
  per(v, 1, n+1) { // 从大到小
    if (idxs[v].empty()) continue; // 忽略不存在的值
    // 本轮全为问号的范围
    std::tie(lo, hi) = make_pair(
        min(idxs[v].front(), hi),
        max(idxs[v].back()+1, lo)
    );
 
    // 本轮点 树状数组上标记为1,
    for (int a : idxs[v]) {
      for (; a <= n; a += (a&-a)) fenwick[a-1]++;
    }
    // 区间 [lo, hi) = pre[hi-1] - pre[lo-1]
    for (int a = hi-1; a; a -= (a&-a)) ans += fenwick[a-1];
    for (int a = lo-1; a; a -= (a&-a)) ans -= fenwick[a-1];
  }
  printf("%lld\n", ans);
  return 0;
}

F

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

0/1 字符串 S

每次选择一段 sort, 代价 |cnt(1) - cnt(0)| + 1

求最小总代价,让整个S有序

范围

n 2e5

题解

我的想法

假设最后一次操作了 [l..r]

那么说明 操作之前, [0..l-1] 和目标一样[r+1..n-1] 和目标一样

并且[l..r]中的1和0的个数尽可能的靠近

题解

结论: 只对0和1个数相等的进行排序

证明:

若最优方案中, 对[l,r]排序,且区间中,0比1多d个(d > 0), 代价d+1

如果l上是0, 只需要对[l+1,r]排序,代价为d, 且效果相同, 所以l上一定是1

确定区间左端点,右端点增加时,0和1的差的变化为+1/-1

因此必然存在k < r, 区间 [l,k] 的0和1的个数相等

排序[l,k],代价1, 再排序 [l+1,r] 代价 = d, 总代价 = d+1

所以任何一个0比1多排序, 可以拆成 (0和1相等的排序,代价1) + (0和1的差更小,更短,比原来代价更小的排序)

对于1比0多的情况, 对称关系同理可证

得证

问题变成如何选尽量少的0和1相等区间排序

把0换为-1

又变成经典的,前缀和2维图形化了, 每次选择的是等高的点, 让等高点之间变成 V字形

假设1比-1多,那么也就是结束点比起点高, 如果最后一段是从一个和起点相等的值 一直+1达到 结束点的,那么 把起点和这个值的区间处理即可

所以就是让最后一个连续+1 到的结束点 的那一串尽量长

我们记录达到每个值的首先出现的点, 只考虑(>=0的部分) 显然随着值越大,下标大,( 因为是从0涨过来的

而我们对末端的操作不会改变这个首次出现的位置

贪就完了

-1 比 1多 对称处理即可, 这里只要方案数不要操作细节,(所以还可以把 1变-1,0变1,并旋转字符串)

样例输入1的最后一个数据

这个和上面假设相反, 那就是 把头部可达的值的最小值的最后出现位置之间做区间处理

当然也可以双指针, (总代价移动是线性的

代码

https://codeforces.com/contest/1693/submission/162002156

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
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

char s[200010];
int pre[200010]; // 前缀和
int pos[200010]; // 首次出现的位置

int w(){
  int n = read();
  fill(pos,pos+n+1,-1);
  scanf("%s",s);
  int cnt[] = {0,0};
  rep(i,0,n) cnt[s[i] == '1'] ++;
  if(cnt[0] > cnt[1]) { // 保证 个数1 > 个数0
    swap(cnt[0],cnt[1]);
    rep(i,0,n) s[i] = (1 - (s[i] - '0')) + '0';
    rep(i,0,n/2) swap(s[i],s[n-1-i]);
  }
  int d = cnt[1] - cnt[0];
  rep(i,0,n) pre[i+1] = pre[i] + (s[i] == '0'? -1 : 1);
  rep(i,0,n+1){
    if(pre[i] < 0) continue;
    if(pos[pre[i]] != -1) continue;
    pos[pre[i]] = i;
  }
  int minv = d; // 倒着最小能连续到达的值
  per(i,-cnt[0],d+1){
    if(pre[n - (d-i)] != i) break;
    minv = i;
  }
  int ans = 0;
  while(minv + cnt[0] > 0){ // 已经完成排序
    if(minv < 0) return ans + 1; // 和l=0配
    ans ++ ;
    minv -= ((n-(d-minv))/*r*/-pos[minv]/*l*/)/2; // [l..r]
  }
  return ans;
}

int main(){
  int t = read();
  while(t--) printf("%d\n",w());
  return 0;
}

总结

C

Dijkstra 性质还是不够熟啊

D

直接的dp能想到,也在想转移,倒是转移也可以倒着做, 而且需要推导这个变化的条件,从而得到必定是区间变化,有遍历次数=变化次数=可能次数

另一个方案, 我有大的方向, 说看能不能找不成立的,但是没有得到3412/2143, 一个是这个充要真不知道比赛能不能快速证明,

再就是3412, 就算我知道了, 也不知道怎么去算, 这个按中间位置做遍历, 预处理 两头算是又学了一手

E

总觉得好像见过类似的标记处理, 这里是标记+延后+贪心

哦 像python里的 a,b= b,a+b 可以写成 std::tie(a,b) = make_pair(b,a+b)

原来树状数组还有bit和fenwick写法区别

bit版本的是 a|=a+1

fenwick的是 a+=(a&-a)

逻辑上 bit版本,统计的是末尾连续1的所有子集或上高位1的信息

而fenwick是当前结束向前(a&-a)长度的信息

F

敢于去猜让解答变容易的特殊情况,并证明它

经典的0/1区间个数相等处理, 变成-1,1 和二维图

参考

官方

ecnerwala E

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
F(2-sat)

我的第二次 2-SAT 练习

题目

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

给你m个限制, 分别可能是

  1. $a_i \neq x$
  2. $a_i+a_j \ge x$
  3. $a_i+a_j \le x$

请构造一个满足限制的长n的数组a, 且每个元素在$[1,k]$之间

范围

n 2e4

m 2e4

k 10

2s

512MB

题解

我的思路

一眼2-sat,写过但不熟, 来看看题解如何建立图的

tourist ,jiangly也是拖的板子, XD, 看来我要好好准备板子了?

题解

一个值拆成2k个点

分别是$\le 1,\le 2,\cdots,\le k,>1,>2,\cdots,>k$

其中$\le i, > i$ 是一个互补对

$(i,v,0) = a_i \le v$

$(i,v,1) = a_i > v$

因为2-sat 就是每个点选或不选 0/1, 而上面的两个必定一个满足一个不满足

$(i,v,0) \to (i,v+1,0)$ 不等式关系

$(i,v,1) \to (i,v-1,1)$ 不等式关系 (可以由上面自动建立对称关系

$(i,v,1) \to (i+1,v,1)$ 非严格单增

$(i,x,0) \to (i,x-1,0)$, $a_i \ne x$

$(i,x-1,1) \to (i,x,1)$, $a_i \ne x$ (可以由上面自动建立对称关系

$(i,v,1) \to (j,x-a_i-1,0)$, $a_i + a_j \le x$, 轮换$i,j$

$(i,v,0) \to (j,x-a_i-1,1)$, $a_i + a_j \ge x$, 轮换$i,j$

对于限制必定不合法的$(i,v,x)$ , 建立 $(i,v,x) \to (i,v,x\oplus 1)$

2-sat 的选择

之前有个问题, 我一直没想太通, 现在有点思路了

假设我们完成建边和tarjan的部分

如下, 这样那怎么顺序选都没问题

1
2
a0 <-> b0
a1 <-> b1

而对于这种, 你是不能去选b1/c1 的,而这也是Tarjan 不会处理的,因为tarjan只是合并联通块, 这种还算有答案

1
2
3
a0 <-> b0
b1 <-> c1
c1 -> a0

这种是没有答案, 而且tarjan 的时候是判断不了的

1
2
3
a0<->b0
b1<->c1
c0<->a1

那么两个办法我想的

方法一

如果我们要加 $a[x] \to b[y]$

考虑 如果 $b[y\oplus 1]$ ,那么a不能选x, 所以同时会产生$b[y\oplus 1] \to a[x\oplus1]$

这个好处是,本身可以利用tarjan

方法二

在tarjan处理完scc后, 对scc的每个点的反点做并查集, 缺点是还要跑并查集

等价性 一个奇怪的视角可以证明就是 这些操作是对称性的, 比如方法一里面每次都是对称加的边, 而方法二,不妨设scc 中的反点个数比它大,那么scc必定会合其它scc连接,最终所有并查集完成后, scc和scc反点的scc个数相等

这两个任选一种以后, 最后对scc/并查集 做原图的反向边 做倒序拓扑选择,必定有解?

再看上面的 3个例子

第一个不变

1
2
a0 <-> b0
a1 <-> b1

第二个变成如下,你需要反向拓扑选择

1
2
3
a0 <-> b0 <-> c0
a1 <-> b1 <-> c1
c1 -> a0

第三个则全部连到一个并查集里了, 直接确定不合法了

第三个是限制的不可选状态

比如 $(i,x)$ 不可选, 之前的办法是做一个 失败的节点,让它和这个节点双向连通

而现在发现其实$(i,x) \to (i,x\oplus 1)$, 因为这样如果选$(i,x)$自动造成矛盾

注意区别是不可选还是选了一定满足

代码

我先自己写了个twosat的板子,下次也可以用

https://codeforces.com/contest/1697/submission/160657743

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
177
178
179
180
181
182
183
184
185
186
187
188
#include <bits/stdc++.h>
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;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

class TwoSat{
  vector<int> low; // 能达到的最小的点
  vector<int> dfn; // tarjan 用的深搜访问次序标识
  stack<int> stk; // tarjan 用的stk
  vector<int> res; // tarjan 结果
  vector<vector<int> > p; // 所有点
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = id++;
    stk.push(v);
    for(auto w:p[v]){
      if(dfn[w] == -1){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(res[w] == -1){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  TwoSat(int SZ):n(SZ){ // 点范围[0..SZ-1]
    low = vector<int>(2*n,-1);
    dfn = vector<int>(2*n,-1);
    stk = {};
    res = vector<int> (2*n,-1);
    p = vector<vector<int> >(2*n);
  }

  bool calc(vector<bool> & ans){
    rep(i,0,2*n) if(res[i] == -1) scc(i);
    // rep(i,0,2*n) printf("scc[%lld] = %d\n",i,res[i]);
    rep(i,0,n) if(res[i*2] == res[i*2+1]) return false; // 同一个块的真假都在一个scc里
    vector<int> revscc(2*n); // 互斥scc
    rep(i,0,n) {
      revscc[res[i*2]] = res[i*2+1];
      revscc[res[i*2+1]] = res[i*2];
    }
    vector<set<int> > scc2scc(2*n);
    unordered_map<int,int> degree; // scc入度
    unordered_map<int,bool> scctf; // scc 真假
    rep(i,0,2*n) { // 跨scc的反向边, 做拓扑选择
      degree[res[i]] = 0;
      for(auto j:p[i]){ // i -> j
        if(res[i] == res[j]) continue;
        scc2scc[res[j]].insert(res[i]);
      }
    }
    for(auto s:scc2scc){
      for(auto t:s) degree[t]++;
    }
    vector<int> d0; // 入度为0
    for(auto [v,d]: degree) if(!d) d0.pb(v);
    rep(i,0,d0.size()) {
      if(!scctf.count(d0[i])){ // 没有选择过
        // printf("pick %d, unpick %d\n",d0[i],revscc[d0[i]]);
        scctf[d0[i]] = true;
        scctf[revscc[d0[i]]] = false;
      }
      for(auto item:scc2scc[d0[i]]) { // 更新入度排序
        if(!(--degree[item])) d0.pb(item);
      }
    }
    ans = vector<bool>(n);
    rep(i,0,n) ans[i] = scctf[res[i*2+1]];
    return true;
  }
  void p2(pair<int,bool> pi, pair<int,bool> pj){ // {i,true/false} -> {j,true/false}
    auto [i,bi] = pi;
    auto [j,bj] = pj;
    // printf("(%d,%d) -> (%d,%d)\n",i,(int)bi,j,(int)bj);
    // printf("(%d,%d) -> (%d,%d) (auto\n",j,(int)bj^1,i,(int)bi^1);
    assert(i >= 0 && i < n);
    assert(j >= 0 && j < n);
    p[2*i+bi].pb(2*j+bj);
    p[2*j+(!bj)].pb(2*i+(!bi)); // 自动建立逻辑边
  }
};


int n;
int m;
int k;

int c(int i,int j){
  return i*k+j;
}

void w(){
  n = read();
  m = read();
  k = read();
  TwoSat ts(n*k);
  // a[i][j=0..k-1] => i*k+j
  // false : <= j+1
  // true  : >  j+1
  // 不等式关系
  rep(i,0,n){
    rep(j,0,k-1){
      ts.p2({c(i,j),0},{c(i,j+1),0}); // 自动建立反向边 ts.p2({c(i,j+1),1},{c(i,j),1});
    }
    ts.p2({c(i,k-1),1},{c(i,k-1),0}); // 不能选 > k
  }
  // 非严格单增
  rep(i,0,n-1){
    rep(j,0,k){
      ts.p2({c(i,j),1},{c(i+1,j),1});
    }
  }

  while(m--){
    int op = read();
    int i = read()-1;
    if(op == 1){
      int x = read()-1;
      if(x){
        ts.p2({c(i,x),0},{c(i,x-1),0});
        // ts.p2({c(i,x-1),1},{c(i,x),1}); // 对称自动
      }else{
        ts.p2({c(i,x),0},{c(i,x),1}); // 输入的原始 x = 1 的时候, 不能选 <= 1
      }
    }else if(op == 2){
      int j = read() - 1;
      int x = read(); // a[i] + a[j] <= x , a[i] > v : a[j] <= x-a[i] < x-v, a[j] < x-v-1
      rep(v,1,k+1){
        int v2 = x - v - 1;
        if(v2 >= 1 && v2 <= k){
          ts.p2({c(i,v-1),1},{c(j,v2-1),0});
          // ts.p2({c(j,v-1),1},{c(i,v2-1),0}); // 对称自动建立
        }else if(v2<1){ // 不可选的v , ( v2 > k 说明一定满足
          ts.p2({c(i,v-1),1},{c(i,v-1),0});
          ts.p2({c(j,v-1),1},{c(j,v-1),0});
        }
      }
    }else if(op == 3){
      int j = read() - 1;
      int x = read(); // a[i] + a[j] >= x, a[i] <= v : a[j] >= x - a[i] >= x - v > x - v - 1
      rep(v,1,k+1){
        int v2 = x - v - 1;
        if(v2 >= 1 && v2 <= k){
          ts.p2({c(i,v-1),0},{c(j,v2-1),1});
          // ts.p2({c(j,v-1),0},{c(i,v2-1),1}); // 对称自动建立
        }else if(v2 > k){ // 不可选的v, (v2 < 1 是一定满足
          ts.p2({c(i,v-1),0},{c(i,v-1),1});
          ts.p2({c(j,v-1),0},{c(j,v-1),1});
        }
      }
    }
  }
  vector<bool> ans;
  vector<int> a(n);
  if(!ts.calc(ans)){
    printf("-1\n");
  }else{
    rep(i,0,n){
      rep(j,0,k){
        if(!ans[i*k+j]){
          a[i] = j+1;
          break;
        }
      }
    }
    rep(i,0,n) printf("%d%c",a[i]," \n"[i==n-1]);
  }
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

总结

这里的问题就是说 选则一个范围的值,怎么变成2-sat需要的 真/假

这里的办法是拆成大于小于

当然从逻辑上 用 $= v$ 和$\ne v$ 也可以, 但是这样的问题是, 在做上面的和的不等式的关系时, 边的量就很大了, 不是k条边了

之前2-sat 还有点问题,缺少了一些反向的连接,和缩点后的反向拓扑序选择

准备准备2sat的板子了

参考

官方

0%