[BOJ][백준]lazy propagation-17474번 수열과 쿼리 26

https://www.acmicpc.net/problem/17474

17474번: 수열과 쿼리 26

문제

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 

• 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = min(Ai, X) 를 적용한다. 
• 2 L R: max(AL, AL+1, ..., AR)을 출력한다.
• 3 L R: AL + AL+1 + ... + AR을 출력한다.

입력

첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 A1, A2, ..., AN이 주어진다. (0 ≤ Ai < 231)

셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 1,000,000)

넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ L ≤ R ≤ N, 0 ≤ X < 231) 2번과 3번 쿼리는 한 번 이상 주어진다.

출력

2, 3번 쿼리의 결과를 한 줄에 하나씩 출력한다.

---

 

수쿼26번 문제입니다. 처음 문제가나오고 5시간 넘게 삽질하다가 결국은 못 풀고 포기했던 문제인데,

다른 분의 풀이를 보고 힌트를 얻어 풀어낼 수 있었습니다.

출처:https://m.blog.naver.com/PostView.nhn?blogId=kyo20111&logNo=221667191729&proxyReferer=https%3A%2F%2Fwww.google.com%2F

Segment tree beats 간단하게 구현하기 (백준 17474)

풀이는 자세하게 풀어 써 주셨으니 참고하시길 바랍니다. (저 블로그의 풀이도 lazy propagation의 기초가 있으신 분들을 위한 풀이입니다. 꽤 입문장벽이 있으니 lazy propagation을 모르시는분들은 개념정리를 한 후에 보시는 것이 좋습니다.)

찾아보니 segment tree를 응용한 lazy propagation유형을 응용한 segment tree beats 라는 알고리즘이 따로 있나 봅니다. 제가 잠시 휴식기일때 유명세를 탔던 것 같은데, 아무튼 처음보는 알고리즘이라 개념정리가 필요했던 문제였습니다.

처음 접근은 max,min,sum을 각각 담당하는 lazy segment tree를 작성하고, 1번쿼리가 들어올때 구간의 최솟값과 최댓값을 고려해서 max와min과sum segment tree를 각각 구간별로 업데이트시키고... 그냥 간단히 말해 시간제한이4초니까 lazy segment로 어떻게는 커팅해서 비벼보자..! 라는 마인드였는데, 어림도없는 풀이였던것 같네요.

이 문제 해결법의 주요 포인트는 2개가 있는데, 첫째는 최댓값과 2번째 최댓값을 segment tree로 관리하는 것이고, 둘째는 sum의 업데이트를 max_cnt(해당 구간에서의 최댓값의 갯수)를 이용해 한번의 수식으로 갱신시키는겁니다. 자세한 풀이는 위의 블로그를 참고해 주시면 됩니다. 사실 말이쉽지 이걸 번뜩 생각해내기란 상당히 어렵다고 봅니다. 그래서 다양한 문제를 폭넓게 많이 풀면 좋다는 것인데, segment tree beats의 탈을 쓰고 응용된 문제가 나온다면 과연 내가 깔끔하게 잘 짤수 있을까? 라는 물음엔 쉽게 대답은 못하겠습니다. 하지만 이런 문제의 경험이 누적되면 반드시 좋은 성과를 낼..수...있겠죠? 사실 아직은 잘 모르겠습니다.

 

 

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=987654321;
int N,Q;

struct NODE
{
    int max1,max2,cnt_max;
    ll sum;
};

struct SEG_TREE
{
    int n;
    vector<NODE>tree;
    SEG_TREE(){;}
    SEG_TREE(vector<int>v)
    {
        n=v.size();
        tree.resize(n*4);
        init(v,0,n-1,1);
    }
    NODE add(NODE a,NODE b)
    {
        if(a.max1==b.max1) return {a.max1,max(a.max2,b.max2),a.cnt_max+b.cnt_max,a.sum+b.sum};
        else if(a.max1>b.max1) return {a.max1,max(a.max2,b.max1),a.cnt_max,a.sum+b.sum};
        else if(b.max1>a.max1) return {b.max1,max(a.max1,b.max2),b.cnt_max,a.sum+b.sum};
    }
    NODE init(vector<int>&v,int left,int right,int node)
    {
        if(left==right)return tree[node]={v[left],-INF,1,v[left]};
        int mid=(left+right)/2;
        return tree[node]=add(init(v,left,mid,node*2),init(v,mid+1,right,node*2+1));
    }
    void lazy_propagation(int left,int right,int node)
    {
        if(left!=right)
            for(int idx=node*2;idx<=node*2+1;idx++)
                if(tree[node].max1<tree[idx].max1)
                {
                    tree[idx].sum-=(ll)tree[idx].cnt_max*(tree[idx].max1-tree[node].max1);
                    tree[idx].max1=tree[node].max1;
                }
    }
    void update(int left,int right,int k){return update(left,right,k,0,n-1,1);}
    void update(const int left,const int right,const int k,int nodeLeft,int nodeRight,int node)
    {
        //cout<<nodeLeft<<" "<<nodeRight<<endl;
        if(nodeRight<left||right<nodeLeft||tree[node].max1<=k) return ;
        lazy_propagation(nodeLeft,nodeRight,node);
        if(left<=nodeLeft&&nodeRight<=right&&tree[node].max2<k)
        {
            tree[node].sum-=(ll)tree[node].cnt_max*(tree[node].max1-k);
            tree[node].max1=k;
            lazy_propagation(nodeLeft,nodeRight,node);
            return ;
        }
        int mid=(nodeLeft+nodeRight)/2;
        update(left,right,k,nodeLeft,mid,node*2);
        update(left,right,k,mid+1,nodeRight,node*2+1);
        tree[node]=add(tree[node*2],tree[node*2+1]);
    }

    int query_max(int left,int right){return query_max(left,right,0,n-1,1);}
    int query_max(const int left,const int right,int nodeLeft,int nodeRight,int node)
    {
        lazy_propagation(nodeLeft,nodeRight,node);
        if(nodeRight<left||right<nodeLeft)return -INF;
        if(left<=nodeLeft&&nodeRight<=right)return tree[node].max1;
        int mid=(nodeLeft+nodeRight)/2;
        return max(query_max(left,right,nodeLeft,mid,node*2),query_max(left,right,mid+1,nodeRight,node*2+1));
    }

    ll query_sum(int left,int right){return query_sum(left,right,0,n-1,1);}
    ll query_sum(const int left,const int right,int nodeLeft,int nodeRight,int node)
    {
        lazy_propagation(nodeLeft,nodeRight,node);
        if(nodeRight<left||right<nodeLeft)return 0;
        if(left<=nodeLeft&&nodeRight<=right)return tree[node].sum;
        int mid=(nodeLeft+nodeRight)/2;
        return query_sum(left,right,nodeLeft,mid,node*2)+query_sum(left,right,mid+1,nodeRight,node*2+1);
    }
};



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N;
    vector<int>v(N);
    for(auto&i:v)cin>>i;
    SEG_TREE seg(v);
    cin>>Q;
    while(Q--)
    {
        int type,left,right,x;
        cin>>type;
        if(type==1)
        {
            cin>>left>>right>>x;
            seg.update(left-1,right-1,x);
        }
        else if(type==2)
        {
            cin>>left>>right;
            cout<<seg.query_max(left-1,right-1)<<"\n";
        }
        else if(type==3)
        {
            cin>>left>>right;
            cout<<seg.query_sum(left-1,right-1)<<"\n";
        }
    }
}

 

solved.ac 기준 다이아2 수준이라는 태그를 단 문제입니다. 이태껏 푼 문제중 가장 어려운 문제였는데, 100% 내가 생각해 낸 풀이로 성공을 하진 못하였지만 새로운 알고리즘을 배웠다는 것 에 의의를 두었습니다. 그나저나 수쿼 문제들은 하루에 한두개만 풀어도 머리가 깨질듯 아픕니다. 그런데 그만큼 풀면 또 자신감 회복도 많이 되는것같아서, 가끔 매운맛이 필요할때 찾아서 풉니다.