Atcoder arc114

發表於 更新於 分類於 ， Disqus： 文章字數： 5.2k 所需閱讀時間 ≈ 17 分鐘
D(题意转换,DP)E(概率论)F(持久化线段树)

https://atcoder.jp/contests/arc114

D

数轴上n个点ai，数轴红色

每次操作 选一个点+1 或 -1, 经过的颜色翻转（红/蓝）

目标是 数轴切割成 红 蓝 红 蓝…红的指定多段（输入切割点的坐标）

求最少操作次数

n 5000

|坐标| 1e9

2s

1024mb

我的思路

没啥想法，首先 颜色可以看成 红0 蓝1

那么就是 多个1的 xor 等于目标

问题是 ai可以重复

1
2
3
4
5
11111111
    a1
    a2
11111
     111

可以这样构成

然后一个是

1
2
3
4
11111111
a1
     11111111
           a2

如果两个朝向中间的有重叠，那么不重叠肯定更优，所以任意两个朝向中间的不重叠

那么重叠的就只能同向

1
2
3
4
5
6
7
8
9
10
111111111
a1
     1111111111
     a2
等价于

111111111111111
a1
     1111
     a2

同向的可能重叠，不过同向的话，那就有可重叠但不覆盖，

这里一个想法就是 能否证明每个1 都可以一次覆盖，如果能的话那每个1只需要尝试左侧或右侧最近的点

考虑多个重叠关系

1
2
3
4
5
6
7
8
1111111111
a1
   11111111111
   a2
      11111111111
      a3
=      
111   1111    111

中间这一段 合法的方案 一定会被至少3个覆盖，得不到上面猜想的性质

1
2
3
4
5
6
7
8
9
10
11
1111111111
	1111111111
		1111111111
=
1111    11    1111

1111111111
		1111111111
			1111111111
=			
11111111  11      1111

也保证不了ai对应的是前面几个点

不过 a的个数 = 覆盖1的段数

a是 段的端点（除了第一个）

因为有

1
2
3
4
5
6
7
11111111111    111  
     a0
     a1
           a2
111111
      111111111
           1111111

的情况

而a0/a1比较难切割，因为左侧也可以对称

所以一个连续的多个1

1
2
3
4
5
6
7
111    111111   111
=
      a  aa  a
1111111
   1111111
          111111
             111111

dp[前i段1完成][最后使用的a]= 最小代价

dp[i][j] = min(dp[i0][j0]+cost(i0+1..i,j0+1..j)

也就是需要 计算用$j_0+1\cdots j$来完成$i_0+1..i$这段的$1$的代价

题解

a为初始位置, 非严格单调递增

b为结束位置

$\min(\sum_{i=1}^n |a_i-b_i|)$

而如果 有 $b_i > b_{i+1}$

显然 交换 不会更差, 所以b也非严格单调递增

定义一个点的颜色: 点颜色=左侧边颜色 xor 右侧边颜色

换句话说，也就是 把原来的线段颜色变成：点的左右是否异色

那么 对于选的区间$[a,b]$ 实际上是对，点a的颜色进行 翻转，再b的颜色进行翻转！！！！！！！

把 $a_i,b_i$ 放入可重复集合$S$中，那么也就需要$S$中出现奇数次的点的集合 = 目标点的集合！！！， 因为$a_i,b_i$ 变成翻转点以后，剩下的就是点被翻转奇数次才是目标

这转换 好神奇 看了之后又觉得显然，但自己想不到

所以问题变成

对于可重集合 $A$, 放入$n$个点，其奇数次出现的 = $T$，且让n个点$\sum |a_i-b_i|$ 尽量小

那么也就是$A+T+$ n个点 以后全是偶数次出现

那么$X=A+T$中出现奇数次$X_{\mathrm{odd}}$的至少放一个，需要满足$|X_{\mathrm{odd}}|\le n$

剩下$n-|X_{\mathrm{odd}}|$个点需要是偶数,随便放，但需要一对一对的，所以$\frac{n-|X_{\mathrm{odd}}|}{2}$个位置

$dp[i][j][k]=$ 前$i$个$a$,必须要出现的用了$j$个,已经使用$k$个自由放的 的最小代价

那么两种情况，

  • 使用必须要出现的 $\mathrm{chmin} (dp[i+1][j+1][k],dp[i][j][k]+|a[i+1]-X[j+1]|)$
  • 使用自由放的 $\mathrm{chmin} (dp[i+2][j][k+2],dp[i][j][k]+|a[i+2]-a[i+1]|)$

这里自由放的没有考虑 相对顺序，因为如果不满足更优的顺序，那么必定是合法 但是 更差的答案，不会影响结果

而自由放时 是在$|a[i+1]-p|+|a[i+2]-p|$的最小值,那么在它们之间都可以

然后$n^3$肯定是不行的,不过注意到 因为匹配对应的关系 始终有$i=j+k$

  • $\mathrm{chmin} (dp[i+1][j+1],dp[i][j]+|a[i+1]-X[j+1]|)$
  • $\mathrm{chmin} (dp[i+2][j],dp[i][j]+|a[i+2]-a[i+1]|)$

其中$0\le j < |X_{\mathrm{odd}}|$

$ans = dp[n][|X_{\mathrm{odd}}|]$

代码

https://atcoder.jp/contests/arc114/submissions/50620525

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
#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;}
const ll INF=0x3f3f3f3f'3f3f3f3f;

int main(){
  auto chmin=[&](auto&a,auto b){a=min(a,b);};
  int n=read();
  int k=read();
  vector<ll> a;
  vector<int> at;
  rep(i,0,n) {
    int v=read();
    a.push_back(v);
    at.push_back(v);
  }
  rep(i,0,k) at.push_back(read());
  sort(begin(a),end(a));
  sort(begin(at),end(at));
  vector<pair<int,int> > tcnt;
  rep(i,0,size(at)) {
    if(i==0 or at[i] != at[i-1]) {
      tcnt.emplace_back(at[i],1);
    }else{
      tcnt.back().second++;
    }
  }
  vector<ll> todd;
  for(auto [v,c]:tcnt) if(c%2==1) todd.push_back(v);
  int m=todd.size();
  if(m > n or (n-m)%2==1){
    printf("-1\n");
    return 0;
  }
  vector dp(n+1,vector<ll>(m+1,INF)); // dp[匹配个数][钦定个数]
  dp[0][0]=0;
  rep(i,0,n) rep(j,0,m+1) if(dp[i][j] != INF){
    if(j<m)  chmin(dp[i+1][j+1],dp[i][j]+abs(a[i+0]-todd[j])); // |a[i]-todd[j]|
    if(i+1<n)chmin(dp[i+2][j  ],dp[i][j]+abs(a[i+1]-a[i+0] )); // |a[i]-p| + |a[i+1]-p|
  }
  printf("%lld\n",dp[n][m]==INF?-1:dp[n][m]);
  return 0;
}

E Paper Cutting 2

h * w二维数组, 两个格子黑色，其余白色

每次 从$h-1$条水平线和$w-1$条垂直线，等概率 选一条线，平面切割成两块，

  • 如果 两个黑色格子 在同一块，则扔掉空白的继续
  • 如果 黑色格子 被分割，那么停止

求 E(操作次数)

h,w 1e5

2s

1024mb

我的思路

感觉横纵不影响

因为 两个黑的

1
2
3
4
5
B

          之间的横纵线

    B

所以，设之间有a条横纵线

dp[i]=, 除了之间的横纵线有$i$条开始向后需要的次数期望

$dp[0]=1$

$dp[i]+=\frac{a}{i+a}$ 切割到里面

那么问题来了， 切割外部的时候 和外部的单侧距离是有关的，不仅仅是总量

1
2
3
    v1
v0  B  v2
    v3

$dp[v_0][v_1][v_2][v_3] += \sum_{i=1}^{v_0} \frac{1}{a+v_0+v_1+v_2+v_3}(dp[v_0-i][v_1][v_2][v_3]+1)$ 例如从左侧选一个线

这样 光是状态就来到了$H^2W^2$

换个 计算$t$次 切割后 还在一起

这里的问题是，因为每次切割时 是等概率选择，所以分母 和具体的切割前的长度是有关的，所以不能直接的binom 到概率

考虑更简单的 , a为B的可选个数

1
B v_0

$dp[i] = \frac{a}{a+i} + \sum_{j=1}^{i}\frac{1}{a+i}(dp[j]+1)$

$dp[i] = 1+ \frac{\sum_{j=1}^{i} dp[j]}{a+i}$

前缀和 可以$O(n)$

1
B v_0 v_1

$dp[i][j] = \frac{a}{a+i+j} + \sum_{t=0}^{i-1}\frac{1}{a+i+j}(dp[t][j]+1)+ \sum_{t=0}^{j-1}\frac{1}{a+i+j}(dp[i][t]+1)$

$\displaystyle dp[i][j] = 1 + \frac{\sum_{t=0}^{i-1} dp[t][j]+ \sum_{t=0}^{j-1}dp[i][t]}{a+i+j}$

$O(n^2)$的

令 $f[i][j]=dp[i][j]x^{a+i+j}$

则 $dp[i][j]=\frac{f[i][j]}{x^{a+i+j}}$

$f[i][j]=dp[i][j]x^{a+i+j}=(1 + \frac{\sum_{t=0}^{i-1} dp[t][j]+ \sum_{t=0}^{j-1}dp[i][t]}{a+i+j})x^{a+i+j}$

$\displaystyle =(1 + \frac{\displaystyle \sum_{t=0}^{i-1} \frac{f[t][j]}{x^{a+t+j}}+ \sum_{t=0}^{j-1} \frac{dp[i][t]}{x^{a+i+t}}}{a+i+j})x^{a+i+j}$

$\displaystyle =x^{a+i+j} + \frac{\sum_{t=0}^{i-1} f[t][j]{x^{i-t}}+ \sum_{t=0}^{j-1} dp[i][t]{x^{j-t}}}{a+i+j}$

没有什么用

再就是$f[i][j]=f[j][i]$

令$g[i][j]=\sum_{t=0}^{j}dp[i][t]$有$dp[i][j]=g[i][j]-g[i][j-1]$, 也就是第二维前缀和，注意$g[i][j]$ 不一定等于$g[j][i]$

令$h[i][j]=\sum_{t=0}^i g[t][j]$,有$g[i][j]=h[i][j]-h[i-1][j]$, 也就是 两个 维前缀和, 且$h[i][j]=h[j][i]$

$\displaystyle dp[i][j] = 1 + \frac{\sum_{t=0}^{i-1} dp[t][j]+ \sum_{t=0}^{j-1}dp[i][t]}{a+i+j}$

$\displaystyle dp[i][j] = 1 + \frac{g[j][i-1]+g[i][j-1]}{a+i+j}$

$\displaystyle g[i][j] =\sum_{t=0}^{j} dp[i][t] = \sum_{t=0}^{j} (1 + \frac{g[t][i-1]+g[i][t-1]}{a+i+t})$

然而 第二个 无法合并

不如直接跳过g看 $h$和$dp$的关系

$h[i][j] = h[i-1][j]+h[i][j-1]-h[i-1][j-1]+dp[i][j]$, 所以如果能快速算h,则可以快速算dp

$\displaystyle dp[i][j] = 1 + \frac{\sum_{t=0}^{i-1} dp[t][j]+ \sum_{t=0}^{j-1}dp[i][t]}{a+i+j}$

$\displaystyle dp[i][j] = 1 + \frac{(h[i-1][j]-h[i-1][j-1])+(h[i][j-1]-h[i-1][j-1])}{a+i+j}$

$h[i][j]=1+(1+\frac{1}{a+i+j})h[i-1][j]+(1+\frac{1}{a+i+j})h[i][j-1]-(1+\frac{2}{a+i+j})h[i-1][j-1]$

还是没啥用

不过这里的一个想法是既然 是线性变换了，如果能消掉常数 变成纯线性变换会不会更好

也不行

题解

也是一样 考虑上下左右 有dp,但是4次方状态, TLE

转化是 A,B,C,D,E 个不同颜色 有数字序号的球，分别对应 上下左右中

那么 考虑 E类 球首次出现位置的期望，和我想的一样的，因为有丢球的过程的所以这个期望并不是答案

所以如果 一个球前面出现了相同颜色更小数字的球，需要忽略这个球

直观地说，我们可以从前往后选择序列中的球，扔掉应该忽略的球（不要合并同样的结果），而不会改变相关球的概率！？！？！？！？！？！？！？！？！？！？！？！？！？！？

期望的线性 关系可以相加！

所以 颜色互不影响，计算 (颜色,序号i) 出现在 E之前的概率

也就是 它在 （同色更小，它自己，所有E球）中最早出现的概率 也就是$\frac{1}{i+a}$

下面 $p(球id出现概率) = p(全排列中 球id出现 且 满足 在黑色之前和比自己小的之前 的概率)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ab|cd（cd是目标切线

所有顺序有

abcd  : abc
abdc  : abd

acbd  : ac
acdb  : ac
adbc  : ad
adcb  : ad
bacd  : bc
badc  : bd
bcad  : bc
bcda  : bc
bdac  : bd
bdca  : bd

c...  : c
d...  : d

那么就是$1+0\frac{1}{2}+1\frac{10}{24}+2\frac{2}{24}=1+\frac{1}{1+2}+\frac{1}{2+2}$

我感觉最卡的是 这两个概率的样本空间不一样，一个是 所有压缩后的状态（也就是题目直接求的问题），另一个是全排列

这里$a$的贡献是$\frac{1}{4}=\frac{6}{4!}$,$b$的贡献是$\frac{1}{3}=\frac{8}{4!}$

1
2
3
4
5
6
7
8
9
注意： 不要合并！！！！！！， 合并以后 a=1/2,b=1/2
abc
abd
ac
ad
bc
bd
c
d

所以上面的例子是：

例如选了$b$ 那么剩下的按照题目就是在$cd$中选了，是等概率的

但是如果加上$a$,变成$acd$

1
2
3
axx
xax
xxa

这三种方案的每个方案内和a无关的 部分的概率是不会变的，而都乘上1/3相加和没有a是一样的

而这里只需要a不被统计就好了，要统计的c或者d的关系是不受影响的

更大一点

1
aaaaaa|bbbbbb|cccccc|dddddd|eeeeee

目前选了 (a,i) 还没被选的 与a无关的 bbbcccdddeee...

那么

1
2
3
4
5
bbbcccdddeee... 的全排列 内部之间的关系

和 插入了(a,<i)的 以后，不影响上面内部关系的概率，而这些点本身0贡献

a0xxa1xxa2xxxxxxx

还看到一个题解 说

相当于每次选线永远不重复，但是不需要抛弃空白块，而是如果选的切割位置已经被切割，只需要当前不计算次数，重新选一个就好了

所以次数贡献 只有合法的被选的，

代码

https://atcoder.jp/contests/arc114/submissions/50622337

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
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
mint I[200010];
int main(){
  I[1]=1;
  rep(i,2,200000+1) I[i]=(MOD-MOD/i)*I[MOD%i];
  int n=read();
  int m=read();
  int a=read();
  int b=read();
  int c=read();
  int d=read();
  if(a>c) swap(a,c);
  if(b>d) swap(b,d);
  int e=c-a+d-b;
  mint ans=1;
  for(int u:{a-1,n-c,b-1,m-d})rep(i,1,u+1)ans+=I[i+e];
  printf("%d\n",ans.val());
}

F - Permutation Division

给定一个1..n的排列p

把p切割成 恰好k个非空连续子序列

Maroon会把你切割好的合并成Q，他会让Q字典序尽量大，而你希望让Q字典序尽量小

输出Q

n 2e5

2s

1024mb

我的思路

题目简洁

首先啊， 如果切割了，那么新拼起来的比原来更大，那么他会选择新的，否则他直接用原串就好了

所以Q字典序上一定不小于原串

那么问题来到，如果有k-1个$<P[0]$数，那么从这些位置切开

因为 都 $<P[0]$ 所以新的开头至少是$p[0]$

而后面的段是可以随便排序

1
2
3
4
5
6
7
8
9
10
11
12
p: [....................]
        [               ]
        切1次 最小的一定可以切

但切2次，不一定是最和次的

   [4...................]
        2
             3
                  1
        [        ][     ] 2和1
             [   ][     ] 3和1 这种方案得到的更好

而可以变成

1
2
p: [p[0]...............] f(p    ,k)
        [t.............] f(p[t:],k-1)

令 f(p,k) = 答案

那么 如果有 多余k-1个 <p[0], 那么选择其中一个位置t, 考虑后缀的子问题

但这里的问题是 后面内部是可以颠倒顺序的，但也要保持 <p[0]才行，这会增加一个维度的状态

而注意到maroon 是让序列增大

所以 评价一个 后缀的切割方法， 可以评价是否有不换 p[t]的切割法

$s(a,k)=$ bool(把 a切成k段 存在 让a[0]不变的方案)

而这很好判断，就是上面的性质 有>= k-1个 < a[0]的值即可,倒着算用fenwick可以 nlogn 处理好

那么对于$f(p,k)$

如果 $s(p,k)=True$,

如果

  • 存在$t$使得$a[t] < p[0],s(p[t:],k-1)=True$, 那么从最前面的t开始切割？？？ 最优性证明？？
  • 如果不存在，则找最后几个k-1个 $>p[0]$的点开始切割，为了保证变化离头部尽量远，也就字典序最小

第一个 有反例

1
2
3
4
5
6
这里举例x足够大, 主要为了表现大小关系，实际把它们离散化压缩一下就是一个实际的例子
max x 2x x-2 2x-1 x-1 2x-2

这里 从x切和2x切都可以保持自身不被换，但是
[  ][   ][       ][      ] 这会让x-2的地方被换
[    ][     ][       ][  ] 这会完全不会被换

也就是说就算保证开头不会被换 也保证不了后续不会被换

那这个观察就再极端一点，如果要全部不会被换，就需要单调递减序列（这里是排列两两不等，所以是严格单调递减序列）

$c(p) =$序列$p$完全不被换的最大切割数=以p[0]开头的最长单调递减子序列，这个可以 dp+fenwick 或者(优先队列+二分) O(n log n)算出所有位置

所以 对于序列p，和k段

  • 如果可以完全不被换 则完全不被换的
  • 如果可以保证头不被换用头不被换的
  • 如果头会被换则让头尽量小，也就是k（因为k段k个头，最少是k,且p[0] <= k)

问题还是 第二段

序列 能保证 头不被换，但保证不了全部不被换

  • 对于后续 头要换 就贪心最后几个
  • 但是头不换 似乎没啥判断方法
1
2
3
4
5
6
7
8
max  
        6
               5
              4
     3
             2
          1
[      ][   ][][] 6 [4<->5] 换影响的位置更远？

重新思考 选的切割点的结构

1
2
3
4
5
6
7
x0 
    x1
        x2
           x3
              [...<x3...]
               i
            j

应该是一个 下降序列 拼上一个 小于 序列末端的 ，然后让下标i尽量大

所以枚举 下降序列的末端位置j

计算 后面[<a[j]] 的倒数 第k-(j到p[0]长度)的下标

左侧面很好算, 右侧如何算? 又要值小于 又要第xx个

一个 强行的做法就是持久化线段树，下标存值的个数，然后root[时刻] 支持二分

似乎这样能做？

https://atcoder.jp/contests/arc114/submissions/50623295

ACx38 WAx2 ?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

问题 在于

1
2
3
4
5
6
7
    i      [......]
  j        [......]
因为i,j不同 后面可选值 个数 和范围都不同，但是有可能 后面的起点都一样！！！
所以 不光要起点更靠后，还要 后面的可选点个数更少！！！！！

            v 
           这两个区间里都是 <= （某个值）的所有值，所以 （某个值）越小，个数越少！

代码

https://atcoder.jp/contests/arc114/submissions/50624050

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
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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 SEG_ROOT(r) r,0,n+1
#define SEG_L seg[o].l
#define SEG_R seg[o].r
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

struct node{
  int l=-1;
  int r=-1;
  int v=0;
};
vector<node>seg;
int newnode(){
  int t=seg.size();
  seg.push_back(node{-1,-1,0});
  return t;
}

ll read(){ll r;scanf("%lld",&r);return r;}
int n;
vector<int>p;

void pick(vector<int>pos){
  vector<int>isst(n,0);
  vector<pair<int,int> > st;
  for(auto i:pos) {
    st.push_back({p[i],i});
    isst[i]=true;
  }
  sort(begin(st),end(st),[](auto x,auto y){return y<x;});
  for(auto [v,stp]:st) {
    rep(i,stp,n){
      if(i!=stp and isst[i]) break; // 到下一个起点了
      printf("%d ",p[i]);
    }
  }
}

int query(int o,int l,int r,int ql,int qr){ // [l,r) [ql,qr)
  if(o==-1) return 0;
  if(ql <= l and r <= qr) return seg[o].v;
  int ret=0;
  if(ql < mid) ret += query(SEG_L_CHILD,ql,qr);
  if(qr > mid) ret += query(SEG_R_CHILD,ql,qr);
  return ret;
}

int add(int o,int l,int r,int p){
  assert(1<=p and p<=n);
  if(l+1==r){
    assert(o==-1);
    int v=newnode();
    seg[v].v=1;
    return v;
  }
  int v=newnode();
  if(o!=-1) { // clone
    seg[v].l=seg[o].l;
    seg[v].r=seg[o].r;
  }

  if(p< mid) seg[v].l=add(seg[v].l,l,mid,p);
  if(p>=mid) seg[v].r=add(seg[v].r,mid,r,p);

  seg[v].v = 0;
  if(seg[v].l!=-1) seg[v].v+=seg[seg[v].l].v;
  if(seg[v].r!=-1) seg[v].v+=seg[seg[v].r].v;
  return v;
}

int main(){
  n=read();
  int k=read();
  p.resize(n);
  rep(i,0,n) p[i]=read();
  if(k>=p[0]) { // 一定变 开头选1~k
    vector<int>pos;
    rep(i,0,n) if(p[i] <= k) pos.push_back(i);
    pick(pos);
    return 0;
  }

  vector<int> sz(n,0);
  sz[0]=1;
  vector<int> pre(n,0); // 最长严格下降上一个节点
  vector<int> idx; // val, 值严格下降, 个数=下标+1
  idx.push_back(0);
  rep(i,1,n) if(p[i] < p[0]){
    int l=0;
    int r=idx.size();
    while(r-l>1){ (p[idx[mid]] > p[i]?l:r) = mid; }
    pre[i] = idx[l];
    sz[i]=r+1;
    if(r < (int)idx.size()) {
      if(p[i] > p[idx[r]]) idx[r]=i;
    }else{
      idx.push_back(i);
    }
  }
  rep(i,0,n) if(sz[i] >= k) { // 可以完全不变
    pick({0});
    return 0;
  }
  vector<int> roots={-1}; // [n, n-1,....]
  array<int,3> best={-1,-1,-1}; // 后缀选择起始下标, 选点个数, 前缀单调下降最后一个起始值下标（比较值下标)
  per(i,0,n) {
    if(p[i]<=p[0]){
      int s = sz[i];
      assert(s<k);
      // 后面 选 k-s 个 < p[i]的
      int c=query(SEG_ROOT(roots.back()),1,p[i]);
      if(c >= k-s) {// 能选出k-s个<p[i]
        int l=0;
        int r=roots.size()-1;
        while(r-l>1) (query(SEG_ROOT(roots[mid]),1,p[i]) >= k-s ?r:l)=mid;
        // {n-r,i}: n-r开始<p[i]}
        if(n-r > best[0]){
          best = {n-r,k-s,(int)i};
        }else if(n-r == best[0]){ // 起始相等 待选点越少越好
          if(k-s < best[1]) {
            best = {n-r,k-s,(int)i};
          }
        }
      }
      roots.push_back(add(SEG_ROOT(roots.back()),p[i]));
    }else{
      roots.push_back(roots.back());
    }
  }
  assert(best[0] != -1);
  auto [si,_,pi] = best;
  assert(pi<si);
  vector<int> pos;
  rep(i,si,n) if(p[i]<p[pi]) pos.push_back(i);
  int i=pi;
  while(true){
    pos.push_back(i);
    if(i==0) break;
    i=pre[i];
  }
  assert((int)pos.size()==k);
  pick(pos);
  return 0;
}

Ref

https://atcoder.jp/contests/arc114

总结

D: 分析能力 和 题意处理还是很差，这个“线段的属性”和“点的属性”的转换还是很妙，这样去掉线段就自然很多,这道题 我觉得很棒，值得推荐

E: 概率论完全不会

这里的技巧我觉得是，把单次的 概率直接忽略掉，变成 转化所有操作方案对应一个新的状态

那么直接 计算 新状态里的 单点概率贡献 而不关心单次操作的概率

概率的独立性 完全不会啊

有人说 这题很Edu,我觉得有被edu到

F: 感觉D,E比F难啊，虽然想漏了一个细节，但不太需要智力，持久化线段树数据结构搞一搞

感觉我的思路比题解更直接只是代码长，只要逻辑没有错误main里的调用都很自然，题解稍微不一样的是分析了前缀的单调性，所以二分前缀一致的，然后前缀不同段数的最大结束值去找后缀的个数，然后数据结构可以更简单用set