열대야 주간 (JUNGOL 8536)

https://jungol.co.kr/problem/8536

---

아이디어

구간에 대한 세그트리를 다음과같이 만들어줍시다. 이때 M 이상의 수는 1로, M미만의 수는 0으로 표현해줍시다.

1. 구간의 시작점

2. 구간의 끝점

3. 왼쪽 에서 연속으로 1이 최대 몇개가 있는지

4. 오른쪽에서 연속으로 1이 최대 몇개가 있는지

5. 그 구간에서 그냥 최대 1이 몇개가 연속해있는지

이 구조체 세그먼트 트리를 만들어주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

struct Range{
    ll s,e,Left,Right,mx;
};
Range operator+(Range A,Range B)
{
    Range res;
    res.s=A.s;
    res.e=B.e;
    res.Left=(A.Left==(A.e-A.s+1)?A.Left+B.Left:A.Left); //A의 왼쪽 범위가 전체 범위이면
    res.Right=(B.Right==(B.e-B.s+1)?B.Right+A.Right:B.Right);
    res.mx=max({A.mx,B.mx,A.Right+B.Left});
    return res;
}

Range tree[4040404]={0};
void update(ll s,ll e,ll node,ll idx,ll num)
{
    if (idx<s || e<idx) return;
    if (s==e)
    {
        tree[node].s=s;
        tree[node].e=e;
        tree[node].Left=tree[node].Right=tree[node].mx=num;
        return;
    }

    ll mid=(s+e)/2;
    update(s,mid,node*2,idx,num);
    update(mid+1,e,node*2+1,idx,num);
    tree[node]=tree[node*2]+tree[node*2+1];
}
Range query(ll s,ll e,ll node,ll l,ll r)
{
    if (e<l || r<s) return {0,0,0};
    if (l<=s && e<=r) return tree[node];
    ll mid=(s+e)/2;
    return query(s,mid,node*2,l,r)+query(mid+1,e,node*2+1,l,r);
}

ll arr[1010101]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,Q,M,type,a,b;

    cin>>N;
    for (i=1;i<=N;i++) cin>>arr[i];

    cin>>Q>>M;
    for (i=1;i<=N;i++) update(1,N,1,i,arr[i]>=M);

    for (i=0;i<Q;i++)
    {
        cin>>type>>a>>b;

        if (type==1)
        {
            ll res=query(1,N,1,a,b).mx;
            if (res==0) res=-1;
            
            cout<<res<<"\n";
        }
        else
        {
            update(1,N,1,a,b>=M);
        }
    }
}