尝试 Hack

可能能 Hack 第三篇题解?

作者的 update 是这么写的

void update(int rt,int l,int r,int ql,int qr,int i){
        if(ql<=l&&r<=qr){
            //没有直接更新 
            if(!id[rt]) return id[rt]=i,void();
            int mid=(l+r)>>1;//更新的时候交换，可能被淘汰的线段在左右区间会是最优线段
            if(f[i](mid)-f[id[rt]](mid)>eps) swap(i,id[rt]);
            //等于时让编号小的去更新 
            if(f[i](l)-f[id[rt]](l)>eps||(f[i](l)==f[id[rt]](l)&&i<id[rt])) update(lson,ql,qr,i);
            if(f[i](r)-f[id[rt]](r)>eps||(f[i](r)==f[id[rt]](r)&&i<id[rt])) update(rson,ql,qr,i);
            return;
        }
        int mid=(l+r)>>1;
        if(ql<=mid) update(lson,ql,qr,i);
        if(mid<qr) update(rson,ql,qr,i);
    }

发现他在新线段完全优于旧线段的情况下好像会遍历整棵子树 那么我只要造组数据使得当前线段完全优于前一个线段就可以卡掉