我一开始认为,节点对应在线段树上的点维护的是它到重链链底的信息,这样的话,矩阵应该是从链底乘到链顶的。而又由于链顶的编号大,所以我线段树里面的顺序是反过来的,我觉得这很符合逻辑。但是实际证明,以下代码是可以通过的,但是用注释里面的实现却只有 30pts,求说明或者指出我思路可能的错处。
void build(int u,int l,int r){
if(l==r){
t[u]=g[ti[l]];
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
t[u]=t[u<<1]*t[u<<1|1];
// t[u]=t[u<<1|1]*t[u<<1];
return ;
}
void updata(int u,int l,int r,int k,Matrix x){
if(l==r){
t[u]=x;
return ;
}
int mid=(l+r)>>1;
if(k<=mid) updata(u<<1,l,mid,k,x);
else updata(u<<1|1,mid+1,r,k,x);
t[u]=t[u<<1]*t[u<<1|1];
// t[u]=t[u<<1|1]*t[u<<1];
return ;
}
Matrix query(int u,int l,int r,int L,int R){
if(L<=l&&r<=R) return t[u];
int mid=(l+r)>>1;
if(R<=mid) return query(u<<1,l,mid,L,R);
if(L>mid) return query(u<<1|1,mid+1,r,L,R);
return query(u<<1,l,mid,L,R)*query(u<<1|1,mid+1,r,L,R);
// return query(u<<1|1,mid+1,r,L,R)*query(u<<1,l,mid,L,R);
}