YeXiaoRain Blog

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
D(二分，单调队列，前缀和，线段树，区间覆盖，动态规划)

D

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

3xn 左上角 走到 右下角，只能右和下两个方向的走，价值= 经过块的值的和

第一行，第三行直接可走，第二行需要额外代价v,开启[l,r]一段

问总获得价值最大值

范围

n <= 5e5

块上值 -1e9 ~ 1e9

可选扩展 5e5 个，扩展代价 1~1e9

题解

行走代价简化

走过的样子无非是

1
2
3
xxxxxx
     xxxxxxx
           xxxxxxxxx

拆分一下,

第一段： 第一行+，第二行-

第二段： 第二行+，第三行+

1
2
3
4
5
6
     i
++++++
-----
            j
+++++++++++++
            +++++++++

那么行走代价为s[i]+t[j]

剩下就是开放(i,j)的最小代价

状态与转移与范围最值

考虑从(1,1)走到(2,i), 其中当前使用的最右侧的开放端点是i

1
2
3
4
5
6
     ?
xxxxxx      i
     xxxxxxxx
        [   ]
      [  ]
    [  ]

dp[i] = (1,1) -> (2,i) 且i 是当前最右侧开放的点, 上述条件下 , 最大的 s[?] - cost(?,i)

这里两点

  1. i 是某个区间右侧端点, 且走到了这个位置
  2. dp表示的是这样范围中最大的, 包含s 和 cost , 这里很神奇，没有t意味着，下面转移时并不用考虑第二行所选位置对dp的影响

也就是一个准确，一个范围最值

状态转移，

要么是通过第一行直接进入所选区间走到i,

要么就是先走到(2,j), 再在一个区间内走到i, 所以 j 在 [l-1,r] 内

1
2
3
4
5
6
     ?
xxxxxx       j
     xxxxxxxxx
           [      ]
xxxxxx            i
     xxxxxxxxxxxxxx

dp[i] = max(dp[j] - cost(i,j).value)

剩下的就是最终的答案, 因为可能走到不是某个区间的终点，就去第三行了

1
2
3
4
5
     ?
xxxxxx         i  j
     xxxxxxxxxxxxxx
                  xxxxxxx
              [      ]

ans = max(dp[i] - cost(i,j).value + t[j])， i,j 在某个区间内，i < j, 对于相等的情况 上面直接+t[i]就更新

换个角度，先固定一个区间,cost确定,再在这个区间里找 max(dp[i]+t[j])

其中i 在[l-1,r]内

注意到上面的方案，一定经过了某个开放区间的终点，开放区间为 >= 1 个 ，所以还有一种情况，只开放了一个区间，i和j都在区间之中

上面最重要的是控制成了一个区间,但不一定是唯一一个区间

而上面的操作和只开放一个区间十分的像，都是开放一个区间，左dp[i],右t[j] 和(i < j) 左s[i],右t[j] (i <= j)

注意到对于左dp,右t的情况，i==j只会产生比最优更小的答案，所以可以考虑在最值处理时合并left[i] = min(dp[i],dp[i-1],s[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
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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define pb push_back
#define SEG_ROOT 1,0,n-1
#define SEG_L o<<1,l,m
#define SEG_R o<<1|1,m+1,r
const double pi = acos(-1.0);
 
const int N = 500'000;
ll s[N + 10];
ll t[N + 10];
ll dp[N + 10];
ll a[3][N + 10];
vector<tuple<int, int, ll> > rlv;
 
ll seg[2][N * 4 + 10];
ll segans[N * 4 + 10];
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
ll query(int o, int l, int r, int ql, int qr) {
  if (l == ql && r == qr)
    return seg[0][o];
  int m = (l + r) / 2;
  if (qr <= m) {
    return query(SEG_L, ql, qr);
  } else if (ql > m) {
    return query(SEG_R, ql, qr);
  } else {
    return max(query(SEG_L, ql, m),
               query(SEG_R, m + 1, qr));
  }
}
 
void update(int o, int l, int r, int pos) {
  if (l == r) {
    seg[0][o] = dp[l];
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m)
    update(SEG_L, pos);
  else
    update(SEG_R, pos);
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}
 
void build(int o, int l, int r) {
  if (l == r) {
    seg[0][o] = dp[l];
    return;
  }
  int m = (l + r) / 2;
  build(SEG_L);
  build(SEG_R);
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}
 
// [l,r]为开放段
void buildans(int o, int l, int r) {
  if (l == r) {
    // 可以dp到[l-1] 或[l]
    seg[0][o] = max(max(dp[l], s[l]), l > 0 ? dp[l-1] : -INF);
    seg[1][o] = t[l];
    segans[o] = seg[0][o] + t[l];
    return;
  }
  int m = (l + r) / 2;
  buildans(SEG_L);
  buildans(SEG_R);
 
  seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
  seg[1][o] = max(seg[1][o << 1], seg[1][o << 1 | 1]);
  segans[o] = max(seg[0][o << 1] + seg[1][o << 1 | 1],
                  max(segans[o << 1], segans[o << 1 | 1]));
};
 
// {最大值, 最大dp, 最大t}
vector<ll> qans(int o, int l, int r, int ql, int qr) {
  if (ql == l && qr == r) {
    return {segans[o], seg[0][o], seg[1][o]};
  }
  int m = (l + r) / 2;
  if (qr <= m) {
    return qans(SEG_L, ql, qr);
  } else if (ql > m) {
    return qans(SEG_R, ql, qr);
  }
  auto lres = qans(SEG_L, ql, m);
  auto rres = qans(SEG_R, m + 1, qr);
  return {max(max(lres[0], rres[0]), lres[1] + rres[2]), max(lres[1], rres[1]),
          max(lres[2], rres[2])};
}
 
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  ll a2 = 0;
  rep(i, 0, 3) {
    rep(j, 0, n) { scanf("%lld", &a[i][j]); }
  }
  rep(i, 0, n) a2 += a[2][i];
  s[0] = a[0][0];
  rep(i, 1, n) { s[i] = s[i - 1] + a[0][i] - a[1][i - 1]; }
  t[0] = a2 + a[1][0];
  rep(i, 1, n) { t[i] = t[i - 1] + a[1][i] - a[2][i - 1]; }
 
  rep(i, 0, q) {
    int r, l;
    ll v;
    scanf("%d %d %lld", &l, &r, &v);
    rlv.pb({r - 1, l - 1, v});
  }
  ll ans = -INF;
  // 按右端点排序
  sort(rlv.begin(), rlv.end());
  // 处理 使用一次区间直接进入的
  vector<int> pos;  // 单调队列
  unsigned long itr = 0;
  rep(i, 0, n){
    dp[i] = -INF;
  }
  rep(i, 0, n) {  // 下标
    while (pos.size() && s[pos.back()] <= s[i]) {
      pos.pop_back();
    }
    pos.pb(i);
    while (itr < rlv.size() && get<0>(rlv[itr]) == i) {
      // 区间内最大值
      dp[i] = max(
          dp[i],
          s[*lower_bound(pos.begin(), pos.end(), get<1>(rlv[itr]))] -
              get<2>(rlv[itr]));  // cost > 0选自己没影响
      if (dp[i] != -INF) {
        ans = max(ans, dp[i] + t[i]);
        // printf("dp[%lld] => %lld\n", i, dp[i]);
      }
      itr++;
    }
  }
  build(SEG_ROOT);
  itr = 0;
  for(auto [r,l,v]:rlv){
    // 注意可以上一个结束的位置[?..l-1] 和当前 [l..r] 是相邻而不是重叠
    // dp[i] = max(dp[<i] - cost);
    ll newdpi = query(SEG_ROOT, max(0,l-1), max(0,r-1)) - v;
    if (newdpi > dp[r]) {
      dp[r] = newdpi;
      ans = max(ans, dp[r] + t[r]);
      // printf("update: dp[%lld] => %lld\n", i, dp[i]);
      update(SEG_ROOT, r);
    }
  }
  buildans(SEG_ROOT);
  // [l...r] => [l..m] [m+1,r]
  for (auto [r, l, v] : rlv) {
    auto qres = qans(SEG_ROOT, l, r);
    if (qres[0] <= -INF)
      continue;
    ans = max(ans, qres[0] - v);
  }
  printf("%lld\n", ans);
 
  return 0;
}

总结

一个核心的点就是区间覆盖，转换成刚好走到以某个区间结束的动规，感觉要是一个纯的动规还可能想到，合在一起竟然卡住了

参考

官方题解

C202044zxy

cggghh

Sstee1XD

某岛

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

D

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

n(1e5)个数组

每个数组长度为m(<=5), 包含值(<1e9), 每个数组有总代价w(<=1e9)

找出两个数组，让它们的值没有重复，且代价和最小，求最小代价

题解

  1. 随机映射到0-15,注意同一个数一定映射到相同数，不同数可能映射到相同数, 多次运行提高概率期望到2, orz(见YB Lin 的链接)

  2. 集合数学性质

一个集合属于A,又属于B，

如果该集合个数为奇数，则+1

如果该集合个数为偶数(包含空集合)，则-1

那么，如果A,B有公共元素，则结果为0，否则为1

然后维护一个Trie树，上面是所有子集

把原数组按照w排序

利用Trie树找到首个合法的组合i,j

因为要答案最小，所以 i < i’, 则有 j’< j

代码

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

typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define pb push_back
#define all(a) a.begin(), a.end()

// trie 树， 用index取代指针
// 集合按照从小到大 展开存成树节点
struct node {  // 只会新增不会移除， cnt为0 和 移除等价
  unordered_map<int, int> next;  // [值] => 树节点index
  int cnt;
};

vector<node> g;

int new_node() {
  g.push_back(node{{}, 0});
  return g.size() - 1;
}

// 新把数组变化 放入trie树
void add(const vector<int>& x,
         int c /* 1(加入) or -1(移除) */,
         int v = 0 /* trie 树 节点 index*/,
         int i = 0 /* 遍历数组下标 */) {
  if (i == x.size()) {
    g[v].cnt += c;  // 在trie树 的所有集合表示的位置都+1
    return;
  }
  // 不存在创建新节点
  if (!g[v].next.count(x[i]))
    g[v].next[x[i]] = new_node();
  add(x, c, v, i + 1);                // 不选择当前的情况
  add(x, c, g[v].next[x[i]], i + 1);  // 选择当前的情况
}

// 初始全是0
// 如果和 已经加入的 某个数组重合，那么与这个数组贡献的cnt 的结果为 0
// 如果和 已经加入的 某个数组不重合，那么与这个数组贡献的cnt 的结果为 1
// 而trie上的贡献是满足**累加**性质，所以与 trie树直接计算cnt
// 如果为0，则和所有数组现有的都冲突，否则存在一个数组和它没有重合
int get_cnt(const vector<int>& x, int v = 0, int i = 0) {
  if (i == x.size()) {
    return g[v].cnt;
  }
  int res = get_cnt(x, v, i + 1);  // 第i位 不选
  if (g[v].next.count(x[i]))       // 第i位 存在（集合存在） 并选择
    res -= get_cnt(x, g[v].next[x[i]] /* trie 树的下一个节点 */,
                   i + 1);  // 奇偶加减交替
  return res;
}

int main() {
  int n, k;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  vector<pair<int, vector<int>>> a = vector(n, make_pair(0, vector<int>(k, 0)));
  rep(i, 0, n) {
    rep(j, 0, k) {
      cin >> a[i].second[j];  // 读入每个数组
    }
    cin >> a[i].first;  // 数组权重
  }
  rep(i, 0, n) {  // 数组内按照值排序
    sort(all(a[i].second));
  }
  sort(all(a));  // 按权重排序
  new_node();    // trie 根节点 空集合
  int res = -1;
  int i = 0;
  // 和 trie 树中 任何一个重复 都会 让 get_cnt > 0
  while (i < n && !get_cnt(a[i].second)) {
    // 首个一定加入, 如果和现有所有数组都冲突，那么加入trie树
    // 如果存在一个不是和所有都冲突的 , 会触发 get_cnt 不为0
    add(a[i].second, 1);
    i += 1;
  }
  if (i >= n) {
    cout << -1 << "\n";
    return 0;
  }
  // i 是首个 与 [0...i-1]中某个不会冲突的
  int j = i;
  // 从i倒向查找
  while (get_cnt(a[i].second)) {  // 直到所有都冲突，找到一个最小的j
    j -= 1;
    add(a[j].second, -1);  // 每次从trie树中移除一个
  }
  // j < i 互相不冲突, 最小的i对应的最小的j
  res = a[i].first + a[j].first;
  // j' < j < i < i'
  for (i += 1; i < n && j > 0; ++i) {
    while (get_cnt(a[i].second)) {  // 循环直到 和 前面都冲突
      j -= 1;                       // 找一个 最小的j 让 i和j不冲突
      add(a[j].second, -1);         // 移除
    }
    // 不一定是有效值（可能i,j是冲突的），但是因为代价排序关系，保证不会影响最小值
    res = min(res, a[i].first + a[j].first);
  }
  cout << res << "\n";
  return 0;
}

总结

  1. 先按照价值排序，
  2. 再从小到大找到首个和前面某个不冲突的
  3. 找到前面最小的与当前不冲突的，确定一个合法j < i
  4. i增加，每次找更小的j与新的i不冲突的，或者找不到跳过这个i, 每次更新最小值

关键的核心就是,trie树保存的是两两冲突的数组的所有集合，而与trie树 做子集重合get_cnt运算，如果与已加入的所有都有重合则总结果为0，否则大于0, 相当于trie能帮助完成批量判断

ref

官方题解

YB Lin 概率映射 sosdp 乱搞

neweryyy

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

题目

https://projecteuler.net/problem=516

题意

求 n < 10^12, phi(n)的值仅包含质因数2,3,5的所有n的和，mod2^32

题解

欧拉函数

$\phi(n) = n(1-\frac{1}{p_0})(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots$

其中$p_i$均为$n$的质数因数

性质:

$\phi(x)\phi(y)=\phi(xy), gcd(x,y)==1$

$\phi(prime)\phi(x)=(prime-1)\phi(x), gcd(x,prime)==1$

题目转换

$n = 2^{q_0}3^{q_1}5^{q_2} p_0p_1p_2\cdots$

其中$p_i + 1$ 是只包含$2,3,5$ 质因子的数

广搜2,3,5

$x => 2x,3x,5x$

广搜小于$10^{12}$的所有只包含质因数$2,3,5$的数

质数判别

小于$2^{64}$里的质因数可以 Miller-Robin算法 常数级别 判别

二分

$n = 2^{q_0}3^{q_1}5^{q_2} p_0p_1p_2\cdots$

后面又可以拆分成$2^{q_0}3^{q_1}5^{q_2}$ 和 $p_0p_1p_2\cdots$

右边每个质数最多一次方，直接生成所有的积，左边还是上面求的

要两部分数组内容乘积小于n, 可以左侧枚举二分右侧，右侧枚举二分左侧都一样的, 通过前缀和辅助得到和

Ref

Euler’s totient function

發表於 更新於 分類於 ， Disqus： 文章字數： 4k 所需閱讀時間 ≈ 13 分鐘
B, DP,分治,前缀和,数学

题目

https://atcoder.jp/contests/agc056/tasks/agc056_b

一个长度为n的排列

对于q个查询构成的大小为q向量有多少种

其中每次查询排列[l..r] 中最大值的下标

n <= 300

查询不重复, 合法(l < r)

题解

考虑把数字从大到小放入排列的位置.

假设把N放在位置pos,那么有三类区间

  1. 包含pos的
  2. 完全在pos左侧
  3. 完全在pos右侧

那么显然对于所有查询区间包含pos的,返回都是pos

而对剩余的,如果把左侧位置的所有值保持相对顺序,右侧位置的所有值保持相对顺序, 然后调整值让左侧所有值大于右侧所有值, 对于输出的q维向量没有变化.(因为相对顺序不变,左侧和右侧内部,原来哪个位置大还是哪个大,且都在pos单侧互不影响), 因此不妨我们选定pos后如此调整

先不考虑重复

那么设计状态dp[i][j][pos] = 在[i..j]中, pos为最大值, 且属于[i..j]中某个完整区间的 方案数

那么注意到上面,当我们选定了pos, 就是把区间划分成[i..pos-1]pos[pos+1..j]

原题的答案变为 sum(dp[0][n-1][pos = 0..n-1])

其中注意到,我们在对于无效的pos结果为0, 例如 pos不属于[i..j]中任何一个完整区间, 其对应的情景是最大值不属于任何一个区间,那么 这个位置删掉都行 更不用考虑值了

那么上面的转移方程有

dp[0][n-1][pos] = sum(dp[0][pos-1][0..pos-1]) * sum(dp[pos+1][n-1][pos+1..n-1])

也就是 左侧 和 右侧分别独立计算.

而这个计算规则实际上和原问题是同一个问题. 因此可以看成是分治

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

其中 sum为零时,记为1,属于空方案

引理: 分治中数值的大小无影响,只有输出有影响

因为隔离性,假设右侧不动,来考虑左侧的排列数值变化,但产出向量不变,对结果有什么影响.

假设左侧存在[1..2][3..4] 非重叠 或者 [1..2][2..3]重叠区间或其它任何状态, 那么可能不同的值,有相同的向量产生

一旦左侧的产出向量确定了, 注意到转移方程的剩余部分,一个是pos,那一定比左侧都大,而右侧根据它们的隔离性,比左侧都小,所以转移方程的任何剩余向量也不会受到影响.

所以, 转移方程只与单侧的向量产生相关, 与具体值无关

上面的东西,看上去搞个前缀和,再for(len)for(左端点i)for(最大值下标pos) 就搞完了

重复

基本的东西有了,下面是精确计算值

正如上面的例子[1..2][3..4]

如果是1234 输出是(2,4)

如果是3412 输出也是(2,4)

而对于dp来说,一个是按照 第4位 开始划分,一个是按照第2位开始划分的. 有重复的问题

同样,对于[1..2][2..3] 来说

如果312 和 213 也会重复.分别是第1位和第3位最大进行讨论的, 而它们的输出都是(1,3)

注意, 这里 132 和231 不会重复统计

一个办法是容斥(本文不会提到

另一个就是发现其数学性质

当在[i..j] 中 pos是最大值的下标 且属于其中某个完整区间时

如果[i..pos-1] 中的最大值 在idx, 且idx和pos 在[i..j] 中不属于任何同一个完整区间, 那么 让idx变为 [i..j]中的最大值, pos改为次大值,总输出向量不变

证明

因为前面假设过, value[pos] > 所有左侧值 > 所有右侧值,所以pos最大,idx次大

交换以后,value[idx] > value[pos] > 其它左侧值 > 所有右侧值

按情况讨论区间

  1. pos右侧的所有区间,因为包含的内容全在右侧值中,所以都不受影响
  2. 包含pos的所有区间, 原本输出pos, 因为不包括idx,现在pos次大,所以依然输出pos
  3. pos左侧所有区间, 只有idx变大了,但对于所有左侧区间来说,相对顺序都没有变化, 所以左侧的也都没有变

所以总的向量没有变

以上证明了,如果[i..pos-1]中的最大值和pos在[i..j]中不属于同一个完整区间,那么会被重复统计. 所以

dp[i][j][p] = sum(dp[i][p-1][i..p-1]) * sum(dp[p+1][j][p+1..j])

要改为

dp[i][j][p] = sum(dp[i][p-1][f(p)..p-1]) * sum(dp[p+1][j][p+1..j])

f(p) = 最小的 在[i..j]中和p属于同一个完整区间的

不漏从dp过程中已经保证了,上面我们只是提到了去重,而并不能说明所有重复都没有了.下面证明所有重复都没有了

即是证明 任何输出向量,只会被至多统计一次

不妨设某个 输出被统计了两次.

根据统计过程, 如果它在首次被不同的最大值下标统计了,那么

  1. 这两个下标属于同一个区间,和下标是最大值矛盾,一个区间只有一个下标是最大值
  2. 这两个下标不属于任何同一个区间,那么根据上面的变化, 只会统计在左侧为更大值

代码

基于 heno239 的代码 https://atcoder.jp/contests/agc056/submissions/27693073

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
#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 - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

struct modint {
  int n;
  modint() : n(0) { ; }
  modint(ll m) {
    if (m < 0 || mod <= m) {
      m %= mod;
      if (m < 0)
        m += mod;
    }
    n = m;
  }
  operator int() { return n; }
};
bool operator==(modint a, modint b) {
  return a.n == b.n;
}
modint operator+=(modint& a, modint b) {
  a.n += b.n;
  if (a.n >= mod)
    a.n -= mod;
  return a;
}
modint operator-=(modint& a, modint b) {
  a.n -= b.n;
  if (a.n < 0)
    a.n += mod;
  return a;
}
modint operator*=(modint& a, modint b) {
  a.n = ((ll)a.n * b.n) % mod;
  return a;
}
modint operator+(modint a, modint b) {
  return a += b;
}
modint operator-(modint a, modint b) {
  return a -= b;
}
modint operator*(modint a, modint b) {
  return a *= b;
}
modint operator^(modint a, ll n) {
  if (n == 0)
    return modint(1);
  modint res = (a * a) ^ (n / 2);
  if (n % 2)
    res = res * a;
  return res;
}

ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) {
  return a * modint(inv(b, mod));
}
modint operator/=(modint& a, modint b) {
  a = a / b;
  return a;
}

vector<int> vle[305];       // [r pos] = {l pos...} 区间右端点到左端点
modint dp[305][305][305];   // [l][r][x] = [l..r-1] 最大的是x的方案数, 其中不论l取值多少,x与[l,r-1]至少属于[l,r-1]中的一个完整区间
modint rdp[305][305][305];  // rdp[l][r][i] =  dp[l][r][0..i-1] 的前缀和

// 默认 全false, 右端点在[l+1..r]之间，长度 <= r-l 的区间是否存在
bool exi[305][305];

int cl[305];  // 计算过程中[l..r-1] 中, cl[i] = 与i同属于完整区间属于[l..r-1]的 最左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l - 1);
  }
  // 同样右端点 左端点从小到大, 方便后面二分找满足条件的左端点
  rep(i, 0, n + 1) sort(all(vle[i]));
  rep(len, 1, n + 1) {    // 枚举 长度[1..n], 因为每次划分是 左右两个更短的范围
    rep(r, len, n + 1) {  // 右端点从小到大 [len..n]
      int l = r - len;    // 左侧端点 = 右端点-长度
      int nw = r; // 遍历过程中,当前属于[l..r-1]的完整区间的最小左端点
      per(j, l + 1, r + 1) {  // j（右端点）从大到小 [l+1,r] 范围内的每个右端点
        // 第一个大于或等于某个元素的位置, 二分查找
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) {  // [nw,j] 区间小于等于 len
          nw = min(nw, vle[j][t]);
        }
        // 右端点 [j..r] 中的区间的最小左端点, 不存在的情况 r > j - 1
        cl[j - 1] = nw;
      }
      if (nw == r) {  // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;  // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r) {    // [l..r-1]
        if (x < cl[x])  // 不存在 [l,r] 之间的小区间 包含 坐标x
          continue;
        // [l..x-1]x[x+1..r-1]
        // 存在右端在 [l+1..x], 长度小于 x-l 的区间,
        // sl = sum{dp[l][x][cl[x]..x-1]}
        // 注意这里, 当[l..x-1]不存在时是1, 而[l..x-1]存在时,因为防止重复统计可能[cl[x]..x-1]是0
        modint sl = exi[l][x] ? rdp[l][x][x] - rdp[l][x][cl[x]] : (modint)1;
        // 存在右端在 [x+2..r], 长度小于 r-x-l 的区间,
        // sr = sum{dp[x+1][r][x+1..r-1]}
        // 而对于右侧 似乎可以直接判断前缀和是否非零,但实际上因为是取mod运算,可能为mod的倍数,所以还是需要一个exi的辅助数组
        modint sr =
            exi[x + 1][r] ? rdp[x + 1][r][r] - rdp[x + 1][r][x + 1] : (modint)1;
        dp[l][r][x] = sl * sr;  // [l,r-1]中 最大的下标为x, 方案数
        // 下面由此输出
        // printf("%d %lld %lld => %d %d\n",l,r,x,(int)sl,(int)sr);
      }
      rep(j, l, r) {
        // [l..r-1]
        // rdp[l][r][j] = dp[l][r][0..j-1] 前缀和
        rdp[l][r][j + 1] = rdp[l][r][j] + dp[l][r][j];
      }
    }
  }
  printf("%d", (int)rdp[0][n][n]); // [0,n-1] 最大下标[0..n-1]的方案数
  return 0;
}

例子

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
//
// [l          x-1]x[x+1          ]r
// x 是最大值
// dp[l][r][x] = 左边方案数 x 右边方案数, 其中右边的长度覆盖了x
//             = sum{dp[l][x][cl[x]..x-1]} * sum{dp[x+1][r][x+1..r-1]}
//             = x 是最大值，对左侧的影响当前 最近的是 cl[x]
//
//
// 012345678
//  xx
//   xxx
//     xxx
//      xx
//        xx
//
/*
9 5
2 3
3 5
5 7
6 7
8 9
*/
/*
l r x ==sl*sr
[l r) 左闭右开,所以 实际区间是[l..r-1]

len = 2
1 3 1 => 1 1
1 3 2 => 1 1

5 7 5 => 1 1
5 7 6 => 1 1

7 9 7 => 1 1
7 9 8 => 1 1

len = 3
0 3 1 => 1 1
0 3 2 => 1 1 (0不属于完整区间,所以没有 0 3 0

1 4 1 => 1 1
1 4 2 => 1 1 (虽然3和属于[2..4]的完整区间,但这里的区间是[1..3],3 不属于这之间的任何完整区间, 所以也没有 1,3,3

2 5 2 => 1 1
2 5 3 => 1 1
2 5 4 => 1 1

4 7 4 => 1 2 (首次包含关系 区间,一个[4..6]一个[5..6],右侧 = dp[5][7][5] + dp[5][7][6] = 1+1 = 2, 也就是[4..6] 最大值在4时,不影响右侧不包含它的区间,右侧有两种值
4 7 5 => 1 1
4 7 6 => 1 1

5 8 5 => 1 1
5 8 6 => 1 1

6 9 7 => 1 1
6 9 8 => 1 1

len = 4
0 4 1 => 1 1
0 4 2 => 1 1

1 5 1 => 1 3 (同 上面 4 7 4
1 5 2 => 1 1 (这个和下面两个都是 1 1, 但实际上有些不同, 下面两个的左边的1, 如果按照上面右侧的统计法,应该是 2 而不是1, 注意到上面算sl和sr是有区别的,一个是[cl[x]..x-1], 一个是[x+1..r], 如果一致应该是[l..x-1]而不是[cl[x]..x-1], 说面 左侧最大值, 一定要和x属于同一组,如果不同组, 让左侧更大,其它平移补位, 总输出不变. 所以下面两个都是1.
1 5 3 => 1 1
1 5 4 => 1 1 

2 6 2 => 1 1
2 6 3 => 1 1
2 6 4 => 1 1

3 7 4 => 1 2
3 7 5 => 1 1
3 7 6 => 1 1

4 8 4 => 1 2
4 8 5 => 1 1
4 8 6 => 1 1

5 9 5 => 1 2
5 9 6 => 1 2
5 9 7 => 0 1
5 9 8 => 0 1

len = 5
0 5 1 => 1 3
0 5 2 => 1 1
0 5 3 => 1 1
0 5 4 => 1 1
1 6 1 => 1 3
1 6 2 => 1 1
1 6 3 => 1 1
1 6 4 => 1 1
2 7 2 => 1 4
2 7 3 => 1 4
2 7 4 => 1 2
2 7 5 => 1 1
2 7 6 => 1 1
3 8 4 => 1 2
3 8 5 => 1 1
3 8 6 => 1 1
4 9 4 => 1 4
4 9 5 => 1 2
4 9 6 => 1 2
4 9 7 => 0 1
4 9 8 => 0 1

len = 6
0 6 1 => 1 3
0 6 2 => 1 1
0 6 3 => 1 1
0 6 4 => 1 1
1 7 1 => 1 12
1 7 2 => 1 4
1 7 3 => 1 4
1 7 4 => 1 2
1 7 5 => 1 1
1 7 6 => 1 1
2 8 2 => 1 4
2 8 3 => 1 4
2 8 4 => 1 2
2 8 5 => 1 1
2 8 6 => 1 1
3 9 4 => 1 4
3 9 5 => 1 2
3 9 6 => 1 2
3 9 7 => 0 1
3 9 8 => 0 1

len = 7
0 7 1 => 1 12
0 7 2 => 1 4
0 7 3 => 1 4
0 7 4 => 1 2
0 7 5 => 1 1
0 7 6 => 1 1
1 8 1 => 1 12
1 8 2 => 1 4
1 8 3 => 1 4
1 8 4 => 1 2
1 8 5 => 1 1
1 8 6 => 1 1
2 9 2 => 1 8
2 9 3 => 1 8
2 9 4 => 1 4
2 9 5 => 1 2
2 9 6 => 1 2
2 9 7 => 0 1
2 9 8 => 0 1

len = 8
0 8 1 => 1 12
0 8 2 => 1 4
0 8 3 => 1 4
0 8 4 => 1 2
0 8 5 => 1 1
0 8 6 => 1 1
1 9 1 => 1 24
1 9 2 => 1 8
1 9 3 => 1 8
1 9 4 => 1 4
1 9 5 => 1 2
1 9 6 => 1 2
1 9 7 => 0 1
1 9 8 => 0 1

len = 9
0 9 1 => 1 24
0 9 2 => 1 8
0 9 3 => 1 8
0 9 4 => 1 4
0 9 5 => 1 2
0 9 6 => 1 2
0 9 7 => 0 1
0 9 8 => 0 1
*/

改版

对于上面代码改了主要几个部分

把[l,r]改为左右都是闭区间了,不用考虑加减1的描述范围

把所有下标按照题目变成1-index而不是上面的0-index,因为这样也方便前缀和不用单独处理下标0

去掉了 大佬的modint, 假设没有modint的实现的情况下,直接加mod运算

https://atcoder.jp/contests/agc056/submissions/27743665

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
#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 - 1; i >= a; i--)
constexpr ll mod = 998244353;
#define all(v) (v).begin(), (v).end()

vector<int> vle[305];   // [r pos] = {l pos...} 区间右端点到左端点
ll dp[305][305][305];   // [l][r][x] = [l..r] 最大的是x的方案数, 其中不论l取值多少,x与[l,r]至少属于[l,r]中的一个完整区间
ll rdp[305][305][305];  // dp 前缀和
bool exi[305][305];     // 默认 全false, 在[l..r]之间 是否存在完整区间
int cl[305];            // 右端点 in [i..最右侧] = 区间的最小左端点
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  rep(i, 0, m) {
    int l, r;
    scanf("%d %d", &l, &r);
    vle[r].push_back(l);
  }
  rep(i, 1, n+1) sort(all(vle[i]));
  rep(len, 2, n+1) {              // 枚举 长度
    rep(r, len, n+1) {            // 右端点 从小到大
      int l = r - len + 1;        // 左侧端点 = 右端点 - 长度 +1
      int nw = r + 1;             // 左端点, 在[l..r] 中
      per(j, l, r + 1) {          // j（右端点）从大到小 [l,r] 范围内的每个右端点
        int t = lower_bound(all(vle[j]), l) - vle[j].begin();
        if (t < vle[j].size()) nw = min(nw, vle[j][t]);
        cl[j] = nw;
      }
      if (nw == r+1) {            // 没有任何有效区间
        exi[l][r] = false;
        continue;
      }
      exi[l][r] = true;           // 右端点在 [l+1 ..r], 长度小于等于 len 的区间 存在
      rep(x, l, r+1) {            // [l..x-1]x[x+1..r]
        if (x < cl[x]) continue;  // 不存在 [l,r] 之间的小区间 包含 坐标x
        ll sl = exi[l][x-1] ? rdp[l][x-1][x-1] - rdp[l][x-1][cl[x]-1] : 1;
        ll sr = exi[x+1][r] ? rdp[x+1][r][r] - rdp[x + 1][r][x] : 1;
        dp[l][r][x] = ((sl%mod) * (sr%mod))%mod;    // [l,r-1]中 最大的下标为x, 方案数
      }
      rep(j, l, r + 1) rdp[l][r][j] = (rdp[l][r][j-1] + dp[l][r][j])%mod;
    }
  }
  printf("%lld", (rdp[1][n][n]+mod)%mod); 
  return 0;
}

参考

官方题解 https://atcoder.jp/contests/agc056/editorial/3045

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
E(线段树)

E

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

给你字符串只包含abc

给你q次操作,每次操作修改一个位置上的字符为’a’/‘b’/‘c’中的一种

每次操作后,问对于当前字符串,至少修改多少个字符,使字符串不包含abc子序列

子序列定义: 字符串任意位置删除任意个得到的剩余字符串

范围

字符串长度 1e5

询问次数 1e5

题解

一个可以过的方案是

seg(l,r,state) = 最少次数

其中l,r表示一个区间,通过线段树维护

state 是 5bit的状态分别对应a,b,c,ab,bc, 是否在区间中出现过

那么 线段树节点关系 是

f(根, mergestate(statel,stater)) = min(f(左节点,statel)+f(右节点,stater))

其中 产生abc的不更新 根节点状态

问题是 实现起来感觉有点卡常数 $q \cdot log(N) 32 \cdot 32 $ 的运算量 ,2464ms/3000ms 过的, 看到有些其它状态设计,状态如果更少会更快

tourist 300ms 过的

另一个想法是,实际上变成 [不存在a][不存在b][不存在c]的字符串就好了

那 操作代价(其实就是分别移除a,b,c) = count[a][0..i]+count[b][i+1..j]+count[c][j+1..end]

所以对count计算总是先a后b再c

变成了维护 f(l,r,startch, endch) = 最少代价

也就是 在区间[l,r]上 起始位置是计算startch,结束位置是计算endch

这样状态数最多3x3,根据a,b,c的顺序, 真实有效的只有6 个, 计算代价 常数就小很多

代码(前一种)

https://codeforces.com/contest/1609/submission/137409899

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

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = (i & (1 << (s[pos] - 'a'))) ? 0 : INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos])
      continue;
    // 一次修改
    rep(i, 1, (1 << 5)) {
      if (i & (1 << (ch - 'a'))) {  // 包含该bit
        t[o][i] = min(t[o][i], 1);
      }
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}

可能包含改成恰好包含快了不少

https://codeforces.com/contest/1609/submission/137444815

1216 ms/3000 ms

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

#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
const int INF = 0x3f3f3f3f;  // 无限大操作
int n, q;
char s[100010];

int t[400010][40];

// bits
// 0 a
// 1 b
// 2 c
// 3 ab
// 4 bc
void mergeState(int o) {
  rep(i, 1, (1 << 5)) { t[o][i] = INF; }
  rep(i, 1, (1 << 5)) {  // 左state
    if (t[o << 1][i] == INF)
      continue;
    rep(j, 1, (1 << 5)) {  // 右state
      // abc = 'a' + 'bc' or 'ab' + 'c'
      if (((i & (1 << 0)) && (j & (1 << 4))) ||
          ((i & (1 << 3)) && (j & (1 << 2)))) {
        continue;
      }
      // new bit state
      int k = i | j;
      // ab = 'a'+'b'
      if ((i & (1 << 0)) && (j & (1 << 1))) {
        k |= (1 << 3);
      }
      // bc = 'b' + 'c'
      if ((i & (1 << 1)) && (j & (1 << 2))) {
        k |= (1 << 4);
      }
      t[o][k] = min(t[o][k], t[o << 1][i] + t[o << 1 | 1][j]);
    }
  }
}

void calc(int o, int pos) {
  rep(i, 1, (1 << 5)) {  // 状态
    t[o][i] = INF;
  }
  rep(ch, 'a', 'c' + 1) {
    if (ch == s[pos]){
      t[o][1<<(ch-'a')] = 0;
    }else{
      t[o][1<<(ch-'a')] = 1;
    }
  }
}

void update(int o, int l, int r, int pos, char ch) {
  if (l == r) {
    s[pos] = ch;
    calc(o, l);
    return;
  }
  int m = (l + r) / 2;
  if (pos <= m) {
    update(o << 1, l, m, pos, ch);
  } else {
    update(o << 1 | 1, m + 1, r, pos, ch);
  }
  mergeState(o);
}

void build(int o, int l, int r) {
  if (l == r) {
    calc(o, l);
  } else {
    int m = (l + r) / 2;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    mergeState(o);
  }
}

int main() {
  scanf("%d %d", &n, &q);
  scanf("%s", s);
  build(1, 0, n - 1);
  rep(i, 0, q) {
    int pos;
    char ch;
    scanf("%d %c", &pos, &ch);
    update(1, 0, n - 1, pos - 1, ch);
    int ans = INF;
    rep(i, 1, (1 << 5)) { ans = min(ans, t[1][i]); }
    printf("%d\n", ans);
  }

  return 0;
}
0%