E

原题链接

2300评分

大意

很难直接说 ，看原题目图片

大概就是10x10网格，从左下 横走到头，向上一层，再横走到头，再向上一层，这样走到左上角

每次步长 整数[1->6]等概率

其中有一些纵向梯子，梯子出度为0/1

只能停在 梯子下方时(立刻?)使用梯子，重叠的梯子不能切换,不能从上到下使用梯子, 不能在没有横着走的情况下连续使用梯子

如果 走的步数会导致超过终点那么他不会走

他会尽快走

求期望步数

数据范围

梯子数量<=100

题解

显然虽然我赛内 没有做出来，也知道基本知识点是 dp和概率论，然而我的概率论弱到爆炸

然后也是显然把二维降到一维

官方题解

先定义f函数 如果

i点没有梯子， f(i) = i;

i有梯子， f(i) = 梯子的目标;

i点到终点，的最小期望步数为$dp_i$

显然dp_100 = 0

$$dp_i = 1 + \sum_{r = 1}^{6} \frac{1}{6} \cdot \min(dp_{g(i, r)}, dp_{f(g(i, r))})$$ // 这里min是必要的 因为可能因为一些小梯子错过一些大梯子，不一定爬梯子更优

从i走 r=1->6步,到 i->i+r 或者

其中 当 $i+r<=100$时 $g(i, r) = i + r$ 否则 $g(i,r)=i$

作为一个 概率论弱菜，想说这里的期望步数竟然可以直接取min的咯????

以及为什么明明是 1/6 的前进概率，却可以反过来 还是按照1/6来算???

对于上面会超过终点，也就是$95 \leq i \leq 99$时

$dp_i = \frac{6}{100 - i} \cdot \left( 1 + \sum_{r = 1}^{100 - i} \frac{1}{6} \cdot \min(dp_{i + r}, dp_{f(i + r)}) \right)$

其实也是上面的式子，把其中 走 改为停在原地 $dp_i$再移项得到的

这里我卡了很久很久很久

大概最后能理解 的是

dp表示的是剩余期望步数,是一个最终结果值

如果考虑过程的话，每一次 i 会向 i+1~6 发送 (期望步数-1)*1/6

而计算 当计算到i时，小于i的所有都已经和最终结果相同了，所以对于dp[i]来说

dp[i][最终结果] = sum{dp[i-1~6][最终结果]-1}/6也是满足的

也就是 每次从i走1/6的概率 和反过来 看最终期望值，可以用一样的概率

然后对于尾部的思考 感觉还是没有直接思考出，但是用无穷级数得到一样的答案了XD

感觉自己概率论还是没有入门啊

当然题解的另外一个方法就是 直接模拟个1000次

每次至少前进一步，那么100步以后，就只剩下 最后几个，然后就没了，每轮的量也就100*6 随便搞啊 精度应该不会爆吧

代码

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 INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

// 10x10
// 左下->左上

// 蛇形路线
//
// 有纵向梯子
// 不能用连续的后一个梯子

int main() {
  int grid[10][10]; // 输入
  int arr[110]; // 可以用梯子到达的目标
  int flat[10][10]; // 映射为一维数组
  rep(i,0,10){
    rep(j,0,10){
      scanf("%d",grid[i]+j);
      flat[i][j] = (9 - i) * 10 + ((i & 1) ? j : 9 - j);
      arr[flat[i][j]] = flat[i-grid[i][j]][j];
    }
  }

  double dp[100];
  dp[99] = 0;
  per(i,0,99){
    double dpi = 0;
    int c = 6;
    rep(r,1,7){
      if (i + r >= 100) continue;
      dpi += min(dp[i + r], dp[arr[i + r]]) / 6;
      c--;
    }
    dp[i] = 6 * (1+dpi) / (6 - c);
  }
  printf("%.10lf\n",dp[0]);
  return 0;
}

参考

https://www.cnblogs.com/LLTYYC/p/11782276.html

问题难点分析

为什么可以反过来使用概率,反过来用不等于反着走，而且期望的事情，可以把dp[i]改成dp[i][过程中/最终值]来加深理解

然后就是自己能到自己的理解了，依照各个题解过程意思是等价代换 推新公式即可？

然后就是题目这里的梯子，其实是一个可选择的不消耗次数的传送门，当你停在门前时才可选择，不能路过时使用。

F

原题链接

2300评分

大意

t组测试数据

求 l<=x,y<=r中 满足 x+y==x^y的有序对(x,y)的个数

数据范围

0<=l<=r<=10^9

题解

如果一道题看上去像bitdp，长得像容斥原理，那么它就是 bitdp+容斥原理

假设 F(n,m)表示 a属于[0,n], b属于[0,m]

那么ans = F(r,r) - 2F(l-1,r) + F(l-1,l-1)

所以如果能计算F(n,m)即可

G[前i位][x 是否贴着上限][y 是否贴着上限]的方案数

贡献

G[i][false][false]:

x3 -> G[i+1][false][false]

(因为都没有贴着上限，所以x,y值无论填0/1都 依然没有贴着上限,由因为两个只能最多有一个1,所以只有(0,0),(1,0),(0,1)三种))

对于

G[i][false][true] / G[i][true][false] / G[i][true][true]

其中至少有 一个是贴着上限的，那么，贡献时注意是否上限，填写的时候不要超过上限

也注意x&y == 0 也就是x+y<=1

1
2
3
4
5

rep(x,0,2){
  rep(y,0,2-x){
    G[i][ln & ( x == ((n>>(30-i))&1) )][lm & ( y == ((m>>(30-i))&1) )] += G[i-1][ln][lm];`
  }
}

当然可以用滚动数组进行优化

代码

官方题解

https://codeforces.com/blog/entry/71080

直接设f(l,r)是l<=x,y<r的答案，也就是真的答案是f(l,r+1)

有f(0,r)=2r-1+f(1,r), 因为 (0,0),(0,1~r-1),(1~r-1,0)都合法 一共(2r-1)

如果l,r都大于0那么 f(2l,2r) = 3 f(l,r)

其实和上面的数位dp 推理很像， 这里是考虑最后一位， 只有3种可选的，且都合法，因为有2倍保证

然后再 把 l,r 不是2的倍数的 和2的倍数之间找出关联，最终可归约到 f(0,?) 即可

问题难点分析

第一个是 我有往数位dp想，但是没想到具体

一个是没有拆解成F(x,y)变成类似前缀和 或者说计算子矩阵和的样式

另外就是数位dp做的题太少，还是不够熟悉

问题还有就是 两种方法，只要在草稿纸上多画一画会变得简单很多。

虽然以前对两个的维度来做前缀，或者向下归约的题型做过，但实际操作 还是体现出了不熟练

容斥是没怎么用还是矩阵和数位dp

原题链接

tourist出的题！

大意

二叉查找树 节点有n个且

倒数第二层满节点

每个节点和左儿子 奇偶相反

每个节点和右儿子 奇偶相同

的方案数

结果mod 998244353

数据范围

1<=n<=1'000'000

3s

512MB

题解

塞内没看到sum of depths做了个假题

第一个思路直接 树上dp, dp[cnt][height][oddoreven] 表示总节点cnt,高度height的,root奇偶性为oddoreven的 方案数

然后dp表达式

1
2
3
4
5
6
7
8

dp[cnt][height][root is odd?] = 

sum{
  dp[left cnt][height -1/-2][root is odd ^ 1] *
  dp[cnt-1-left cnt][height -1/-2][even] *
}

其中注意保证性质

调完bug的代码TLE 11 见下面

因为一些编写过程的推理问题，遗留的height,其实当cnt确定，根据题目的要求，height也就唯一了，算是多设计的

因为每次计算时 计算的子来源大概有 cnt/2左右个

代码

TLE 11

代码

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

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
// 1 -> 3 -> 7(C(4,4)) -> 15 -> 31 -> ...
// 4(C 4,1) 5(C 4,2)
 
//    ji
// ou     ji
//ji     ou      ou  ji
//ou ji ji ou  ji ou ou ji
 
 
// dp[cnt][height][ji/ou]
 
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
// sum of depths !
 
ll dp[1000010][22][2];
 
int v2h(int v){
  int ret = 0;
  while(v){
    ret++;
    v>>=1;
  }
  return ret;
}
 
int h2v(int v){
  return (1<<v)-1;
}
 
ll dfs(int cnt,int height,int jiou,int dep=0){
  // rep(i,0,dep){
  //   printf("\t");
  // }
  // printf("call dfs(%d,%d,%d)\n",cnt,height,jiou);
 
  ll &ret = dp[cnt][height][jiou];
  if(ret != -1)return ret;
  if(height == 1){
    return ret = (cnt == 1 && jiou == 1);
  }
  if(height == 0){
    return ret = (cnt == 0);
  }
  if(cnt > h2v(height) || cnt <= h2v(height-1))return ret = 0;
  ret = 0;
  int r = h2v(height-1);
  int l = cnt-1-r;
 
  rep(i,l,r+1){
    if(i%2 == jiou)continue;
    int hl = v2h(i);
    int hr = v2h(cnt-1-i);
    if(hl != height-1){
      if(hl != height-2 || hl > 1)continue;
    }
    if(hr != height-1){
      if(hr != height-2 || hr > 1)continue;
    }
    if(!(hr == height -1 || hl == height -1))continue;
 
    ll lcnt = dfs(i,hl,jiou^1,dep+1);
    ll rcnt = dfs(cnt-i-1,hr,0,dep+1);
 
    // rep(i,0,dep){
    //   printf("\t");
    // }
    // printf("dfs(%d,%d,%d) %d-1-%d : {l * r}={%lld * %lld}\n",cnt,height,jiou,i,cnt-1-i,lcnt,rcnt);
    (ret+=lcnt*rcnt)%=MOD;
  }
  // rep(i,0,dep){
  //   printf("\t");
  // }
  // printf("ret dfs(%d,%d,%d)=%lld\n",cnt,height,jiou,ret);
  return ret;
}
 
int main(){
  int n;
  cin>>n;
  int h = v2h(n);
  rep(i,0,1000001){
    rep(j,0,22){
      rep(k,0,2){
        dp[i][j][k] = -1;
      }
    }
  }
  cout<<(dfs(n,h,0)+dfs(n,h,1))%MOD<<endl;
  return 0;
}

果然tle了

AC代码 … TODO

原题链接

大意

前m个字母的所有排列中

对于字符串s

求min{sum{f(s[i-1],s[i])}} ，i = [1,len(s)-1]

f(char1,char2) = 在所选排列中 这两个char的下标差的绝对值

数据范围

1<=m<=20

1<=len(s)<=100000

1s

256MB

题解

显然把 字符串处理为统计信息一个m*m的表M

其中M[char1][char2]表示 字符char1和char2相邻的次数

然后看到 20/12都应该想一想 bitdp

dp[state] 表示前 bitcount(state)个数选择了state时的最优代价;

那么我们在 这个状态后面 添加一个未选取的数v

那么 [选取的数的状态][数字v]

问题来了

前面的最优状态如果没有具体位置,那么 v到已经选择的数字的 距离不同，所以权重也就不同,而即使 在最优代价中加上具体状态的记录，也不满足 子最优必定父最优

怎么把 选取的数字的顺序无关化?

考虑已经完全选好的一个排列

xyzabc

那么这个贡献 也就是 dis(x,y)*M[x][y]+dis(x,z)*M[x][z]+....+dis(b,c)*M[b][c]

如果我们画图把 这些点用线连起来

从中间切一刀，例如从xyz|abc这里切分, 会发现 a连出的线条数和 左边排列顺序无关，只和左边个数以及a相对于分割线的位置有关，

考虑 xyz|abc -> xyza|bc ,xya|zbc -> xyaz|bc

所以上面dp[state]的描述 改为 bitcount(state)个数选择了state时，且向右连线到分界线时的最优代价

注意新的分界线 增加的值和老的分界线 没有关系 所以只需要 O(m^2 * 2^m)而不是 m^3

代码

source

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

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
int n,m;
char s[100010];
 
int cnt[30][30];
ll dp[(1<<20)+10];
 
int main(){
  cin>>n>>m;
  scanf("%s",s);
  rep(i,1,n){
    cnt[s[i-1]-'a'][s[i]-'a']++;
    cnt[s[i]-'a'][s[i-1]-'a']++;
  }
  rep(state,1,1<<m){
    int ii = state;
    dp[state] = 0x3f3f3f3f;
    while(ii){
      int bit = ii & (-ii);
      ll costbit = dp[state^bit];
      dp[state]=min(dp[state],costbit);
      ii^=bit;
    }
    // 增加切割的分界线即可
    rep(i,0,m){
      if(!(state & (1<<i)))continue;
      rep(j,0,m){
        if(state & (1<<j))continue;
        dp[state]+=cnt[i][j];
      }
    }
  }
  cout<<dp[(1<<m)-1]<<endl;
  return 0;
}

C

大意

求sum{f(x)},x取值为 [0,X]的所有

其中f(x) = x以N位二进制表示(x<2^N,不足的补前导零),把最右的二进制位 取反 放到最左，这样操作?次后变回原样

结果mod 998244353

数据范围

1<=N<=200000

0<X<2^N

2s

1024MB

例

N=5 x=3时

00110 -> 10011 -> 01001 -> 00100 -> 10010 -> 11001 -> 01100 -> 10110 -> 11011 -> 01101 -> 00110

f(3) = 10

题解

显然2N次一定能回到原来的数

又假设 循环节最小为k，那么一定所有循环节为k的倍数，所以2N一定是k的倍数

又N次移动一定是何原来所有位取反 一定不相等

所以2N/k 一定是奇数

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

[xxxxxxxxxxxxxxxxxx]
[移动k][xxxxxxxxxxxxxxxxxx]

[ 长度 N                ][        原字符串取反N ]
[ 长度 2N                                       ]
[长度k][长度k][长度k][长度k][长度k][长度k][长度k]
       [长度k][长度k][长度k][长度k][长度k][长度k][长度k]
                        |这里k是偶数 刚好对半分

[长度k               ]
[长k后一半][长k前一半] 取反

所以 [长度k] = [长度k前一半] + [长度k前一半]取反

所以可行串又可以看做

[串A][~串A][串A][~串A][串A][~串A]...[串A][~串A][串A]

然后容斥 枚举k

时间复杂度 = O(N * N因数个数+ N log(N) )

我们把上面 串A 的长度 定义为循环节长度

容斥的部分

先假设所有的循环都是2n,那么 答案为(X+1)*(2n)%MOD

假设长度len循环节有f(len)个可行方案，那么对答案的变化为 +f(len)*(len-2n)%MOD

容斥原理 len的 权重为 = (len-2n) - ans(len的2次以上倍数)

h(len) = len-2n - sum{h(k * len)}, 其中k>=2且 长度k*len 可行

代码

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

char s[200010];
int n;
int ans;
int val[200010]; // val[i]表示以 i为循环节长度的方案数
vector<int>divs; // 所有 2n/2divs[idx] 为奇数


// 以 s[0..len-1]为 循环节 [正][取反][正]这样产生的长n的字符串的 方案数
ll cnt(int len) {
  int ans = 0;
  rep(i,0,len){
    ((ans*=2)+=s[i]-'0')%=MOD;
  }
  // [0.........................n]
  // [0...len][反0...len][0...len]
  // s>=t ans+1
  // t>s ans+1
  // 因为统计了全零所以+1, 如果t比s大那么[0..len]作为循环节不行,把 [0..len] 值减1可行 所以 全零+1,再-1就是ans
  rep(i,0,n){
    char ti = ((s[i%len]-'0')^((i/len)%2))+'0';
    if (s[i] > ti) return ans + 1;
    if (ti > s[i]) return ans;
  }
  return ans + 1;
}

int main() {
  cin>>n;
  scanf("%s", s);
  rep(i,1,n+1){
    if (n % i == 0 && (n / i) % 2 == 1){
      divs.pb(i);
    }
  }
  ll ans = cnt(n) * (2 * n) % MOD; // 全部都是2n 次
  per(idx,0,divs.size()){
    int i = divs[idx];
    val[i] = (2*i-2*n) % MOD;
    rep(j,idx+1,divs.size()){
      if(divs[j] % divs[idx] == 0){
        (val[i]-=val[divs[j]])%=MOD;
      }
    }
    (ans += cnt(i) * val[i] )%=MOD;
  }
  cout<<(ans+MOD)%MOD<<endl;
  return 0;
}

D

大意

到(0,0) 长度为1上的一系列点

随机选这些点形成的三角形的内切圆的圆心期望坐标

数据范围

圆上点的个数<=3000

4s

1024MB

题解

https://codeforces.com/blog/entry/70291 不少人吐槽 觉得这是 数学奥林匹克的题

假设选的三角形为$\Delta ABC$,做三个角的角平分线分别交$\Delta ABC$ 外接圆于点$A_1,B_1,C_1$

因为是角平分线所以显然，角平分线的交点就是要求的内心

$A_1,B_1,C_1$分别为$\widehat{BC},\widehat{CA},\widehat{AB}$的中点 (圆周角知识)

假设圆周上点的顺序为$A,C_1,B,A_1,C,B_1$

下面证明$\Delta ABC$的角平分线是，$\Delta A_1B_1C_1$的垂线

对称性只需要证明 $AA_1 \perp B_1C_1$

$\angle AC_1B_1+\angle A_1AC_1$

$= \angle ABB_1+\angle A_1AB+\angle BCC_1$

$= (\angle ABC+\angle CAB+\angle BCA)/2$

$= 90^\circ$

综上$\Delta ABC$的内心为 $\Delta A_1B_1C_1$的垂心

$A_1B_1C_1$的外接圆也是单位圆所以$A_1B_1C_1$的外心为$(0,0)$

假设$\Delta ABC$的 外心 垂心 重心分别为$O,H,G$

下面证明欧拉线 即 $3\cdot\vec{OG} = \vec{OH}$

即$O,H,G$三点共线且 分割线段长度为 $1:2$

注意到 $\vec {GA} = \frac{\vec {BA}+\vec {CA}}{3}$

所以有 ${\displaystyle {\vec {GA}}+{\vec {GB}}+{\vec {GC}}=0.}$

$3\cdot \vec{OG}$

$= (\vec{OA}+\vec{AG}) + (\vec{OB} + \vec{BG}) + (\vec{OC} + \vec{CG})$

$= \vec{OA}+\vec{OB} + \vec{OC} + (\vec{AG}+\vec{BG}+\vec{CG})$

$= \vec{OA}+\vec{OB}+\vec{OC}$

注意到

$(\vec{OA}+\vec{OB}+\vec{OC}-\vec{OH})\cdot \vec{BC}$

$=(\vec{OA}-\vec{OH})\cdot \vec{BC} +(\vec{OB}+\vec{OC})\cdot \vec{BC}$

$=\vec{HA}\cdot \vec{BC} +(\vec{OB}+\vec{OC})\cdot \vec{BC}$

$=0$

因为HA垂线所以前一半0

因为$O$为外心，所以$\Delta OBC$是以$BC$为底的等腰三角形 所以 后一半乘积为0

然后又因为$\vec{BC}\neq 0$ 所以有 $\vec{OA}+\vec{OB}+\vec{OC} = \vec{OH}$

综上$3\cdot\vec{OG} = \vec{OH}$ 欧拉线得证

重心坐标就没啥好说了 三角形顶点的均值

所以 内心期望 = 弧的中点 的 均值

注意这样算的是 内心 根据上面的外心 垂心关系，把内心坐标乘3就行了

要注意的是 弧的中点 不是靠优弧和劣弧来决定的 而是 弧外的第三个点不在的那条弧上

时间复杂度 O(点^2)

代码

卧槽 这还会有精度问题

精度问题代码

AC代码

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

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);
 
int n;
int l;
 
pair<double,double> twoT2P(int twoT){
  double v = pi*twoT/l;
  return make_pair(cos(v),sin(v));
}
int t[3010];
 
int main(){
  cin>>n>>l;
  rep(i,0,n){
    scanf("%d",t+i);
  }
  double cntX=0;
  double cntY=0;
  rep(i,0,n){
    rep(j,i+1,n){
      pair<double,double> ret = twoT2P(t[i]+t[j]);
      cntX+=(n-2*(j-i))*ret.first;
      cntY+=(n-2*(j-i))*ret.second;
    }
  }
 
  printf("%.15lf %.15lf\n",6*cntX/n/(n-1)/(n-2),6*cntY/n/(n-1)/(n-2));
  return 0;
}

原题链接

大意

n个人 有值1~n

有m条无向边

求 图中 满足 值i>值j>值k 有多少对

q次操作 每次指定一个人 使它的值+n,并求在新的图中有多少对

数据范围

1<=n<=100000, 0<=m<=100000,0<=q<=100000

4s

256MB

题解

首先 题目的数值保证了不会有相等的值出现

显然如果根据值的大小，把无向边改成有向边 多少对 = sum{每个点 出度 * 入度}

那么如何处理更新

如果裸更新 可能遇到聚点 时间复杂度可能有O(m * q)

然后 官方题解

如果我们把点 按照 总度从大到小，从左到右排列

那么每个点和它左边点相连的个数 小于等于(根号2m)

反证， 如果存在 一个和左侧连接个数大于 (根号2m)

那么 有 左侧点个数 大于 根号2m,也有 左侧点的度 > 该点的度 >= 该点于左侧点的连接数 > 根号2m

边 >= 有左侧点度的总数 (根号2m) * (根号2m) = 2m 矛盾

???? 怎么就 q 根号2m了 TODO 官方题解这里没有看懂

cf群里的证明

感谢RUSH_D_CAT 和 QAQAutoMaton大佬

以下忽略等号的描述 sqrt(m)都视作非整数[因为在意的是复杂度,是否精确讨论等号 对复杂度没有影响

提供的把点分为大点和小点

大点 度> sqrt(m)

小点 度< sqrt(m)

同上的反证法可以得到 大点的个数 < sqrt(m)

每次更新一个小点 时间复杂度 sqrt(m)

对于一个大点 总的时间复杂度 O(m+q)

因为只有第一次更新大点会达到 O(m)的复杂度

对于非第一次更新大点 最多更改的点 = 上一次更改到当前更改的点 = O(q)

所以总的时间复杂度

O(n*sqrt(m) + sqrt(m) * (m+q))

常数优秀的话能过 10**^7.5 = 31622776.60168379

注意的是 m+q 这个上界 也是难达到的? (怎么证一个更小的范围)

代码

这题难点不在代码 在证明

因为我看完题也就脑糊了这个算法估计能过，但不知道怎么证明