抽象错误集锦
本文收录自己犯过的一些离谱错误,用来引以为戒。
通用错误
变量名错误。
- (Acwing220)其一:线性筛循环较多时不要搞错下标。 正确示范:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void prime_prework(){
memset(min_prime_factor,0,sizeof min_prime_factor);
for(ll i=2;i<=inp;i++){
if(min_prime_factor[i]==0){
phi[i]=i-1;
min_prime_factor[i]=i;
primes[n]=i;
n++;
}
sum_prefix[i]=sum_prefix[i-1]+phi[i];
for(ll j=0;j<n&&primes[i]<=min_prime_factor[j]/*此处下标i,j反了*/&&i*primes[j]<=inp;j++){
phi[i*primes[j]]=phi[i]*(i%primes[j]==0?primes[j]:(primes[j]-1));
min_prime_factor[i*primes[j]]=primes[j];
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void prime_prework(){
memset(min_prime_factor,0,sizeof min_prime_factor);
for(ll i=2;i<=inp;i++){
if(min_prime_factor[i]==0){
phi[i]=i-1;
min_prime_factor[i]=i;
primes[n]=i;
n++;
}
sum_prefix[i]=sum_prefix[i-1]+phi[i];
for(ll j=0;j<n&&primes[j]<=min_prime_factor[i]&&i*primes[j]<=inp;j++){
phi[i*primes[j]]=phi[i]*(i%primes[j]==0?primes[j]:(primes[j]-1));
min_prime_factor[i*primes[j]]=primes[j];
}
}
} - (Luogu P6225)写树状数组时记得不要把
和 搞混了。虽然很离谱但是我已经连续两次把 中的 写成 了。 - (Luogu P6619)倍增的时候不要直接把算出来的
当作 。听起来很离谱,但是我确实这么干了。还有记得更新各个变量。
- (Acwing220)其一:线性筛循环较多时不要搞错下标。
(AcWing258)想得太复杂了。看完题目以为要用一大堆推理分析,调了好久都没想出来。后来发现暴力就能过。(实际上不是没注意到数据范围,而是以为这道题目时限比较松)结论就是:当一个思路不太好实现时,建议换一个思路。
(Luogu P4198)开
long double
要开全!!正确示范:1
ll cal(ll p,ll h){/**/} // <-- ll h 应为 long double h
1
ll cal(ll p,long double h){/**/}
(Luogu P4556)检查特殊下标(比如
)有没有特判(可以用 fsanitize
查查ub)。(Luogu P7453)记得取模!!!
(P2824) P2824 破防实录(其二):遇到分类讨论的时候记得询问时也要分类。(奇怪,明明写之前还记得的) 错误示范:
正确示范:1
cout << 1 + query(loc.rt, q - loc.l + 1) << endl;
1
2
3
4cout << 1 + query(loc.rt, loc.is_inc
? q - loc.l + 1
: tree[loc.rt].cnt - (q - loc.l + 1) + 1)
<< endl;(校内模拟) 浮点数运算一定要先乘再除。先除成一个极小的数下溢之后再做被除数会变成
inf
,先乘再除就没这个问题。(Luogu网校 T486366)多测慎用
memset()
,以及不需要频繁取模。正确示范:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18while(t--){
memset(s,0,sizeof s); //<-- 这一行
memset(order,0,sizeof order); //<-- 和这一行
/*
由于这两个数组是 1e7 级别的
数据保证所有测试点 n 的总和为 1e7
所以当 n 的规模远小于 1e7是
总共的测试点组数可能会来到
1e3 甚至 1e4。
而这两个语句在每个测试点都会重复memset一边 1e7 的数组
因此导致 TLE。
*/
//sth else
for(ll i=0;i<n-k+1;i++){
ans+=((i+1)*(order[i]+1))%(ll)(1e9+7); //<-- 这里的取模是多余的,因为下一行已经取过一次摸了,而且并不会爆精度。多出来的一次取模导致常数变大 TLE
ans%=(ll)1e9+7;
}
}1
2
3
4
5
6
7
8
9
10while(t--){
//sth else
s[n+1]=s[n]=0;// 最终程序最大只会访问到 n,因此只把这两个赋值就可以了。(前面的有输入)
//sth else
for(ll i=0;i<n-k+1;i++){
ans+=((i+1)*(order[i]+1))%(ll)(1e9+7); // <-- 去掉多余的取模操作
ans%=(ll)1e9+7;
}
//output...
}(Luogu P6033)这道题时间复杂度卡的很紧。有的时候构造函数可以省略。
正确示范:1
2
3
4
5
6
7
8
9
10
11
12struct node{
ull val;
ull times;
node(){
val=times=0; //<-- 此处构造函数会在声明时调用。由于数组过大(1.5e7)导致调用是会有约 50ms 的常数增加(此题时限 500ms,卡的很紧)
}
};
struct Queue{
node data[(int)1.5e7+100];
//sth
//在队列的push函数中已经有了对于node相关成员的修改。因此无需初始化。
}1
2
3
4
5
6
7
8
9struct node{
ull val;
ull times;
// <-- 删去了构造函数
};
struct Queue{
node data[(int)1.5e7+100];
//sth
}(Luogu网校 T489100)写线性筛的时候需要注意各种边界问题。(以及复制代码的时候把变量名盖全)
复制粘贴问题。
- (校内模拟)复制粘贴:其二
1
2
3
4
5
6
7
8
9
10ll l=1,r=sz;
while (l<r) {
ll mid=(l+r)>>1;
if(rotate(m, mid)==rotate(m, mid)){ // <-- 恒等
l=mid+1;
}
else {
r=mid;
}
} - (校内模拟)复制粘贴:其一
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
35template<ll T>
struct modint{
ll val;
modint(){
val=0;
}
modint(ll x){
val=x%T;
}
bool operator==(const modint<T>& b)const{
return val==b.val;
}
modint<T> operator+(const modint<T> &b)const{
return modint<T>(val+b.val);
}
modint<T> operator+=(const modint<T> &b){
val=(val+b.val)%T;
return *this;
}
modint<T> operator*(const modint<T> &b)const{
return modint<T>(val+b.val); //<-- 注意这里
}
modint<T> operator*=(const modint<T> &b){
val=(val*b.val)%T;
return *this;
}
modint<T> operator-(const modint<T> &b)const{
return modint<T>(val-b.val+((val-b.val<0)?T:0));
}
modint<T> operator-=(const modint<T> &b){
val=(val-b.val)%T;
if(val<0)val+=T;
return *this;
}
};
- (校内模拟)复制粘贴:其一
- (校内模拟)复制粘贴:其二
(CF1691F)运算符优先级,乘法比加法先:
1
2
3
4
5
6
7void dfs(ll x) {
//do sth
ans += modular<MOD>(n) * C(k, n) - totalc;
//ans += modular<MOD>(n) * (C(k, n) - totalc);
//就这个问题调了好久。
return;
}(P9149) 死循环:其一
1
2
3
4
5
6
7
8
9while (h < v.size() && i == v[h].r) {
ll t = bi.query(v[h].r) - bi.query(v[h].l - 1);
if (t > d) {
continue; //<-- 注意 h 并不会更新,导致死循环
}
ll rest_w = w - nums - t, rest_d = d - t;
ans += C(rest_d, rest_w);
h++;
}(CSP-S 2024 T2)局部变量记得初始化!!!!! 挂分写法:
正确写法:1
2
3
4void solve() {
bit b;
//do sth
}1
2
3
4
5void solve() {
bit b;
b.clear();
//do sth
}。 是因为还有一个地方写挂了。 (P3527)无限递归:其一
考虑1
2
3
4
5
6
7
8
9
10void add(ull l, ull r, ull val) {
if (r < l) {
add(1, m, val);
add(r + 1, l - 1, -val);
} else {
add(l, val);
add(r + 1, -val);
}
return;
}l==3&&r==2
的情况,add(r + 1, l - 1, -val);
递归后仍然r<l
。(P3810)使用之前记录下来的下标访问元素的时候要原数组是否更改。
解决:1
2
3
4solve(0, total - 1); // 这个函数是cdq分治,里边要重新排序,之前记录的下标会失效
for (ll i = 0; i < n; i++) {
cnt[ans[i]] += arr[i].times;
}补上提交记录或许更容易理解:不排序,排序1
2
3
4
5solve(0, total - 1);
sort(arr, arr + total, [](const e &a, const e &b) {return a.i<b.i;});// <-- 重新排个序就好了
for (ll i = 0; i < n; i++) {
cnt[ans[i]] += arr[i].times;
}(HDU1180 1010)memset 时看清楚变量类型(哎这个为什么 HDU 不报 RE 啊)。
1
2
3
4bool vis[N];
...
memset(vis, 0, sizeof(ll) * (n + 5)); // 应该是 sizeof(bool)
...(QOJ-3030)如果有下标相关的判断和取下标值的判断,要先判断下标,否则可能会 re(如果先判断下标会因为断点不会 re)。
1
2
3if (used[val[j] + min_unused] || val[j] + min_unused > n)
// 应该改成
if (val[j] + min_unused > n || used[val[j] + min_unused])STL 相关
(Luogu网校 T483205)一边 range-for 一边(用 STL)插入节点会出问题。
(Luogu网校 T483205)
std::unordered_map<__int128,__int128>
会出问题,因为__int128
没有默认的 hash 函数。(改为long long
即可)- (CF1824D)
std::vector
在push_back
或其他修改操作后其原来的迭代器会失效,引用也会失效。 这样写也不行:因为1
2
3
4
5
6
7
8
9
10
11
12struct node;
vector<node> v;
struct node{
ll data;
void f(){
//do sth with v;
v.push_back(data);
//...
}
}
//...
v[i].f();push_back
后原本这个v[i]
也失效了。
- (CF1824D)
(P2824) P2824 破防实录(其一):
erase
完std::set
后这个迭代器会失效。不能++
。 错误示范:正确示范:1
2
3
4for (auto i = beg; i != end; i++) {
rt = merge(rt, i->rt);
s.erase(i)
}似乎还有一种写法是1
2
3
4
5
6for (auto i = beg; i != end; i++) {
auto tmp = i;
tmp--;
s.erase(tmp);
rt = merge(rt, i->rt);
}s.erase(i++)
。
算法
数学
(AT_abc356_d)组合数求法。 错误示范:
槽点有点多。1
2
3
4
5
6
7
8
9
10
11ll c(ll p,ll n){
if(n==0)return 0;
ll res=1;
for(ll i=1;i<=p;i++){
res=(res*i)%Mod;
}
for(ll i=n;i>=n-p;i--){
res=(res*i)%Mod;
}
return res;
}
首先,,因此即便 , 也非零。其次,下半部分的阶乘应当时乘上乘法逆元,而不是乘上 。第三, 有 个数。正确示范: 1
2
3
4
5
6
7
8
9
10ll c(ll p,ll n){
ll res=1;
for(ll i=1;i<=p;i++){
res=(res*niyuan[i])%Mod;
}
for(ll i=n;i>n-p;i--){
res=(res*i)%Mod;
}
return res;
}离散化
(Acwing 121)离散化之后混用下标和离散化的数值
正确写法:1
2
3
4
5
6
7
8ll tx=lower_bound(x,x+rx,i+mid-1)-x,ty=lower_bound(y,y+ry,j+mid-1)-y;
if(x[tx]>i+mid||tx>=rx)tx--;
if(y[ty]>j+mid||ty>=ry)ty--;
ll ans=sum[tx][ty]-(i!=0?sum[i-1][ty]:0)-(j!=0?sum[tx][j-1]:0)+(i!=0&&j!=0?sum[i-1][j-1]:0);
if(ans>=c){
res=true;
goto out_of_loop;
}其中1
2
3
4
5
6
7
8
9ll tx=lower_bound(x,x+rx,x[i]+mid-1)-x,ty=lower_bound(y,y+ry,y[j]+mid-1)-y;
if(x[tx]>x[i]+mid-1||tx>=rx)tx--;
if(y[ty]>y[j]+mid-1||ty>=ry)ty--;
ll ans=sum[tx][ty]-(i!=0?sum[i-1][ty]:0)-(j!=0?sum[tx][j-1]:0)+(i!=0&&j!=0?sum[i-1][j-1]:0);
if(ans>=c){
res=true;
goto out_of_loop;
}i,j
是下标,x[i],y[j]
是离散化之后的数。
LCA 相关
倍增法
(Luogu P4556)还是那题,倍增法LCA记得特判第一步就移动到相同的点上的可能。
(Luogu P4556)又是那题,还是倍增法LCA,检查开的数组的大小,记住
。 欧拉序 + ST 表
(Luogu P2680)两点间 lca 是欧拉序上深度最小的节点。不是最大的(
max
打习惯的属于是)。Floyd
(Luogu网校 T491913)Floyd 算法。需要注意不能枚举通过一条边到达
的点和从 开始通过一条边可以到达的点。具体看代码。 正确写法:1
2
3
4
5
6
7
8
9
10
11
12
13
14for(ll i=0;i<m;i++){
ll s,t,v;
cin>>s>>t>>v;
G1[s].push_back({v,t});
G2[t].push_back({v,s});
}
//do sth
for(ll i=1;i<=n;i++){
for(auto s:G2[arr[i].ind]){ //<-- 这两处有误
for(auto t:G1[arr[i].ind]){ //<--
//do sth
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14for(ll i=0;i<m;i++){
ll s,t,v;
cin>>s>>t>>v;
G1[s].push_back({v,t});
G2[t].push_back({v,s});
}
//do sth
for(ll i=1;i<=n;i++){
for(ll s=1;s<=n;s++){
for(ll t=1;t<=n;t++){
//do sth
}
}
}搜索
DFS
(P4281) dfs 方法预处理 lca 的 fa 数组时记得先预处理在递归。 错误示范:
正确示范:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void dfs(ll x) {
vis[x] = true;
for (auto k : G[x]) {
if (!vis[k]) {
dfs(k);
}
else {
fa[x][0] = k;
depth[x] = depth[k] + 1;
}
}
for (ll i = 1; i < 20; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
return;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void dfs(ll x) {
vis[x] = true;
for (auto k : G[x]) {
if (vis[k]) {
fa[x][0] = k;
depth[x] = depth[k] + 1;
}
}
for (ll i = 1; i < 20; i++) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
}
for (auto k : G[x]) {
if (!vis[k]) {
dfs(k);
}
}
return;
}(P10480) 考虑这道题。一个很简单(但是错误)的想法是 dfs,返回这个节点可以到达的并且还没有访问过的节点个数。然后对于每个节点,如果下一个节点访问过就加上大小,否则加上从下一个点可以到达的没有访问过的节点个数。 一个反例就是:
从
开始 DFS。先访问 ,再访问 ,此时 可以到达 ,但是由于递归到 返回的结果是没有访问过的节点数,因此不包括 。
DP
(Luogu P4170)递归dp如果不确定调用次数记得写记忆化!!!
(CF Gym-100723H) DP 记录前驱的时候没有判断当前状态是否可行就转移并更新前驱,导致最后得到答案时爆炸了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18const auto &p = umap[(ll)(s[i + 1] - 'a')][(ll)(s[j] - 'a')][j - i]
[hs.substr(i + 1, j - i)];
if (p.second) {
// 此时 dp[i] 可能本身不可行。
// dp[i].pre = -1
dp[j].num += dp[i].num * p.second;
dp[j].pre = i;
}
...
ll cur = s.size() - 1;
while (cur) {
ll pre = dp[cur].pre;
ans.push_back(umap[(ll)(s[pre + 1] - 'a')][(ll)(s[cur] - 'a')]
[cur - pre][hs.substr(pre + 1, cur - pre)] // 这里数组只开了 100,但是那个 i 大于 100,爆炸了。
.first);
cur = pre;
// 其实如果不再那里爆炸也会之后访问到 -1 下标爆炸。
}Hash
(Luogu网校 T483205)手写邻接表+hash 忘记更新下标。 错误示范:
正确示范:1
2
3
4
5
6
7
8
9
10
11i128 query(ll i){
i128 h=((i%M)*P)%M;
ll ind=head[h];
while (ind!=-1){
if(ht[ind].num==i){
return ht[ind].val;
}
}
return 0;
}1
2
3
4
5
6
7
8
9
10
11i128 query(ll i){
i128 h=((i%M)*P)%M;
ll ind=head[h];
while (ind!=-1){
if(ht[ind].num==i){
return ht[ind].val;
}
ind=ht[ind].nxt; //<-- 这行少了
}
return 0;
}(校内模拟)字符串hash没有预处理
pow
数组(甚至已经声明过了(校内)二维 hash 写错数组
1
2
3
4
5
6
7
for(ll i=1;i<=n*2;i++){
for (ll j=1; j<=m*2; j++) {
G[i][j].a=(H[i-1][j].a*P1)+H[i][j].a;
G[i][j].b=(H[i-1][j].b*P2)+H[i][j].b; //<-- 右侧 H[i-1][j] 应为 G[i-1][j]
}
}拓扑排序
(P3065)拓扑排序是连边是通向的结点的入读加一。
1
2
3
4if (t[cur].c[to_int(c)] && c != x) {
G[to_int(x)].push_back(to_int(c));
inc_deg[to_int(x)]++; // --> 改为:inc_deg[to_int(c)]++;
}(P1073) 取出队首时使用
auto f = q.empty();
其他技巧
(P4155)断环成链后,如果需要排序,区间长度记得
。 应改为:1
2
3
4
5
6
7
8
9
10for (ll i = 0; i < n; i++) {
cin >> r[i].l >> r[i].r;
if (r[i].r < r[i].l) {
r[i].r += m;
}
r[i + n] = r[i];
r[i + n].r += m, r[i + n].l += m;
r[i].i = i;
}
sort(r, r + n, [](const range &a, const range &b) { return a.l < b.l; });1
2
3
4
5
6
7
8
9
10
11for (ll i = 0; i < n; i++) {
cin >> r[i].l >> r[i].r;
if (r[i].r < r[i].l) {
r[i].r += m;
}
r[i + n] = r[i];
r[i + n].r += m, r[i + n].l += m;
r[i].i = i;
}
sort(r, r + n * 2,
[](const range &a, const range &b) { return a.l < b.l; });数据结构
ST 表
(P2680) ST 表倍增处理的时候不要跳过头了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14for (ll i = 0; i < n; i++) {
st[i][0] = arr[i];
}
for (ll j = 1; j < LG; j++) {
for (ll i = 0; i < n; i++) {
if (i + (1ll << j) >= n) {
st[i][j] = st[i][j - 1];
}
else {
st[i][j] = min(st[i][j - 1], st[i + (1 << j)][j - 1]); // 此处应该是 st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
// 实际上 st[i][j] 表示的就是 i 到 i + (1<<j) -1 的最小值
}
}
}(AT_abc420_f) ST 表的末端点记得 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16for (ll i = 0; i < n; i++) {
st[i][0] = arr[i];
}
for (ll j = 1; j < LG; j++) {
for (ll i = 0; i < n; i++) {
if (i + (1ll << j) >= n) {
// 应该是 i + (1ll << j) -1 >= n
// 对没错,上面一份代码也是错的。
// 不知道为什么过了。
st[i][j] = st[i][j - 1];
}
else {
st[i][j] = min(st[i][j - 1], st[i + (1 << j)][j - 1]);
}
}
}BIT
(Luogu P6619)还是树状数组,写
pos-=lowbit(pos)
的时候不要把lowbit
漏掉。线段树
(Luogu P3834)可持久化权值线段树到叶子节点的时候记得把旧的数值复制进来。
(Luogu P7453)区间操作也要根据子节点更新这个节点的值。别忘了下传标记。
(Luogu P4513)线段树的
x<=mid
不要写成mid<=x
。1
2
3
4
5
6
7void modify(ll p,ll x,ll v){
//sth
if(mid<=x){ //<-- 应为 x<=mid
modify(lc(p),x,v);
}
//sth
}(P6845) 线段树下传标记的时候要合并标记而不是覆盖标记。
1
2
3
4
5
6
7
8
9void add(ll p, ll val) {
//给 p 结点对应的区间加上 val.
node &cur = t[p];
cur.maxe.val += val;
cur.mine.val += val;
cur.max_halfe_l.val -= val;
cur.max_halfe_r.val -= val;
cur.tag += val; //<--应为: cur.tag += val;
}(CF1824D) 线段树下传标记的函数调用不要放在新建子节点的
if
的括号里。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void spread(ll p) {
ll mid = (arr[p].l + arr[p].r) >> 1;
if (arr[p].lc == -1) {
arr[p].lc = arr.size();
arr.push_back(node(arr[p].l, mid));
//if (arr[p].t != -INF) set(arr[p].lc, arr[p].t);//而不是这里
}
if (arr[p].t != -INF) set(arr[p].lc, arr[p].t);//这里
if (arr[p].rc == -1) {
arr[p].rc = arr.size();
arr.push_back(node(mid + 1, arr[p].r));
//if (arr[p].t != -INF) set(arr[p].rc, arr[p].t); //而不是这里
}
if (arr[p].t != -INF) set(arr[p].rc, arr[p].t); //这里
arr[p].t = -INF;
}(航电多校)区间查询写
if(pos<=mid){...}else{...}
1
2
3
4
5
6
7
8
9
10
11
12
13
14ll query(ll p, ll l, ll r) const {
if (l <= t[p].l && t[p].r <= r) {
return t[p].maxn;
}
ll mid = (t[p].l + t[p].r) / 2;
ll ret = 0;
if (l <= mid) {
ret = max(ret, query(lc(p), l, r));
}
else { // 应为 if (mid + 1 <= r)
ret = max(ret, query(rc(p), l, r));
}
return ret;
}(P3384)线段树区间加忘记乘上区间长度了。
线段树二分
(Gym-100803G) 线段树二分到一个节点前一定要先下传延迟标记。
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
29ll query_right() {
// 第一个有括号。
ll p = 1;
while (nd[p].l != nd[p].r) {
// 此处应当添加 spread(p);
if (nd[lc(p)].has_right) {
p = lc(p);
}
else {
p = rc(p);
}
}
return nd[p].l;
}
ll query_left() {
// 找到第一个合法的左括号。
// 要看后缀 min 是不是小于 2.
ll p = 1;
while (nd[p].l != nd[p].r) {
// 这里也应当添加 spread(p);
if (nd[lc(p)].has_left && nd[rc(p)].minn >= 2) {
p = lc(p);
}
else {
p = rc(p);
}
}
return nd[p].l + 1;
}平衡树
(P3369)查询排名的时候把要查询的值减去左节点的大小了和当前节点的数的个数了。
1
2
3
4
5
6
7
8
9
10
11ll query_rank(ll p, ll val) const {
if (p == -1) {
return 0;
}
if (val <= t[p].val) {
return query_rank(t[p].lc, val);
}
else {
return node_size(t[p].lc) + t[p].cnt + query_rank(t[p].rc, val - node_size(t[p].lc) t[p].cnt);//<-- 应为 node_size(t[p].lc) + t[p].cnt + query_rank(t[p].rc, val)
}
}(P3369)节点
cnt
到时不删除节点,导致查询前驱的时候返回一个 cnt
为的数。 (P3369)写删除节点时左旋然后朝着右结点递归删除(实际上左节点才是原来的节点)。
(P3369)
erase
递减之后没有update_size
。Trie
(CF888G)tire数搞清楚位运算。
1
2
3
4
5
6
7
8
9
10for (int i = p; i >= 0; i--) {
int b = val & (1 << i);//应该改为:int b = (v >> i) & 1;
//这样并没有清楚后面的位,因此不能仅靠 1 来判断。
if (b == 1) {
//do stj
}
else {
//do sth
}
}(CF888G)不要随便霍霍内存。
01-trie 的一个卡内存的技巧:将原数组排序,然后在每个结点记录最左边的数的下标和最右边的数的下标。01-trie 感觉有点像一颗特化的值域线段树(或者维护序列的平衡树),每个结点实际上代表了一个区间。1
2
3
4
5
6
7const int N = 2e5 + 5;
struct node {
//...
vector<int> val;
//...
};
node t[33 * N];并查集
(AT_abc280_f) 带权并查集:合并时根节点分不清,没有计算出正确的权值(注释里是正确的写法)
1
2
3
4
5
6
7
8
9
10
11
12
13void m(ll x, ll y, ll dis) {
ll rx = fi(x), ry = fi(y);
if (rx != ry) {
//ll r_dis=-f[x].dis+dis+f[y].dis;
//注意这行,计算出正确的dis值
f[rx].fa = ry;
//f[rx].dis = r_dis;
f[rx].dis=dis;
f[rx].inf |= f[ry].inf;
//f[ry].inf|=f[rx].inf;
return;
}
}
图论
- 树剖混用 dfs 序和原下标。
- 树剖求 LCA 时先跳深度较大的(应该是链的头深度较大的)