我用了一种线段树合并的写法,如下
inline void merge(int &rt,int pre){
if (!rt||!pre) return void(rt|=pre);
merge(lc[rt],lc[pre]),merge(rc[rt],rc[pre]);
cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
}
上述代码会WA 2个点
但是改成下面这个代码
inline void merge(int &rt,int pre,int l,int r){
if (!rt||!pre) return void(rt|=pre);
if (l==r) return void(cnt[rt]+=cnt[pre]);
int mid=(l+r)>>1;
merge(lc[rt],lc[pre],l,mid),merge(rc[rt],rc[pre],mid+1,r);
cnt[rt]=cnt[lc[rt]]+cnt[rc[rt]];
}
就直接AC了
题目要求了hi互不相同,我想问题应该出在这里
我在darkbzoj上下了一组数据测试,的确出现了hi相同的情况
烦请管理员核实并修改