YeXiaoRain Blog

發表於 更新於 分類於 ， Disqus： 文章字數： 620 所需閱讀時間 ≈ 2 分鐘
E (bitDP)

原题链接

大意

前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;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
C (math + inclusion-exclusion),D(平面几何)

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;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 567 所需閱讀時間 ≈ 2 分鐘
C (graph)

原题链接

大意

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 这个上界 也是难达到的? (怎么证一个更小的范围)

代码

这题难点不在代码 在证明

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

發表於 更新於 分類於 ， Disqus： 文章字數： 867 所需閱讀時間 ≈ 3 分鐘
E (状压DP + 常数优化)

原题链接

2400 评分

大意

n*m的数字矩阵

你可以对任意个列，进行列的循环移动任意次 (cyclical shifts)

问 能得到的((每行最大值之和)的最大值)是多少

数据范围

1<=n<=12, 1<=m<=2000

0<=矩阵中的数字<=100'000

3s

256MB

题解

其实还有题目E1,也就是n最大只有4

显然 我们按照每列最大元素 进行排序，只需要取最大的min(n,m)列，再旋转即可

那么问题来了,问题简化为 最大 12*12的矩阵

如果有一个12*12要怎么做呢

无脑枚举可以做E1,因为只有 4^4,而E2有 12^12

方法是 dp, 状态dp[i][state]

其中 state是 选取的行的状态二进制编码 O(2^n),

整个dp表示 前i列,行的选取状态为state时的最大值

那么答案为 dp[m-1][(1<<n)-1]

状态转移

dp[i][stateX] = max(dp[i-1][stateY]+ sum{矩阵第i列,stateX-stateY选中的行的元素的值 } )

意义就是 前i列 选取行的状态是stateX的话

那么 它的最大期望 是 选取的一部分(stateX-stateY)来自第i列，其余(stateY)来自前i-1列

那么状态转移，对当前列 循环n次移动，每次计算 所有状态, 的所有状态来源

一次状态转移时间复杂度为 O(n(shift移动当前列) * (1<<n)(所有状态) * n(每个状态的来源) )

总的一次状态转移为 O( min(n,m) * n * (1<<n) * n )

12^3*2^12 = 7077888 有注意常数的必要

代码

Accepted Code

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;
 
typedef long long ll;
#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);
 
const int MAXN = 12;
const int MAXM = 2000;
int a[MAXN + 10][MAXM + 10], n, m;
int f[2][1<<MAXN]; // 滚动数组 到某列时 当前答案
int g[1<<MAXN]; // 每轮列旋转1单位时的答案
map<int,int>v2mi;
int lowbit(int x) {
  return x & -x;
}
 
pair<int,int>arr[MAXM + 10];
int tmp[MAXN+10][MAXM+10];
 
void solve() {
  scanf("%d%d", &n, &m);
  int tot = (1<<n);
  rep(i,0,tot){
    f[1][i] = 0;
  }
  rep(i,0,m){
    arr[i] = {0,i};
  }
  rep(i,0,n){
    rep(j,0,m){
      scanf("%d", &a[i][j]);
      arr[j].first = max(arr[j].first, a[i][j]);
    }
  }
  sort(arr, arr + m);
  rep(j,m-min(m,n),m){
    rep(i,0,n){
      tmp[i][m-1-j] = a[i][arr[j].second];
    }
  }
  rep(i,0,n){
    rep(j,0,min(m,n)){
      a[i][j] = tmp[i][j];
    }
  }
  m = min(m,n);
 
  // f[0->i列][选的行的state] = 最大期望
  // 没有旋转的情况下
  // f[0->i列][选的行的state] = max(f[0->i-1列][选的行的stateA]+第i列选行stateB) 其中 stateA & stateB =0 , stateA|stateB = (1<<min(m,n))-1
  rep(i,0,m){
    int itr = i%2;
    rep(j,0,tot){
      f[itr][j] = 0;
    }
    // 旋转n次
    rep(j,0,n){
      rep(k,0,tot){
        g[k] = f[itr^1][k];
      }
      rep(k,0,tot){
        int p = (tot - 1)^k; // p & k =0, p|k = (tot-1)
        while( p ) {
          int x = lowbit(p);
          g[k|x] = max(g[k|x], g[k] + a[v2mi[x]][i]); // 每一圈的最值
          p -= x;
        }
      }
      // 旋转1单位
      int tmp = a[0][i];
      rep(k,0,n-1){
        a[k][i] = a[k + 1][i];
      }
      a[n - 1][i] = tmp;
 
      // 对每个state统计最大值
      rep(j,0,tot){
        f[itr][j] = max(f[itr][j], g[j]);
      }
    }
  }
  printf("%d\n", f[(m-1)%2][tot - 1]);
}
 
int main() {
  rep(i,0,MAXN){
    v2mi[1<<i] = i;
  }
  int t;
  scanf("%d", &t);
  while( t-- ){
    solve();
  }
}

本题另外一个点

max(每一行取最大值的和) = max(每一行任意取一个值的和)

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

原题链接

大意

n个数 a[1->n]

m 个询问

询问类型1: 改动 指定下标i的值为x

询问类型2: 求下标a[l->r] 区间上 是否存在两个 数 ,使得 十进制表示的数 在数位上 有同时不为0的,如果有求 和最小的两个数，否则输出-1

例如 10010 和 23 在第2位 一个是1,一个是2不同时为0,他们的和 就正常加法10010+23=10033

例如 10101 和 1010 ，就不满足要找的数

求的是，满足的数的最小和

注:原题没有这么直接，这是一眼看出的原体的本体

数据范围

0<a[i]<=1'000'000'000

0<=n,m<=200'000

题解

一眼题解就是

按十进制分割成 10个线段树，第i个线段树上只留 在十进制第i位不为0的

线段树修改和查询 也就 线段树日常操作

第一份代码 WA2了,问题出在 ++soo.begin() 写成soo.begin()++了,用的下标-1记录个数有点问题改成0x3f3f3f3f

第二份代码 MLE5，问题在不需要维护所有，只需要维护最小两个数

第三份代码 TLE5

第四份代码 依然TLE5， 相对于第三份代码的改动

  1. 我把pair<int,int>等 换成了数组，感觉这样也许更快,也许不
  2. 很重要的一个改动sort()调用换成冒泡,因为才4个，然后我本地生成随机数测试，就初始化线段树的时间，明显从2秒多变为1秒上下

1762ms AC代码 我对初始化进行优化 把一个一个insert改成递归build，初始化时间变到了0.1s左右然后ac

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
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
189
190
191
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#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);
 
// 没有进位,其余是0
 
// 按十进制 线段树 +multiset
 
struct SEGT{
  int cnt;
  int vs[2];
}segt[12][800010];
#define UNSETINF -1
int a[200010];
int n,q;
 
// template<typename... Args>
// void ptf(const char* fmt, Args... args ){
//   return ;
//   printf(fmt,args...);
// }
 
void mergeS(int *v1,int *v2,int *outv){
  unsigned int sa[] = {
    (unsigned int)v1[0],
    (unsigned int)v1[1],
    (unsigned int)v2[0],
    (unsigned int)v2[1]
  };
  rep(i,0,2){
    rep(j,i+1,4){
      if(sa[j] < sa[i]){
        swap(sa[i],sa[j]);
      }
    }
  }
  // sort(sa,sa+4);
  outv[0] = sa[0];
  outv[1] = sa[1];
}
 
void insert(int off,int o,int l,int r,int idx,int v){
  segt[off][o].cnt++;
  if(l == r){
    segt[off][o].vs[0] = v;
    return ;
  }
  int mid = (l+r)/2;
  if(idx <= mid){
    insert(off,o<<1,l,mid,idx,v);
  }else{
    insert(off,o<<1 | 1,mid+1,r,idx,v);
  }
  mergeS(segt[off][o<<1].vs,segt[off][o<<1|1].vs,segt[off][o].vs);
}
static int ten[]={1,10,100,1'000,10'000,100'000,1'000'000,10'000'000,100'000'000,1'000'000'000};
 
void build(int off,int o,int l,int r){
  if(l == r){
    if((a[l] / ten[off])%10 != 0){
      segt[off][o].vs[0] = a[l];
      segt[off][o].cnt++;
    }
    return ;
  }
  int mid = (l+r)/2;
  build(off,o<<1,l,mid);
  build(off,o<<1|1,mid+1,r);
  mergeS(segt[off][o<<1].vs,segt[off][o<<1|1].vs,segt[off][o].vs);
  segt[off][o].cnt = segt[off][o<<1].cnt + segt[off][o<<1|1].cnt;
}
 
void del(int off,int o,int l,int r,int idx,int v){
  // ptf("del _%d_ o[%d] [%d -> %d] , [%d] = %d\n",off,o,l,r,idx,v);
  segt[off][o].cnt--;
  if(l == r){
    segt[off][o].vs[0] = UNSETINF;
    return ;
  }
  int mid = (l+r)/2;
  if(idx <= mid){
    del(off,o<<1,l,mid,idx,v);
  }else{
    del(off,o<<1 | 1,mid+1,r,idx,v);
  }
  mergeS(segt[off][o<<1].vs,segt[off][o<<1|1].vs,segt[off][o].vs);
}
 
void change(int idx,int v){
  int oldv = a[idx];
  if(oldv == v)return;
  rep(j,0,10){
    if(oldv%10 != 0){
      del(j,1,0,n-1,idx,a[idx]);
    }
    oldv/=10;
  }
  a[idx] = v;
  rep(j,0,10){
    if(v%10 != 0){
      insert(j,1,0,n-1,idx,a[idx]);
    }
    v/=10;
  }
}
 
void qtree(int off,int o,int l,int r,int ql,int qr,int *ret){
  // ptf("qtree  _%d_ o[%d] [%d -> %d] , [%d -> %d] \n",off,o,l,r,ql,qr);
  if(segt[off][o].cnt == 0){
    ret[0] = UNSETINF;
    ret[1] = UNSETINF;
    // ptf("qtree  _%d_ o[%d] [%d -> %d] , [%d -> %d]",off,o,l,r,ql,qr);
    // ptf("\t 1pret [%d %d]\n",ret[0],ret[1]);
    return ;
  }
  if(l == ql && r == qr){
    ret[0] = segt[off][o].vs[0];
    ret[1] = segt[off][o].vs[1];
    // ptf("qtree  _%d_ o[%d] [%d -> %d] , [%d -> %d]",off,o,l,r,ql,qr);
    // ptf("\t 2pret [%d %d]\n",ret[0],ret[1]);
    return ;
  }
  int mid = (l+r)/2;
  if(qr <= mid){
    qtree(off,o<<1,l,mid,ql,qr,ret);
    return ;
  }else if(ql > mid){
    qtree(off,o<<1 | 1,mid+1,r,ql,qr,ret);
    return ;
  }
  int retl[2];
  qtree(off,o<<1    ,l    ,mid,ql   ,mid,retl);
  int retr[2];
  qtree(off,o<<1 | 1,mid+1,r  ,mid+1,qr,retr);
  mergeS(retl,retr,ret);
}
 
void query(int l,int r){
  int ans = -1;
  rep(j,0,10){
    int ret[2];
    qtree(j,1,0,n-1,l,r,ret);
    if(ret[1] == -1){
      continue;
    }
    if(ans == -1 || ans > ret[0]+ret[1]){
      ans = ret[0]+ret[1];
    }
  }
  printf("%d\n",ans);
}
 
void init(){
  rep(i,0,11){
    rep(j,0,800001){
      segt[i][j].vs[0] = UNSETINF;
      segt[i][j].vs[1] = UNSETINF;
    }
  }
}
 
int main(){
  init();
  scanf("%d %d",&n,&q);
  rep(i,0,n){
    scanf("%d",a+i);
  }
  rep(off,0,10){
    build(off,1,0,n-1);
  }
  rep(i,0,q){
    int op;
    scanf("%d",&op);
    if(op == 1){
      int idx,x;
      scanf("%d %d",&idx,&x);
      change(idx-1,x);
    }else{
      int l,r;
      scanf("%d %d",&l,&r);
      query(l-1,r-1);
    }
  }
  return 0;
}

后记

后续优化

  1. 把 冒泡改成了if
  2. 去掉了计数 和cnt =0 判断 (因为考虑到更多的情况来说 不为0 吗?)

时间来到了1372 ms, 有400ms左右的优化效果 但是RUSH_D_CAT的代码的代码只要900+ms,

那么感觉 可能的影响

  1. 是函数传参个数,涉及到 汇编指令个数?
  2. 我看他的分段处理 是每层 都处理，而我的是 在最外层 for 0->9,所以 可能的是连续内存访问带来的cache 高性能?
0%