一些8pts的小小注意事项
查看原帖
一些8pts的小小注意事项
369291
winter2020楼主2022/11/24 13:09

应该没人像我一样犯这么的的离谱错误

  • pushdown 的 tr[u] 的懒标记,一定要记得清掉

  • 如果你是像我一样,在第一种操作时,是先query再update,那注意query的结果=0,不应该update

  • 在query的时候:

int query(int u, int x) {
   if (tr[u].tmax < x) return 0;
   if (tr[u].l == tr[u].r) {
       if (tr[u].lmax == 1) return tr[u].l;
       else return 0;
   }
   pushdown(u);
   int _x = query(u << 1, x);
   if (_x) return _x;
   if (tr[u << 1].rmax + tr[u << 1 | 1].lmax >= x)
       return tr[u << 1].r - tr[u << 1].rmax + 1;
    // 这里的判断不能是 if(tr[u << 1].rmax) return...
    // 因为tr[u].tmax是由右边的区间来管
   else return query(u << 1 | 1, x);
}
2022/11/24 13:09
加载中...