查询确实有问题啊,
你有没有考虑过,如果更改了`tree[rt].gcd`的值,那么下次查询 `if(l<=tree[rt].l&&r>=tree[rt].r)
return tree[rt].gcd;`
会错误?
by Reaepita @ 2018-10-28 23:48:31
这道题用递推就行了呀,为什么要线段树呢??qwq
by Sshenyyyu @ 2018-10-28 23:49:20
改成这个
```
if(r<=mid) return find(rt<<1,l,r);
if(l>mid) return find(rt<<1|1,l,r);
else return gcd(find(rt<<1,l,r),find(rt<<1|1,l,r));
```
by Reaepita @ 2018-10-29 00:04:01
```
int r1=0,r2=0;
if(l<=mid) r1=find(rt<<1,l,r);
if(r>mid) r2= find(rt<<1|1,l,r);
//这里要查的区间不变
if(!r1) tree[rt].gcd=tree[rt<<1|1].gcd;
if(!r2) tree[rt].gcd=tree[rt<<1].gcd;
//不存在!r1&&!r2
//r=0表示没有if过
if(r1&&r2) tree[rt].gcd=gcd(r1,r2);
//自以为是的路径压缩
return tree[rt].gcd;
}
```
这一坨都删掉
by Reaepita @ 2018-10-29 00:04:37
@[Harry_bh](/space/show?uid=19951) 谢谢dalao,祝您AK(手动滑稽)
by lsy263 @ 2018-10-29 06:23:45
@[lsy263](/space/show?uid=72611)
$ST$表大法好~~(逃~~
by ___new2zy___ @ 2018-10-29 07:09:33
@[___new2zy___](/space/show?uid=60359) __不会__
by lsy263 @ 2018-10-29 23:15:42
啊啦啊啦就剩第10点T掉了呢,90分了
by lsy263 @ 2018-10-29 23:18:43
但是就是不想放弃cin,,懒得敲scanf
by lsy263 @ 2018-10-29 23:20:25
诶呀最后还是用了scanf...话说竟然不能混用cin,scanf
by lsy263 @ 2018-10-29 23:38:40