문제 태그 : https://www.acmicpc.net/problem/13925
문제 소개
- x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y)
- x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y)
- x y v: Ai = v를 수행한다. (x ≤ i ≤ y)
- 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)만에 처리해 줄 수 있을 것이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
#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);
}
}
}
|
cs |
'코딩 > 백준 문제 풀이' 카테고리의 다른 글
BOJ 13263 - 나무 자르기 (0) | 2020.03.28 |
---|---|
BOJ 17940 - 지하철 (0) | 2020.03.26 |
BOJ 7791 - KBTU Party (1) | 2020.03.13 |
BOJ 10903 - Wall construction (0) | 2020.03.11 |
BOJ 2162 - 선분 그룹 (2) | 2020.03.08 |