Codeforces 671E Organizing a Race(욕심, 세그먼트 트리)

제목 링크
https://codeforces.com/contest/671/problem/E
문제풀이
전혀 할 줄 몰라요...기본적으로lk의 코드ruogu를 베낀 문제풀이입니다.https://www.luogu.com.cn/blog/ruogu-pupil/cf671esoj809-tan-xin-er-fen-tan-suo-shen-xian#Orz lk & ruogu 주: 본문에서\(a, b, m\)는 각각 원제에서\(g, w, k\)를 어떻게 분배할 것인지를 먼저 고려한다는 것을 나타낸다. 분명한 욕심은 왼쪽에서 오른쪽으로 힘을 내야 할 때 더해서 왼쪽에서 오른쪽으로 합법적임을 보증하고 마지막에 남은 돈을 모두 오른쪽 단점으로 더해서 가능한 한 오른쪽에서 왼쪽으로 합법적임을 보증하는 것이다.(f i=f i=f {i-1}+a {i-1}-b {ii i=f i=f b {i-1}-b {i-1}, g i i=g i=g i=g i i i i i ii i i i i b i b\),\(j\gt i\),\(g j\) 는\(1\) 를 줄이고 변경된\(g\) 를\(h\) 수조로 설정하면 뒤에서\(l\) 를 열거합니다.단조로운 창고를 유지하는 김에\(l\)에서 오른쪽으로 갈 수 있는 최대\(r\)는 단조로운 창고에서 직접 2분의 1로 구할 수 있음을 고려하여\(R\)로 기록합니다.우리는 단조로운 창고를 유지하는 동시에 세그먼트 트리 구간에\(h\)를 추가하면\(r\)에\(h r=g r+m\)가 있습니다.\(g r-m\le min^{r-1} {i=l}h i\)를 충족시키고\(l\le i\le R\)의 최대\(r\)를 조회하려면 접두사와 접두사를 사용하는 것이 묘하다.\(r\)가 다른 값을 얻었을 때\(g r\)의 증가량이 항상\(m\)로 늘어나는 것을 보장한다. 직접 라인 트리의 2분을 고려하고 라인 트리의 노드에 도착했을 때만약\(R>mid\) 왼쪽 반쪽의\(h\)의 최소값이 오른쪽\(g\)의 최소값\(-k\)보다 크면 오른쪽으로 돌아가고 오른쪽에 반드시 답이 있을 것이다(단,\(R\)의 왼쪽에 있을 수는 없다).이는 왼쪽 끝에 있는\(h i\geg i-k\), 오른쪽 끝에 있는\(h i\le g i-k\le g r-k\)가 모두 충족되기 때문입니다.발견된 점이\(R\)의 오른쪽에 있는 경우 해결되지 않은 상태로 돌아가면 복잡성에 영향을 주지 않고 한 번만 발생합니다.오른쪽에 풀이 없거나\(R\le mid\)가 반환되면 현재 최소\(h\)가 왼쪽\(g\)의 최소값\(-m\)보다 크면 왼쪽으로 반환되고 그렇지 않으면 풀이 없음으로 돌아갑니다.한 번에 왼쪽으로 돌아가는 것은 해를 찾을 수 있기 때문에 복잡도가 정확하다.(자세히 설명하지 못할 수도 있습니다...코드 참조) 시간 복잡도\(O(n\log n)\).
코드

#include
#define llong long long
#define mkpr make_pair
#define riterator reverse_iterator
using namespace std;

inline int read()
{
    int x=0,f=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
    for(; isdigit(ch);ch=getchar()) {x = x*10+ch-'0';}
    return x*f;
}

const int N = 1e6;
const llong INF = 1e16;
llong a[N+3],b[N+3],f[N+3],g[N+3];
int stk[N+3];
int n,tp; llong m; int ans;

struct SgTNode
{
    llong h,g,tag;
    SgTNode() {h = INF,g = -INF;}
} sgt[(N<<2)+3];
void pushdown(int u)
{
    if(!sgt[u].tag) return; llong tag = sgt[u].tag;
    sgt[u<<1].h += tag,sgt[u<<1].tag += tag;
    sgt[u<<1|1].h += tag,sgt[u<<1|1].tag += tag;
    sgt[u].tag = 0ll;
}
void updateg(int u,int le,int ri,int pos)
{
    if(le==ri) {sgt[u].g = sgt[u].h = g[pos]; return;}
    int mid = (le+ri)>>1; pushdown(u);
    if(pos<=mid) {updateg(u<<1,le,mid,pos);}
    else {updateg(u<<1|1,mid+1,ri,pos);}
    sgt[u].g = min(sgt[u<<1].g,sgt[u<<1|1].g); sgt[u].h = min(sgt[u<<1].h,sgt[u<<1|1].h);
}
void addh(int u,int le,int ri,int lb,int rb,llong x)
{
    if(le>=lb && ri<=rb) {sgt[u].h += x,sgt[u].tag += x; return;}
    int mid = (le+ri)>>1; pushdown(u);
    if(lb<=mid) {addh(u<<1,le,mid,lb,rb,x);}
    if(rb>mid) {addh(u<<1|1,mid+1,ri,lb,rb,x);}
    sgt[u].h = min(sgt[u<<1].h,sgt[u<<1|1].h);
}
int query(int u,int le,int ri,int rb,llong x)
{
    if(le>rb) {return -1;}
    if(le==ri) {return le;}
    int mid = (le+ri)>>1; pushdown(u);
    llong lv = min(x,sgt[u<<1].h);
    if(rb>mid && lv>=sgt[u<<1|1].g-m)
    {
        int ret = query(u<<1|1,mid+1,ri,rb,lv);
        if(ret!=-1) return ret;
    }
    if(sgt[u<<1].g-m<=x) return query(u<<1,le,mid,rb,x);
    return -1;
}

int main()
{
    scanf("%d%I64d",&n,&m);
    for(int i=1; i=1; i--)
    {
        updateg(1,1,n,i);
        while(tp>0 && f[stk[tp]]>=f[i])
        {
            if(tp>1)
            {
                addh(1,1,n,stk[tp-1]-1,n,f[stk[tp]]-f[stk[tp-1]]);
            }
            tp--;
        }
        tp++; stk[tp] = i;
        if(tp>1)
        {
            addh(1,1,n,stk[tp-1]-1,n,f[stk[tp-1]]-f[stk[tp]]);
        }
        int left = 0,right = tp;
        while(left>1;
            if(f[i]-f[stk[mid]]>m) {left = mid;}
            else {right = mid-1;}
        }
        int r = stk[left]-1;
        int ret = query(1,1,n,r,INF);
        ans = max(ans,ret-i+1);
    }
    printf("%d
",ans);
    return 0;
}