请问 wqs 二分这里为啥要使得选择的区间个数最多啊?
查看原帖
请问 wqs 二分这里为啥要使得选择的区间个数最多啊?
487752
OrezTsim楼主2023/9/18 21:09

这是我的 check 函数

pii ck(int mid,int sm=0,int tot=0,int all=0){
    for(int i=1;i<=ct;++i)t[i]={0,0,0,0};
    ct=rot=0,upd(rot,-inf,inf,0),sm=a[1];
    vector<int>tmp;vector<Point>nxt;
    for(int i=1;i<=n;++i,sm+=a[i]){
        auto it=query(rot,-inf,inf,-inf,sm-mid);
        if(it.fi)tot+=it.fi,all+=it.fi*(sm-mid)-it.se;
        else tmp.push_back(i);
        upd(rot,-inf,inf,sm);
    }
    if(tmp.empty())return {tot,all};
    for(auto pos:tmp){
        int lef=calc(1,pos,1)-st[1][0][pos];
        int rig=calc(pos,n,0)-st[0][0][pos];
        int curr=lef+rig+a[pos];if(curr>=mid)continue;
        nxt.push_back({lef,rig,pos}),all+=curr-mid;
    }
    if(nxt.empty())return {tot,all};
    int len=nxt.size();tot+=len;
    for(int i=1;i<len;++i){
        auto [lef,rig,pos]=nxt[i-1];
        auto [_lef,_rig,_pos]=nxt[i];
        int lst_cont=lef+rig+a[pos]+_lef+_rig+a[_pos]-2*mid;
        int cur_cont=lef+st[0][0][_pos]-st[0][0][pos-1]+_rig-mid;
        if(cur_cont>lst_cont)--tot,all+=cur_cont-lst_cont;
      // 这里有问题,改成 cur_cont>=lst_cont 就挂了
    }
    return {tot,all};
}

就,我往 tot 加的时候就要放宽判定条件,往 tot 减的时候加强判定条件

为啥啊???看不懂捏

2023/9/18 21:09
加载中...