수열과 쿼리 13 [BOJ 13925]

Lazy propagation을 여러 가지 쿼리를 통해 전파하는 경우 어떤 것을 먼저 전파할지 결정하는 것이 매우 중요하다. 하지만 이 문제에서는 3개의 쿼리가 어떤 하나의 쿼리의 일부가 된다. 이를 인지하면 구현량도 많이 줄일 수 있어 실수도 덜 나오고 빠르게 풀 수 있다. 그리고 이 문제가 D5가 박혀있지만 플래 기여가 상당히 많고, 이제 플래로 내려올 때가 된 것 같다. D5 티어에 쫄지 말고 아이디어를 잡기 위해 노력해보자.

 

문제 요약

길이 10만 이하의 수열 A에 대해 다음 4가지 쿼리를 수행한다.

1 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]+v)%MOD 적용

2 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]*v)%MOD 적용

3 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=v 적용

4 x y : 구간 [x, y]의 구간합%MOD 출력

 

사용 알고리즘

레이지 세그

 

문제 풀이

1번, 2번, 3번 쿼리에 대한 레이지를 잘 관리해준다면 4번 쿼리는 쉽다. 그럼 이제 각 쿼리를 어떤 연산으로 통일할 수 있을까? 이에 대한 정답은, 각 값에 <Ax+B>연산을 수행한다는 것이다. 1번 쿼리는 <1x+v>, 2번 쿼리는 <vx+0>, 3번 쿼리는 <0x+v>를 수행한다. 따라서 이 업데이트를 진행하는 함수 하나만 만들어주면 된다. 이는 각 노드마다 2개의 레이지를 관리해줌으로 해결할 수 있다. 이 2개의 레이지는 각각 A, B를 뜻한다. 여기서 조심할 점은 push할 때 C(Ax+B)+D를 하면 ACx+BC+D가 된다는 이야기이다. 즉, 상수항을 처리할 때 상수항이 중첩되는 것을 고려해주어야 한다. 그 외에 부분은 일반 레이지 세그와 동일하게 구현해주면 된다. 말로 구구절절히 설명하는 것보다는 아래 코드를 보는게 훨씬 도움이 될 것 같다.

시간복잡도는 lazy propagation만 진행하므로 O(NlogN)이며, 상수가 조금 크다고 생각할 수 있지만 보통 lazy propagation이 정해인 문제들은 시간제한이 넉넉하게 설정되어있으므로 TLE를 걱정하지 않아도 된다.

 

코드

#include<bits/stdc++.h>
#define SIZE 100010
#define MOD 1000000007
using namespace std;
typedef long long ll;
struct node
{
    ll sum,lz1,lz2;
};
ll N,M,A[SIZE];
node seg[SIZE<<2];
void init(ll l,ll r,ll idx)
{
    seg[idx].lz1=0,seg[idx].lz2=1;
    if(l==r){
        seg[idx].sum=A[l];
        return;
    }
    ll mid=l+r>>1;
    init(l,mid,idx<<1);
    init(mid+1,r,(idx<<1)+1);
    seg[idx].sum=(seg[idx<<1].sum+seg[(idx<<1)+1].sum)%MOD;
}
void push(ll l,ll r,ll idx)
{
    if(seg[idx].lz1==0&&seg[idx].lz2==1)return;
    seg[idx].sum=(seg[idx].sum*seg[idx].lz2+seg[idx].lz1*(r-l+1))%MOD;
    if(l^r){
        for(int i=idx<<1;i<=(idx<<1)+1;i++){
            seg[i].lz2=(seg[i].lz2*seg[idx].lz2)%MOD;
            seg[i].lz1=(seg[i].lz1*seg[idx].lz2+seg[idx].lz1)%MOD;
        }
    }
    seg[idx].lz1=0,seg[idx].lz2=1;
}
void upd(ll l,ll r,ll idx,ll s,ll e,ll v1,ll v2)
{
    push(l,r,idx);
    if(l>e||r<s)return;
    if(s<=l&&r<=e){
        seg[idx].lz1=v1;
        seg[idx].lz2=v2;
        push(l,r,idx);
        return;
    }
    ll mid=l+r>>1;
    upd(l,mid,idx<<1,s,e,v1,v2);
    upd(mid+1,r,(idx<<1)+1,s,e,v1,v2);
    seg[idx].sum=(seg[idx<<1].sum+seg[(idx<<1)+1].sum)%MOD;
}
ll query(ll l,ll r,ll idx,ll s,ll e)
{
    push(l,r,idx);
    if(l>e||r<s)return 0;
    if(s<=l&&r<=e)return seg[idx].sum;
    ll mid=l+r>>1;
    return (query(l,mid,idx<<1,s,e)+query(mid+1,r,(idx<<1)+1,s,e))%MOD;
}
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>N;
    for(int i=1;i<=N;i++)cin>>A[i];
    init(1,N,1);
    for(cin>>M;M--;){
        ll t,x,y,v;
        cin>>t>>x>>y;
        if(t<=3){
            cin>>v;
            if(t==1)upd(1,N,1,x,y,v,1);
            if(t==2)upd(1,N,1,x,y,0,v);
            if(t==3)upd(1,N,1,x,y,v,0);
        }
        else printf("%lld\n",query(1,N,1,x,y));
    }
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장