10.1

其实名义上算是集训第二天，但是才开坑日结。

主要是想记录一下今晚的 ABC C题，这场大概是最丢人的一场 ABC ，赛时交了 $9$ 发没调出 C 题，最后俩题离场直接下 $50+$ 分。。

所以赛后看了看C的最短解，找到了优美的解法，看了看代码分析出来了他的思路整理在这里。

题意是这样的 ： ABC271 C

Problem Statement
Takahashi is going to read a manga series “Snuke-kun” in $10^9$ volumes.
Initially, Takahashi has N books of this series. The i-th book is Volume $a_i$ .

Takahashi may repeat the following operation any number of (possibly zero) times only before he begins to read:

  • Do nothing if he has 1 or less books; otherwise, sell two of the books he has and buy one book of any volume instead.

Then, Takahashi reads Volume $1$, Volume $2$, Volume $3$, …, in order. However, when he does not have a book of the next volume to read, he stops reading the series (regardless of the other volumes he has).

Find the latest volume of the series that he can read up to. If he cannot read any, let the answer be $0$.

（英文原题面

不太会表达这个意思但是既然我赛时都能看懂肯定并不是高深的英文。

（所以不翻译了）

重点的性质 ：

  • 重复的较小数和肯定取不到的大数是等价的，我们都称之为 ： 多余的数。

最好情况是没有“多余的数”，此时答案为 $n$ 。

每当在前边出现了一个数的 “缺失” ，我们就需要用两个数大于等于他来弥补这个缺失，最好情况是我们使用了两个多余的数，否则我们会选择删去最大数。

  • 但是无论如何，一个数的 “缺失” 至少需要消耗两个数来弥补，这使得我们答案的上界减少了 $1$

所以如果我们从 $1$ 到 $n$ 进行扫描来统计答案，我们似乎应当在有一个数 “缺失” 时将我们的枚举上界减小 $1$ 。

枚举上界减小之后，之前恰好卡在枚举上界的数就也成为了 “多余的数”。

考虑如何维护多余的数。

发现我们的数当中除了有用的就是多余的，

所以我们实际上不需要维护有哪些多余的数，考虑问题的本质，容易发现多余的数真的完全是多余的 因为它并不影响我们答案 上界 每次减 $1$ （注意说的是上界）

所以直接抛开多余的数这个概念，维护 $1 \sim n$ 的数是否出现过，枚举时直接改变枚举上界即可。

似乎还是没说的很清楚，所以放一下代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&a);
        if(a <= n)
        x[a] = 1;
    }
    for(int i = 1;i <= n;i++)
    if(!x[i]) --n;
    printf("%d",n);
    return;
}

这显然不是 ABC C题的难度所以实际上显然是一个爆标做法……而且也完全是优雅的。

看到这个做法之后非常高兴所以记录下来。

10.3

交通规划的代码实现怎么写啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊aaaaaaa

题

9.30

B

P3616 富金森林公园

线段树或者树状数组维护前缀和。

赛时想到了正解。

C

DP

发现一个值的正负只与前边当前失配的左括号数量的奇偶性有关。

然后根据这个来写转移就行了

1
2
3
4
5
6
7
8
9
10
if (opt == '+') {
    f[i][0] = max(f[i - 1][0] + x, f[i - 1][1] - x);
    f[i][1] = max(f[i - 1][1] - x, f[i - 1][2] + x);
    f[i][2] = f[i - 1][2] + x;
} 
else {
    f[i][0] = max(f[i - 1][0] - x, f[i - 1][1] + x);
    f[i][1] = max(f[i - 1][0] - x, max(f[i - 1][1] + x, f[i - 1][2] - x));
                f[i][2] = max(f[i - 1][1] + x, f[i - 1][2] - x);
}

就像这样。

10.1

A

注意可能会出现 l 和 r 之外的字母。

B

树的遍历板子题，秒了。

C

挺难维护的。

D

最短路，但事事DP。

容易发现答案只和障碍的最左边那条线有关，然后扔掉了右边界。

用一个 std::set 维护状态，然后转移就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(int i = 1;i <= n;i++)
{
    int mid = inf,miu = inf;
    auto itl = s.lower_bound(statu(0,m[i].yl,0));
    auto itr = s.lower_bound(statu(m[i].x,m[i].yr,0));
  
    while(itl != itr)
    {
        if(dis(itl -> x,itl -> y,m[i].x,m[i].yl) + itl -> d < mid) mid = dis(itl -> x,itl -> y,m[i].x,m[i].yl) + itl -> d;
        if(dis(itl -> x,itl -> y,m[i].x,m[i].yr) + itl -> d < mid) miu = dis(itl -> x,itl -> y,m[i].x,m[i].yr) + itl -> d;
        auto del = itl;
        itl++;
        s.erase(del);
    }
    if(mid < inf) s.emplace(m[i].x,m[i].yl,mid);
    if(miu < inf) s.emplace(m[i].x,m[i].yr,miu);
}

像这样。

10.2

A

进行一个式子的推，然后维护三个前缀和

B

考虑一下一个值能产生贡献的情况，然后发现一共有三个条件，但是第一个条件被后边包括了，所以变成二位偏序问题，求 LIS 。

然后做完了。

D

第一次见这样的DP

对原图形式上构建笛卡尔树，递归求解，用儿子信息来更新父亲。

分开考虑黑白相间和出现了连续两块同色的情况。

10.3

A

简单题，注意读题

B

$k = 1$ 时，原序列异或和就是答案。

$k = 2$ 时，原序列异或和就是答案的异或和。

对每个二进制位维护这一位为 $1$ 的数的异或和，容易发现这个异或和最后只在两个答案不同的二进制位上有值，值是其中一个答案。

然后就非常简单了。

D

求 OEIS A290011

然后就有答案的公式 :

复杂度瓶颈在于求 $1e9$ 的阶乘。

发现不会快速阶乘算法，然后分段打表，每 $1e7$ 打一次，一共一百个数。

然后过了(

10.4

打了三场比赛。

luogu公开赛div1首次进rank30祭（虽然都是水的分而且后来不打了也掉到52了

有两场某原题大赛的题。

上午 ： 原题大赛一

A

贪心，倒序枚举即可

B

倒序枚举最大高度，然后贪心维护一下最小宽度即可

C

DP

发现每列之间没有相互影响，但是每列只能放一个——每行之间有影响。

于是考虑列，把所有行看成一行。

发现可以把限制转化成前缀放一个和后缀放一个。

于是转化限制，维护每个位置及之前有几个前缀限制和后缀限制的端点

对于每一列只需要考虑是满足前缀限制还是后缀限制即可，分类讨论这两部分，用基本组合知识（大概 合并贡献即可。

最后再把所有行拆开，因为没有相互影响所以再乘上一个排列数。

就没了。

D

期望题，还没补完坑。

下午 ： luogu某公开赛

2A

签到题。

观察题目本质之后发现 lowbit 变大当且仅当从奇数变成偶数，于是变成统计区间内奇数个数。

然乎非常简单了。

2C/1A

虽然有意外重题但是意外重题也没做过（

先离线询问。

把询问标记到树上，先dfs找到直径一端，从这一段再做一次到达直径另一端，中途统计一半答案

再从直径另一端统计回来，更新另一半答案。

应该是最简单的做法，复杂度也是优秀的 $O(n + k)$ ，缺点在于必须离线以及常数略大。

于是给出某卡常后的代码实现，其中略去快读

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<cstdio>
#include<vector>
namespace Pozhu{
using namespace std;
#define N 2000001
#define int unsigned int
struct node{
    int k,id;
    node(int _k,int _id) : 
    k(_k),id(_id){}
};

namespace G {
    int to[N*2], next[N*2];
    int head[N], ecnt;
    inline void add_edge(int a, int b)
    {
        ecnt++;
        to[ecnt] = b;
        next[ecnt] = head[a];
        head[a] = ecnt;
        ecnt++;
        to[ecnt] = a;
        next[ecnt] = head[b];
        head[b] = ecnt;
    }
}
using G::add_edge;

vector<node>q[N];
int sta[N];
int ans[N];
int n,Q;
int rt,mxdis;
bool flag;

void dfs(int x,int fa,int dep);

void main()
{
    cin >> n >> Q;
    int x,y,k;
    int i;
    for(i = 1;i+2 < n;i+=2)
    {
        cin >> x >> y;
        add_edge(x, y);
        cin >> x >> y;
        add_edge(x, y);
    }
    if(i==n-1)
    {
        cin >> x >> y;
        add_edge(x, y);
    }
    for(register int i = 1;i <= Q;i++)
    {
        cin >> x >> k;
        q[x].emplace_back(k,i);
    }
    rt = 1;
    dfs(rt,0,0);
    mxdis = 0;
    flag = true;
    dfs(rt,0,0);
    dfs(rt,0,0);
    for(register int i = 1;i <= Q;i ++)
    {
        if(ans[i]) cout << ans[i] << endl;
        else cout << "-1"<<endl;
    }
    return;
}

void dfs(int x,int fa,int dep)
{
    if(dep > mxdis)
    {
        mxdis = dep;
        rt = x;
    }
    sta[dep] = x;
    if(flag)
    for(node i : q[x])
    {
        if(i.k <= dep) ans[i.id] = sta[dep - i.k];
    }
    for(int i = G::head[x]; i; i = G::next[i])
    {
        if(G::to[i] != fa)
            dfs(G::to[i], x, dep + 1);
    }
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

1E/2E

出现重题之后给的附加题。

背景图放了FC过的曲子的曲绘，感觉很熟悉。

然后做这个题

审题的关键在于看到这个 ：

然后结合这个数据范围 ：

所以发现一个数大的话另一个一定小。

于是想到根号分治。

实际上对暴力直接写个记忆化就能离奇通过，就像这样 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for(int i = 1;i <= q;i++)
{
    scanf("%d%d",&l,&r);
    if(mp.count(1ll * l * N + r))
    {
        printf("%lld\n",mp[1ll * l * N + r]);
        continue;
    }
    ll ans = 0;
    for(int i = 1;i <= k;i++)
    {
        ans = max(ans,a[i][r] - a[i][l - 1]);
    }
    printf("%lld\n",mp[1ll * l * N + r] = ans);
}

乐

晚上 ： 原题大赛二

其实我没找到原题，但是这个系列比赛之前都是原题，所以这样暂称

A

自己独立做出的大概是第一道期望题。

似乎有简单的做法，但我是大力推式子推出来的。

所以放一下题面，思路和代码，纪念一下。

题面 ：

小 K 将以一下方式生成一个序列：

初始时序列中只有一个数 $0$，接下来会依次生成 $m$ 个数。
生成第 $i$ 个数时，小 K 会从初始的 $0$、以及前 $i-1$ 个生成的数（总共 $i$ 个数）中等概率地选取一个数 $x$，则第 $i$ 个数为 $x + 1$ 。
每一个数 $i$ 都对应一个权值 $a_i$，小 K 想考考你，这样生成的数列，每个位置数的权值之和的期望是多少。

答案对 $998244353$ 取模。

规定 $a_0 = 0$

$1 \le m \le n \le 10^5, 1 \le m \le 21,0 \le a_i \le 10$

思路 ：

首先说白了那么大的数据范围都是唬人的玩意。。读入的时候只读入 $m$ 个啥事没有……因为最大可能出现的数是 $m$

观察发现这数列生成的过程像是一颗这样的树 ：

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
1 1 1 1
      2
      2
      2
     
    2 1
      2
      2
      3
     
    2 1
      2
      2
      3
    
  2 1 1
      2
      3
      2
    
    2 1
      2
      3
      3
     
    3 1
      2
      3
      4

（画的很抽象

然后可以得到以下规律 ：

前 $n$ 层数字的总个数是

这告诉我们暴力计算答案的复杂度至少是阶乘级别，我们无法接受。

然后前 $n$ 层数字中 $1$ 的总个数是

（左阶乘

考虑逐层统计贡献，发现我们只需要知道每一层中每一个数字出现的次数，而不需要知道它的具体位置，这为我们优化暴力提供了可能。

顺着这个思路想，我们设出以下函数 ：

$f(i,k)$ 表示第 $k$ 层有几个 $i$

$g(i,j)$ 表示以第 $i$ 层的一个节点为根的子树到第 $j$ 层的节点个数（也可以理解为深度为 $(j - i + 1)$ 的部分的叶子节点个数）

$g(i,j)$ 是容易计算的。显然原树上第 $i$ 层的每个节点会向下伸出 $(i + 1)$ 个分支，于是就有 ：

（实际上是一个类似上阶幂的东西）

所以 $g$ 容易计算，考虑如何计算 $f$ 。因为显然有了 $f$ 的值之后就容易统计答案了。

对于 $i = 1$ ，我们容易得到这个式子 ：

然后考虑由 $1$ 如何得到 $2$ 。

发现第 $i$ 层的 $1$ 对于第 $j$ 层的 $2$ 的个数的贡献就是以第 $i$ 层一个值为 $1$ 的节点的子树在第 $j - 1$ 层的叶子个数，即 $g(i,j - 1)$

然后我们显然得到了这个式子 ：

$n > 1$ 时 ：

于是我们就会处理 $f$ 了。

然后考虑剩下的简单的统计答案

设 $\varphi(i)$ 表示数 $i$ 对答案的的贡献（并不是某著名数论函数），那么综合以上内容我们可以计算$\varphi$ ：

其中除以 $d!$ 的原因是根据节点总数的式子我们可以得到每层的节点数是 :

所以每层的结点个数恰好是层数的阶乘……不过从分叉的方法来看这也是显然的。

然后显然答案就是 ：

于是我们做完了这道题，不是很难，好像也没有很大力的推式子……都是很基础的过程，也并没有涉及反演等数学知识。

最后放一下代码，代码中的变量命名和上文式子基本一致……毕竟当时是在看着草稿纸码代码，现在是在看着草稿纸写博客。

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>
namespace Pozhu{
using namespace std;
#define file
#define N 1010
typedef long long ll;
const ll mod = 998244353;

int n,m;
ll a[N];
ll fac[N];
map<ll,ll>mp;

ll phi(ll x);
ll g(ll x,ll k);
ll f(ll x,ll k);
ll ksm(ll a,ll b);

inline void main()
{
    scanf("%d%d",&n,&m);
    fac[0] = 1;
    for(int i = 1;i <= m;i++) fac[i] = fac[i - 1] * i % mod;
    for(int i = 1;i <= m;i++) scanf("%lld",&a[i]);
  
    ll ans = 0;
    for(int num = 1;num <= m;num++)
    ans = (ans + phi(num)) % mod;
    printf("%lld",ans);
    return;
}

inline ll phi(ll x)
{
    ll res = 0;
    for(int d = x;d <= m;d++)
        res = (res + a[x] * f(x,d) % mod * ksm(fac[d],mod - 2) % mod) % mod;
    return res;
}

inline ll g(ll x,ll k)
{
    return fac[k] * ksm(fac[x],mod - 2) % mod;
}

inline ll f(ll x,ll k)
{
    if(x == 1) return fac[k - 1];
    if(mp.count(x * m + k)) return mp[x * m + k];
    ll res = 0;
    for(int i = 1;i < k;i++)
    {
        res = (res + f(x - 1,i) * g(i,k - 1) % mod) % mod; 
    }
    return mp[x * m + k] = res;
}

inline ll ksm(ll a,ll b)
{
    ll ans = 1;
    for(;b;b >>= 1,a = a * a % mod) if(b & 1) ans = ans * a % mod;
    return ans;
}

}

signed main()
{
#ifdef file
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
#endif
    Pozhu :: main();
    return 0;
}

显然对函数 $f$ 的值记忆化可以大大减小计算量，预处理阶乘或许可以在求 $g$ 的时候减小个常数。

这份代码在加入记忆化之前可以跑过 $m = 24$ ，加了之后大概能跑到 $200+$ ，我现在还不能给出严谨的复杂度证明。

但是过这道题绰绰有余了。

UPD : zerc 发现这个是第一类斯特林数·行，然后 $O(n \log n)$ 过掉了，虽然常数很大在这题的数据范围不占优势。

记得取模一定要取够，对着草稿纸码代码容易忘记取模……然后直接挂大分。

这一场后边的还没改，先写到这，似乎T2可以用简单贪心水到满分（

10.5

A

直接枚举一手一次方。

发现最坏情况下会被卡到 $n^2$ ……而且真的有这样的构造数据（话说这数据多难构造啊怎么这都能整出来）

然后考虑剪枝，发现可以扔掉逆元也在原数列中的数。

毕竟保证数两两不同，然后 $a^{-1} \equiv a^{p - 2}$ ，数据范围保证了 $p - 2 > n$ ，于是答案的逆元一定不在数列中，于是证明了剪枝的正确性。

然后能过。

B

发现答案有单调性，于是二分答案。

验证时采用贪心，对最小的 $mid$ 个进行配对，正确性显然。

但是去掉二分的贪心是错误的，$hack$ 容易给出，这里不再赘述。

C

想到了倍增，但是其他地方的实现没想到，所以没做出来。

维护一个最大值和一个次大值，当最大值被 $ban$ 时使用次大值。

容易 $T$ ，然后维护倍增表示使用 $2^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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 200010
 
int n,m,q;
int l[N],r[N];
 
struct jump{
    int to,id;
    jump(){}
    jump(int _to,int _id) : 
    to(_to),id(_id){}
};
 
struct node{
    jump mx,dx;
    void add(jump b)
    {
        if(b.to > mx.to)
            dx = mx,mx = b;
        else if(b.id != mx.id && b.to > dx.to)
            dx = b;
    }
}a[N];
int f[N][30][2];
 
void main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        a[l[i]].add(jump(r[i],i));
    }
    for(int i = 1;i <= n;i++)
    {
        a[i].add(a[i - 1].mx);
        a[i].add(a[i - 1].dx);
        f[i][0][0] = a[i].mx.to;
        f[i][0][1] = a[i].dx.to;
    }
    for(int j = 1;j <= 20;j++)
    for(int i = 1;i <= n;i++)
    {
        f[i][j][0] = f[ f[i][j-1][0] ][j-1][0];
        f[i][j][1] = f[ f[i][j-1][1] ][j-1][a[f[i][j-1][1]].mx.id == a[i].mx.id];
    }
   
    int id,s,t;
    scanf("%d",&q);
    for(int i = 1;i <= q;i++)
    {
        scanf("%d%d%d",&id,&s,&t);
        int ans = 0;
        if(t < l[id]) id = 0;
        if(s < l[id])
        {
            for(int i = 19;i >= 0;i--)
            if(f[s][i][0] < l[id])
                ans += (1 << i),s = f[s][i][0];
            ans ++,s =f[s][0][0];
        }
        if(s >= t) 
        {
            printf("%d\n",ans);
            continue;
        }
        for(int i = 19;i >= 0;i--)
        if(f[s][i][a[s].mx.id == id] < t)
            ans += (1 << i),s = f[s][i][a[s].mx.id == id];
        ans++;
        s = f[s][0][a[s].mx.id == id];
        if(s < t) puts("-1");
        else printf("%d\n",ans);
    }
    return;
}
 
}   
 
signed main()
{
    Pozhu :: main();
    return 0;
}

D

发现题目要求的是加入某个区间内的边之后全图的连通块个数

写一个可撤销并查集（实现难度小于可持久化并查集）维护连通性

然后写一个线段树来维护区间，统计答案的过程就是线段树分治。

写的时候不禁想到了 IOI2021 Day1T1 candies

虽然好像没什么关系

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
#define N 200010
int cnt;
struct czbcj{
    int n,fa[N],siz[N];
    stack<ll> opt;
    void init()
    {
        iota(fa,fa+n,0);
        fill(siz,siz+n,1);
        while(opt.size()) opt.pop();
    }
    int find(int x)
    {
        while(fa[x] != x) x = fa[x];
        return x;
    }
    void merge(int u,int v)
    {
        if(!u || !v) return;
        u = find(u),v = find(v);
        if(u == v) return;
        if(siz[u] < siz[v]) swap(u,v);
        fa[v] = u,siz[u] += siz[v];
        opt.push(1ll * u * n + v);
        cnt--;
    }
    void split(size_t k)
    {
        stack<ll>use;
        while(opt.size() > k)
        {
            int u = opt.top() / n,v = opt.top() % n;
            use.push(opt.top());
            opt.pop();fa[v] = v;siz[u] -= siz[v];
        }
        while(use.size())
        {
            opt.push(use.top()),use.pop();
        }
        opt.push(0);
    }
    void back()
    {
        cnt++;
        int u = opt.top() / n,v = opt.top() % n;
        opt.pop();
        fa[v] = v,siz[u] -= siz[v];
    }
}f;
 
struct Tree{
    int u,v;
}t[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int ff[N];
 
int x[N],y[N];
vector<pair<int ,int > >s[N << 2];
int n,m,k,tp;
unsigned lans;
 
void build(int x,int l,int r);
void update(int x,int l,int r);
 
void main()
{
    scanf("%d%d%d%d",&n,&m,&k,&tp);
    f.n = n;f.init();cnt = n;
    ff[m + 1] = m + 1;
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    int q;
    if((k == 1 && n > m + 1) || (k == n))
    {
        scanf("%d",&q);
        if(k == 1 && n > m + 1)
        {
            for(int i = 1;i <= q;i++)
                puts("No");
        }
        else
        {
            for(int i = 1;i <= q;i++)
                puts("Yes");
        }
        return;
    }
    build(1,1,m);
    scanf("%d",&q);
    unsigned int l,r;
    for(int i = 1;i <= q;i++)
    {
        scanf("%u%u",&l,&r);
        if(tp)
        {
            l = (l + lans) % m + 1;
            r = (r + lans) % m + 1;
        }
        if(l > r) swap(l,r);
        lans <<= 1;
        if(ff[r] > l) puts("Yes"),lans |= 1;
        else puts("No");
    }
    return;
}
 
void update(int p,int l,int r,int ql,int qr)
{
    if(l >= ql && r <= qr)
    {
        s[p].emplace_back(x[ql],y[ql]);
        return;
    }
    int mid = (l + r) >> 1;
    if(mid >= ql) update(ls(p),l,mid,ql,qr);
    if(mid < qr) update(rs(p),mid + 1,r,ql,qr);
}
 
void build(int p,int l,int r)
{
    int tmp = f.opt.size();
    for(auto [u,v] : s[p]) f.merge(u,v);
    if(l == r)
    {
        ff[l] = ff[l + 1];
        while(ff[l] > 1) 
        {
            if(cnt <= k) break;
            f.merge(x[ff[l] - 1],y[ff[l] - 1]);
            if(cnt <= k) break;
            ff[l]--;
            if(ff[l] < l) update(1,1,m,ff[l],l - 1);
        }
        while(f.opt.size() > tmp)
            f.back();
        return;
    }
    int mid = (l + r) >> 1;
    build(rs(p),mid + 1,r);
    build(ls(p),l,mid);
    while(f.opt.size() > tmp)
        f.back();
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

10.6

A

要求通过交换相邻项使得序列成为单峰函数，序列从头到尾依次插入，每次插入后输出结果，不强制在线。

所以离线下来做。

首先显然要做一个逆序对。

然后考虑我们对于这个单峰函数的形状我们会把每个数放在什么位置。

发现我们会从小到大插入这些数，如果没放的数中下标比他大的比下标比它小的多就放前面，否则放后面。

一个数被新插入时，它肯定是放在后边，因为它下标最大。

但是当后边插入的数越来越多时，它会在某个临界位置之后去左边。

这个临界位置有单调性，可以二分。

可以在主席树上二分或者在bit上二分，后者码量小得多。

B

神奇区间DP

赛时考虑了一下区间DP，发现不会合并就没继续朝这个方向想。

实际上两个区间合并时应该是两边的价值减去共有的部分乘二，因为只有这部分放在最底下不用动。

然后共有部分可以预处理出来，这样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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define inf 0x3f3f3f3f
#define N 110
 
int n,m;
int f[N][N];
int dp[N][N];
int t[N][N];
int g[N];
 
void main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        fill(dp[i] + 1,dp[i] + n + 1,inf);
        for(int j = 1;j <= m;j++)
            cin >> f[i][j],
            g[j] = f[i][j];
        for(int j = i;j >= 1;j--)
        for(int k = 1;k <= m;k++)
            g[k] = min(g[k],f[j][k]),
            t[j][i] = t[j][i] + g[k] + g[k];
        dp[i][i] = t[i][i];
    }
    for(int len = 2;len <= n;len++)
    for(int l = 1,r = l + len - 1;r <= n;l ++,r ++)
    for(int k = l;k < r;k++)
    dp[l][r] = min(dp[l][r],dp[l][k] + dp[k + 1][r] - t[l][r]);
    cout << dp[1][n];
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

非常简短。

C

这里有一个不容易想到的贪心。

每次现枚举人，找到一个周围距离小于蓝莓糖果的糖果数最小的人。

如果这个人周围糖果数为 $0$ ，则无解。

否则枚举他周围的糖果，找到属于的人最少的糖果，从问题的集合中删掉这个糖果和这个人，表示一个匹配。

如果可以对所有人执行这个策略，那么有解。

这个策略中的匹配并不代表一定是当时状态下最近的糖果，但是一定可以找到一种喊人的顺序使得这一匹配成立……应该是这样。

我不能给出对于这个贪心的让人满意的证明。

10.7

A

折半搜索。

详见 “世界冰球锦标赛”

B

期望。

首先根据期望线性性转化问题，把两点之间距离变成深度和减去两倍的LCA深度（当然是期望）

然后考虑怎么求节点深度的期望。发现一个结点的深度是他父亲的深度加上边权。

算一个加权平均数也就是 ：

然后考虑如何求 LCA 的深度期望,假设 $u < v$ ，那么考虑一个跳父亲的过程，在 $u < v$ 时 $v$ 会一直向上跳到 $x$ ，直到 $x \le u$ ，此时的 $x$ 位置期望符合 $1 \sim u - 1$ 的加权平均数。。

于是这个期望与 $v$ 无关。

当 $u = x$ 时，期望深度为 $E(dep(u))$ ，否则把 $x$ 当作 $u$ , $u$ 当作 $v$ ,又是一个新的子问题。

所以可以递推求解。

2022.10.8博客字数10w祭

by Pozhu
2022.10.1 - 2022.10.8