BOJ 13925 - 수열과 쿼리 13

문제 태그 : https://www.acmicpc.net/problem/13925

문제 소개

1. x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y)
2. x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y)
3. x y v: Ai = v를 수행한다. (x ≤ i ≤ y)
4. x y: (ΣAi) % MOD를 출력한다. (x ≤ i ≤ y)
   
   의 4가지 쿼리를 처리해야하는 문제이다.

문제 풀이

일단 이런식으로 처리하는데에 있어 기본적으로 lazy segment tree를 생각할 수 있다. 하지만 여기서 lazy하게 처리하는 과정에서 걸리는 부분이 있다. 기존의 lazy 방식은 최대한 미루고 나중에 처리해 주는 방식이다. 따라서 한 노드에 처리해 주어야 할 양이 쌓이기도 한다.

이 부분에서 문제가 발생한다. 기존의 1번 노드만 존재하는 방식은 쌓여도 다 합쳐서 한 번에 처리가 가능하다. 하지만 지금 이 문제처럼 여러가지 쿼리가 존재하고, 이를 처리하는 순서가 중요한 경우 하나하나 처리하다보면 시간이 당연히 터지게 된다. 따라서 우리는 1번 쿼리만 있을 때 처럼 쌓인 1,2,3번 쿼리를 한번에 처리할 방법을 찾아야 한다.

다음과 같은 식을 생각해보자. ((((a)+4)*7)+3) 이 값을 계산하면 결국 7a+31이 된다. 이 과정에서 중간의 분배법칙을 잘 생각해 본다면 +4는 결국 뒤에 쓰여지는 +28과 같은 효과를 낸다는 것을 알 수 있다. 우리는 이런 방식을 통해 1번쿼리와 2번 쿼리를 합칠 수 있게 된다. 그 식은 아래와 같다.

(mul a plus b)쿼리와 (mul c plu d) 쿼리가 합쳐지면 (mul a*c plus b*c+d) 쿼리가 생성된다. 이때 1번 쿼리는 (1,v) 2번 쿼리는 (v,0)으로 표기할 수 있으며 좀 만 더 생각해 본다면 3번 쿼리는 (0,v)로 표기할 수 있다는 사실을 알 수 있다. 어떠한 쿼리가 들어오던지 간에 똑같은 형태의 쿼리로 O(1)만에 합쳐지기 때문에 기존의 lazy propagation with segment tree로 쿼리당 O(logN)만에 처리해 줄 수 있을 것이다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
 
ll mod=1000000007;
struct node{
    ll val,lazm,lazp;
};
 
ll arr[1010101];
node tree[5050505];
 
void laz(ll s,ll e,ll nod){
    if(tree[nod].lazm!=1){
        tree[nod].val=(tree[nod].val*tree[nod].lazm+mod)%mod;
        if(s!=e){
            tree[nod*2].lazm=(tree[nod*2].lazm*tree[nod].lazm+mod)%mod;
            tree[nod*2].lazp=(tree[nod*2].lazp*tree[nod].lazm+mod)%mod;
            tree[nod*2+1].lazm=(tree[nod*2+1].lazm*tree[nod].lazm+mod)%mod;
            tree[nod*2+1].lazp=(tree[nod*2+1].lazp*tree[nod].lazm+mod)%mod;
        }
        tree[nod].lazm=1;
    }
    if(tree[nod].lazp!=0){
        tree[nod].val=(tree[nod].val+(e-s+1)*tree[nod].lazp+mod)%mod;
        if(s!=e){
            tree[nod*2].lazp=(tree[nod*2].lazp+tree[nod].lazp+mod)%mod;
            tree[nod*2+1].lazp=(tree[nod*2+1].lazp+tree[nod].lazp+mod)%mod;
        }
        tree[nod].lazp=0;
    }
}
 
ll q1(ll l,ll r,ll v,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(r<s||e<l) return tree[nod].val;
    if(l<=s&&e<=r){
        tree[nod].lazp=v;
        laz(s,e,nod);
        return tree[nod].val;
    }
    return tree[nod].val=(q1(l,r,v,s,(s+e)/2,nod*2)+q1(l,r,v,(s+e)/2+1,e,nod*2+1)+mod)%mod;
}
 
ll q2(ll l,ll r,ll v,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(r<s||e<l) return tree[nod].val;
    if(l<=s&&e<=r){
        tree[nod].lazm=v;
        laz(s,e,nod);
        return tree[nod].val;
    }
    return tree[nod].val=(q2(l,r,v,s,(s+e)/2,nod*2)+q2(l,r,v,(s+e)/2+1,e,nod*2+1)+mod)%mod;
}
 
ll q3(ll l,ll r,ll v,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(r<s||e<l) return tree[nod].val;
    if(l<=s&&e<=r){
        tree[nod].lazm=0;
        tree[nod].lazp=v;
        laz(s,e,nod);
        return tree[nod].val;
    }
    return tree[nod].val=(q3(l,r,v,s,(s+e)/2,nod*2)+q3(l,r,v,(s+e)/2+1,e,nod*2+1)+mod)%mod;
}
 
ll q4(ll l,ll r,ll s,ll e,ll nod){
    laz(s,e,nod);
    if(r<s||e<l) return 0;
    if(l<=s&&e<=r) return tree[nod].val;
    return (q4(l,r,s,(s+e)/2,nod*2)+q4(l,r,(s+e)/2+1,e,nod*2+1)+mod)%mod;
}
 
 
int main(){
    ll i,j,k,l,m,n,a,b,c,d;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld",&m);
        q3(i,i,m,1,n,1);
    }
    scanf("%lld",&m);
    while(m--){
        scanf("%lld %lld %lld",&a,&b,&c);
        if(a==1){
            scanf("%lld",&d);
            q1(b,c,d,1,n,1);
        }
        if(a==2){
            scanf("%lld",&d);
            q2(b,c,d,1,n,1);
        }
        if(a==3){
            scanf("%lld",&d);
            q3(b,c,d,1,n,1);
        }
        if(a==4){
            printf("%lld\n",(q4(b,c,1,n,1)+mod)%mod);
        }
    }
}