我是sb...倍增写错了
by ustze @ 2019-03-31 16:34:50
我超,我也是样例过了,全 WA。
我~~也~~是sb,也是倍增写错了。
具体来说就是,建完 Kxxxx 树,有 $2n-1$ 个结点。求 `fa[u][i]` 的时候 $u$ 的范围却只取到了 $1\sim n$。
by zhy137036 @ 2022-07-24 12:34:25
《K****** 树要 $2n-1$》
by I_am_Accepted @ 2022-07-30 17:41:48
~~我倍增也写错了~~
具体而言,因为是从 `0` 开始标号的所以根的父亲不能设为 `0` 要设为 `-1` 之类的……
附一份 `Testdata`(
```cpp
#include<bits/stdc++.h>
using namespace std;
const int n=7,m=8,q=50;
int id[n+2];
bool u[n+2][n+2];
int main()
{
srand(chrono::steady_clock().now().time_since_epoch().count());
printf("%d %d %d\n",n,m,q);
for(int i=0;i<n;++i)id[i]=i;
for(int i=0;i<n;++i)swap(id[i],id[rand()%(i+1)]);
for(int i=1,x,y;i<n;++i)printf("%d %d\n",x=id[i],y=id[rand()%i]),u[x][y]=u[y][x]=1;
for(int i=n,x,y;i<=m;++i)
{
do x=rand()%n,y=rand()%n;while(x==y || u[id[x]][id[y]]);
printf("%d %d\n",id[x],id[y]),u[id[x]][id[y]]=u[id[y]][id[x]]=1;
}
for(int i=1,x,y,l,r;i<=q;++i)
{
do x=rand()%n,y=rand()%n;while(x==y);
l=rand()%(x+1),r=rand()%(n-y)+y,printf("%d %d %d %d\n",x,y,l,r);
}
}
```
by 18Michael @ 2022-08-19 21:02:47
我也是全WA
后来发现是《SB主席树》
```cpp
int modify(int p, int l, int r, int x){
int q = ++ tot;
tr[q] = tr[p], v(q) ++;
if(l == r) return q;
int mid = l + r >> 1;
if(x <= mid) l(q) = modify(l(p), l, mid, x);
else r(q) = modify(r(p), l, mid, x);
return q;
}
```
by liqize15235204345 @ 2022-08-31 01:17:07
同上,全WA来看讨论区发现倍增要$2n-1$,改一发直接A(乐)
by The_Last_Candy @ 2023-07-02 14:01:43