Educational Codeforces Round 72

發表於 更新於 分類於 ， 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 高性能?