(현재는 어느정도 내용이 작성된 상태이다. 아래는 글이 거의 안 써졌을 당시의 글이다)
뭘 기대하고 들어왔는가? 2번째 포스팅을 올린지 얼마 안 지났는데 그 모든 글을 쓸 수 있을리가 없다. 그러나 조만간 공부해서 전부 작성할 예정이다.
그냥 조금 써보자면, 퍼시스턴트 레이지 세그?라는 것에 대해 다룰 것이다. 아마 두개를 합친거겠지? 레이지는 내가 그냥 짤줄 알고 퍼시스턴트 세그는 이론상으로 짤 수 있지만 300줄정도 소요될 것이기 때문에 퍼시스턴트세그도 배워서 간결한 구현을 소개할 것이다. 그 다음으론 2D 다이나믹 세그...? 뭔가 이것도 비슷한 쿼리를 처리할 수 있어보이는데 직접 배워봐야 뭘하는건지 감을 잡을 것 같다. 머징은 머징 세그비츠는 최근에 재밌는 문제를 배웠는데 그걸 통해 직관을 얻은 상태라서 이번에 제대로 파볼 생각이다. wavelet tree...?는 뭔진 모르겠는데 공부해봐야겠다.
------------------------------------------------------------------------------------------------------------------------------------------------------------
이제 때가 되었다.
1. 퍼시스턴트 레이지 세그
음...이건 그냥 pst에도 레이지를 적용 가능하다는 뜻인데 굉-장히 그냥 그렇다고 받아들이면 충분한 내용이다. 이걸 구현하는데에 어떠한 문제도 없을 것이다. 나는 정작 pst를 까먹어서 대충 구현을 참고해서 구현법을 다시 익혔다. 대충 백준에 태그 두개 합쳐져있는걸 고르면 이 아이디어를 쓰는 문제가 아닐까?
아무래도 여기에서 끝내면 조금 재미없는 것 같아서, 실제로 문제를 가져와봤다. 10641번: The J-th Number (acmicpc.net)
10641번: The J-th Number
You are given N empty arrays, t1,…,tn. At first, you execute M queries as follows. add a value v to array ti (a ≤ i ≤ b) Next, you process Q following output queries. output the j-th number of the sequence sorted all values in ti (x ≤ i ≤ y)
www.acmicpc.net
해당 문제를 간략히 요약하자면, n개의 빈 배열에 구간적으로 원소들을 삽입할 때, 특정 구간의 배열들에 대해 k번째로 작은 원소를 구하는 쿼리를 처리하는 것이다. 이러한 것은 2차원 격자판에서 각 원소들을 종류별로 순서대로 구간 쿼리를 처리하는 과정을 pst로 저장하고 나서, 몇 개의 인접한 열에 쿼리를 여러번 날리는 것으로 처리할 수 있다. 이 경우, 우리는 어떤 직사각형의 원소의 개수를 구할 수 있는데 이때 특정한 원소까지 어떤 배열이 가지고 있는 원소의 개수가 k를 넘는지, 혹은 그렇지 않은지를 조사하여 이분탐색을 진행할 수 있기 때문에, 대충 로그제곱에 해결할 수 있게 된다. 다만, N이 굉장히 크기 때문에 아마도 dynamic persistent segment tree with lazy propagation을 구현해야 할 것이다. 아니 근데 생각해보니 어차피 pst 자체가 다이나믹해서 별 상관 없을지도
음...위의 문장을 쓴 지 대충 12시간정도 지났다. 그동안 이발을 했고, 삼겹살을 먹었고(맛있었다.), 드라이브를 갔고, 테트리스를 약간 했고, 그 외의 대부분의 시간동안 위 문제의 풀이를 디버깅하는데에 소모했다. 생각보다 pst의 상수가 굉장히 크기 때문에, 단순하게 로그제곱을 짜기에는 굉장히 위험하다.
특히, 메모리가 복병이다. 512MB가 한도인데, 만약 로그제곱 풀이를 짜면 메모리도 로그제곱으로 치솟기 때문에 끝장이 난다. 이를 해결하기 위해선 답을 말하는 쿼리를 한번 처리한 직후에, 트리 전체를 초기 상태, 즉 갱신 연산이 끝난 직후의 상태로 바꾸어주어야 한다. 이를 위해서는, query 함수가 진행되며 propagation이 진행되는 정점들을 잘 골라서, 미리 특정한 배열에 해당 정점과 원래의 자식들을 저장한다. 어차피 query를 진행하며 어떤 정점의 정보가 달라질 수 있는 여부는 레이지를 이미 뿌렸는지, 혹은 그렇지 않은지와 해당 정점의 자식들의 인덱스뿐이기 때문이다. 따라서 그러한 정보들을 저장해서 한번의 query 연산이 끝날때마다 그 연산 자체를 롤백해주면, 구현에 따라 다르겠지만, 나의 경우에는 굉장히 아슬아슬하게 메모리가 통과했다. 사실 내가 굉장히 아슬아슬하게 통과했는데, 하필이면 "기존의 정점들의 모든 정보"를 기억해두는 배열을 만들면 메모리초과가 나서 이렇게 동적으로 정점들의 정보를 저장해서 이것이 많아야 로그제곱정도의 정보를 기억하도록 해야만 했다. 자세한 것은 구현을 참조하면 알 것이다. 주석은 귀찮아서 안 지우려 했는데 생각보다 과도하게 많아서 다 지웠다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct Node{
ll ind,le,ri,flag,st;
bool hasflag;
Node(ll a,ll b,ll c,ll d,ll e,bool f){
ind=a; le=b; ri=c; flag=d; st=e; hasflag=f;
}
Node(){
}
};
ll siz,t,qwer;
vector<ll> flag;
vector<bool> hasflag;
vector<bool> chk;
ll newlazykid(ll node,ll delta,ll L,ll R);
ll NODES=0;
vector<int> le,ri,ple,pri;
vector<ll> st,u;
vector<Node> hold;
void push_bac(Node node)
{
hold[t]=node;
t++;
}
void propagate(ll node,ll l,ll r) {
ll p=node;
if (hasflag[node]) {
u.push_back(node);
ple.push_back(le[node]);
pri.push_back(ri[node]);
if (l != r) {
le[node] = newlazykid(le[node], flag[node], l, l+r>>1);
ri[node] = newlazykid(ri[node], flag[node], (l+r>>1)+1, r);
}
hasflag[node] = false;
}
}
ll newlazykid(ll node,ll delta,ll l,ll r) {
ll p = ++NODES;
le[p] = le[node];
ri[p] = ri[node];
flag[p] = flag[node];
hasflag[p] = true;
flag[p] += delta;
st[p] = st[node] + (r - l + 1) * delta;
return p;
}
ll newparent(ll x,ll y)
{
NODES++;
le[NODES]=x;
ri[NODES]=y;
st[NODES]=st[x]+st[y];
return NODES;
}
ll update(ll s, ll e, ll x, ll p, ll l, ll r) {
if (e < l || r < s) return p;
if (s <= l && r <= e) return newlazykid(p, x, l, r);
propagate(p, l, r);
return newparent(update(s, e, x, le[p], l, (l+r>>1)),
update(s, e, x, ri[p], (l+r>>1) + 1, r));
}
ll query(ll s,ll e,ll p,ll l,ll r) {
if (e < l || r < s) return 0;
if (s <= l && r <= e) return st[p];
propagate(p, l, r);
return query(s, e, le[p], l, (l+r>>1)) + query(s, e, ri[p], (l+r>>1) + 1, r);
}
ll n,i,m,x,y,z,e,q,l,r,mi,root[110000],j,asdf[110000],k,ee,s;
pair<ll,pair<ll,ll>> p[110000];
int main()
{
siz=19000000;
le.resize(siz);
ri.resize(siz);
st.resize(siz);
flag.resize(siz);
hasflag.resize(siz);
scanf("%lld %lld %lld",&n,&m,&q);
srand(time(NULL));
for(i=1;i<=m;i++)
{
scanf("%lld %lld %lld",&x,&y,&z);
p[i]={z,{x,y}};
}
sort(p+1,p+m+1);
for(i=1;i<=m;i++)
{
asdf[i]=p[i].first;
root[i]=update(p[i].second.first,p[i].second.second,1,root[i-1],1,n);
t=0;
u.clear();
ple.clear();
pri.clear();
}
x=NODES;
qwer=1;
for(ee=0;ee<q;ee++)
{
scanf("%lld %lld %lld",&s,&e,&k);
t=0;
l=1; r=m;
while(l+1<r)
{
mi=l+r>>1;
if(query(s,e,root[mi],1,n)<k)
{
l=mi+1;
}
else
r=mi;
NODES=x;
for(i=0;i<u.size();i++)
{hasflag[u[i]]=true;
le[u[i]]=ple[i];
ri[u[i]]=pri[i];
}
u.clear();
ple.clear();
pri.clear();
}
for(j=-2+l;j<=2+r;j++)
{
if(j<=0)
continue;
if(query(s,e,root[j],1,n)>=k)
{
printf("%lld\n",asdf[j]);
break;
}
NODES=x;
for(i=0;i<u.size();i++)
{hasflag[u[i]]=true;
le[u[i]]=ple[i];
ri[u[i]]=pri[i];
}
u.clear();
ple.clear();
pri.clear();
}
NODES=x;
for(i=0;i<u.size();i++)
{hasflag[u[i]]=true;
le[u[i]]=ple[i];
ri[u[i]]=pri[i];
}
u.clear();
ple.clear();
pri.clear();
}
}
2. 2D 다이나믹 세그
2차원 세그라는 것은 무엇을 의미할까? 간단히 말하자면, 세그 노드에 세그를 또 한번 박는 것이다. 즉, 이 세그를 통해 2차원 격자판을 표현 가능하게 되며, 특정한 직사각형 구간의 합 연산을 로그제곱에 처리할 수 있게 된다. 갱신의 경우에는, 특정한 한 점의 값을 갱신하는 쿼리를 처리할 수 있을 것이다. 만약 어떤 점이 들어오면, 해당 점을 포함하는 세그먼트 노드는 로그개이며, 각 세그먼트 노드당 로그개의 실제 노드가 존재하기 때문에 로그제곱정도에 갱신을 할 수 있게 된다. 이제 여기에서 각 노드들을 필요할 때에만 할당하는 것이 2D "다이나믹" 세그인데, 공간복잡도나 시간복잡도는 대략적으로 nlog^2n정도의 스케일이 된다고 생각하면 된다.
8876번: 바자와 샤자
두 사람 바자(Bazza)와 샤자(Shazza)가 다음 게임을 하고 있다. 게임판은 셀로 이루어진 그리드로 되어 있고, R 개의 행이 차례로 번호가 0, …, R - 1 로 매겨져 있고 C 개의 열이 차례로 번호가 0, …, C
www.acmicpc.net
해당 문제는 2D 다이나믹 세그의 예제로 자주 나온다. 다만 내 생각에 이 문제가 그렇게 좋진 않은 것 같은데...왜냐하면 일반적인 2D 다이나믹 세그를 짜서는 안된다고 알고 있기 때문이다. 일단 메모리만 보아도 왜 그것이 애매한지 알 수 있을 것이다. 실제로 만점을 받기 위해서는 마치 레이지를 다루듯이 필요한 경우에만 갱신의 영향을 아래쪽으로 전파...?하는 그런 아이디어가 필요한 것으로 알고 있다. 정확히는 나도 짜봐야 해서 잘 모르겠다. 근데 대충 뭔말인진 알 것 같다. 지금 블로그를 쓰고 있지만 궁금해서 바로 짜러가보겠다.
Solution - Game (IOI 2013) · USACO Guide
Solution - Game (IOI 2013)
A free collection of curated, high-quality competitive programming resources to take you from USACO Bronze to USACO Platinum and beyond. Written by top USACO Finalists, these tutorials will guide you through your competitive programming journey.
usaco.guide
일단 이 사이트에서 풀이를 굉-장히 잘 설명해둔 것 같다.
오 방금 대충 예제 맞는거 보고 냈는데 맞음ㄷㄷ 코드는 다음과 같이 굉장히 복잡한 구조체를 구현하면 된다. 음...솔직히 이걸 외워야 하나...? 외워두면 분명히 쓸모는 있을 것이라 생각한다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll gcd(ll x,ll y)
{
if(x>y)
x^=y^=x^=y;
if(x==0)
return y;
return gcd(y%x,x);
}
ll n,m;
struct Node{
Node *l,*r;
ll y,siz,x,v;
pair<ll,ll> loc;
Node()
{
l=r=NULL;
v=0;
siz=0;
x=0;
y=0;
loc={0,0};
}
ll getvalue(ll s,ll e)
{
if(s<=x&&x<=e)
return y;
return 0;
}
void show()
{
//printf("!@#$:%lld,%lld,%lld\n",x,y,v);
}
};
struct Segtree{
Node *root;
Segtree()
{
root=new Node();
}
void update(Node *node,ll s,ll e,ll x,ll y,pair<ll,ll> loc)
{
//printf("?");
if(node->siz==0)
{
node->siz++;
node->y=y;
node->x=x;
node->v=y;
node->loc=loc;
//printf("on%lld,%lld:",s,e);
node->show();
return;
}
ll m=s+e>>1;
if(node->l==NULL)
node->l=new Node();
if(node->r==NULL)
node->r=new Node();
if(node->loc==loc)
{
node->y=y;
}
else
{
if(x<=m)
{
if(node->l==NULL)
{
node->l=new Node();
}
update(node->l,s,m,x,y,loc);
}
else
{
if(node->r==NULL)
{
node->r=new Node();
}
update(node->r,m+1,e,x,y,loc);
}
}
node->v=gcd(gcd(node->l->v,node->r->v),node->y);
}
ll query(Node *node,ll s,ll e,ll l,ll r)
{
if(e<l||s>r)
return 0;
if(l<=s&&e<=r)
{
//printf("%lld,%lld:%lld\n",s,e,node->v);
return node->v;}
ll x=0;
if(node->l!=NULL)
x=gcd(x,query(node->l,s,s+e>>1,l,r));
if(node->r!=NULL)
x=gcd(x,query(node->r,(s+e>>1)+1,e,l,r));
x=gcd(x,node->getvalue(l,r));
return x;
}
};
struct MetaNode{
MetaNode *l,*r;
Segtree *seg;
MetaNode(){
l=r=NULL;
seg=new Segtree();
//seg=new Segtree();
}
void upd(ll x,ll y,pair<ll,ll> loc)
{
//printf("@");
seg->update(seg->root,ll(1),n,x,y,loc);
}
ll query(ll x,ll y)
{
return seg->query(seg->root,ll(1),n,x,y);
}
ll getgcd(ll x,ll y)
{
return query(x,y);
}
};
void x_update(MetaNode *node,ll s,ll e,ll x,ll y,ll z)
{
//printf("asdf%lld %lld\n",s,e);
node->upd(y,z,{x,y});
//printf("!\n");
if(s==e)
return;
ll m=s+e>>1;
if(x<=m)
{
if(node->l==NULL)
{
node->l=new MetaNode();
}
x_update(node->l,s,m,x,y,z);
}
else
{
if(node->r==NULL)
{
node->r=new MetaNode();
}
x_update(node->r,m+1,e,x,y,z);
}
}
ll x_query(MetaNode *node,ll s,ll e,ll l,ll r,ll x,ll y)
{
if(node==NULL)
return 0;
if(e<l||s>r)
return 0;
if(l<=s&&e<=r)
{
//printf("!%lld,%lld:%lld\n",s,e,node->getgcd(x,y));
return node->getgcd(x,y);}
ll m=s+e>>1;
return gcd(x_query(node->l,s,m,l,r,x,y),x_query(node->r,m+1,e,l,r,x,y));
}
MetaNode *root;
ll e,t,x,y,z,i,j,w;
int main()
{
scanf("%lld %lld %lld",&n,&m,&e);
root=new MetaNode();
for(ll ee=0;ee<e;ee++)
{
scanf("%lld",&t);
if(t==1)
{
scanf("%lld %lld %lld",&x,&y,&z);
x++; y++;
x_update(root,1,m,y,x,z);
}
else
{
scanf("%lld %lld %lld %lld",&x,&y,&z,&w);
x++; y++; z++; w++;
printf("%lld\n",x_query(root,1,m,y,w,x,z));
}
}
}
3. 세그트리 머징
이 주제를 본 사람들은 대체로 이런 반응을 보일 것이다: "세그트리 머징이 머징"
중요한 것은, 세그트리 머징과 머지소트트리는 다른 개념이라는 것이다! 사실 이 글을 쓰고 있는 지금도 세그트리 머징이 뭔지 모른다. 이제 공부하러 갈 것이다.
이해하고 왔...다? 아마.
8211번: Tree Rotations (acmicpc.net)
8211번: Tree Rotations
In the first line of the standard input there is a single integer n (2 ≤ n ≤ 200,000) that denotes the number of leaves in Byteasar's tree. Next, the description of the tree follows. The tree is defined recursively: if there is a leaf labelled with p (
www.acmicpc.net
다음 문제가 좋은 motivation이 될 것이다. 대충 문제를 요약하자면, 이진 트리가 주어지고, 왼쪽 서브트리와 오른쪽 서브트리를 바꾸는 연산을 진행할 수 있다. 이제 각 리프들에 적힌 정수들을 왼쪽에서 오른쪽으로 읽었을 때, 그 반전수가 최소가 되도록 하는 것이 목적이다.
일단 한가지 관찰할 수 있는 사실은, 반전수를 최적화하기 위한 시행들은 각 분기점들에 대해서 독립적으로 따질 수 있다는 것이다. 그리고 조금 더 생각해보면, 두 서브트리의 위치를 바꾸지 않았을 때, 오직 두 서브트리의 두 원소를 각각 뽑아서 계산하는 반전수와 바꾸었을 때의 반전수의 합은 두 서브트리의 크기의 합이 될 것이다. 따라서, 이미 주어져있는 서브트리들의 반전수를 구하는 것으로 해당 문제를 해결할 수 있다는 사실을 알 수 있다. 이런 연산을 처리하는 방법은 분명 다양하게 존재할텐데, 첫번째는 작큰을 활용하는 것이다. 일단 두 서브트리에서 각각 원소를 가져오는 경우를 따지기 때문에, 한 서브트리 내부에 있는 원소들의 순서를 따질 필요는 없다. 따라서 단지 우리가 필요한 것은 원소를 담을 수 있고, 그리고 특정 값보다 작은 원소의 개수를 계산할 수 있는 자료구조이다. 그 자료구조를 통해 서브트리 내의 원소들을 담아두고, 합치거나 더 작은 집합에서 검색을 시도할 수 있기 때문이다. 음...근데 셋은 이터레이터 접근이 불가능해서 좀 애매하고 의외로 선택지가 아주 많진 않을지도 모르겠다. 그냥 실제로 bst를 구현하거나, 혹은 다이나믹세그를 구현하거나, 아니면 그냥 rope를 때려박아도 될 것이다. 이 경우 전체 시간복잡도는 O(nlog^2n)정도가 된다.
이제 이 문제를 보자 8210번: Tree Rotations 2 (acmicpc.net)
8210번: Tree Rotations 2
In the first line of the standard input there is a single integer n (2 ≤ n ≤ 1,000,000) that denotes the number of leaves in Byteasar's tree. Next, the description of the tree follows. The tree is defined recursively: if there is a leaf labelled with p
www.acmicpc.net
무려 제한이 100만이다! 로그제곱이 안된다는 것은 명료하다.
사실, 위의 풀이에서 이미 올바른 접근은 나왔다. 바로 다이나믹 세그먼트 트리를 사용하는 것인데, 작-큰의 방식처럼 작은 집합의 원소를 더하는 것이 아니라, 세그먼트 트리일 때 적용 가능한 세그 머징의 방식을 채택하면 한 번의 머징이 발생할 때 작은 집합의 원소의 개수에 그 시간복잡도가 bound되도록 할 수 있다!
이제 세그 머징이 무엇인지 알아보자. 일종의 작-큰과 유사한 아이디어를 사용하는데, 이 아이디어는 총 n개의 원소들에 대해 각각의 세그를 만든 다음에, 이들을 전부 합쳐서 하나의 세그로 변형시킬 때 총 시간복잡도 및 공간복잡도를 O(nlogn)으로 하는 테크닉이다. 작-큰에 익숙하다면, 한 번의 병합 과정이 O(min(x,y))이면 충분하다는 사실을 알 것이다. 이를 어떻게 하냐면, 두 세그먼트 트리가 있다고 생각하자. 동일한 구간을 나타내는 두 정점에 대해서 merge 함수를 실행하자. 만약 한 세그먼트 트리에 해당 구간을 나타내는 정점이 없다면, 그냥 단순하게 그 정점이 존재하는 쪽의 정점을 채택하고 바로 종료하면 충분하다. 이제 merge 함수는 그 둘의 왼쪽 정점과 오른쪽 정점들 각각에 대해 merge를 진행하고, 합쳐진 결과가 될 세그먼트 트리의 새로운 노드를 반환해준다. 이제 현 시점에 merge 함수는 받은 두 노드를 통해 자신의 값을 갱신하고, 그 노드를 위쪽에서 호출되었을 merge 함수에 반환한다.
즉, 세그 머징이라는 것은 두 세그먼트 트리를 겹치는 것이다. 말로는 이해가 힘들 수도 있기 때문에, 코드를 참조하는 것을 추천한다.
아무튼, 우리는 두 세그를 전보다 빠르게 합칠 수 있다. 이제 문제를 풀기 위해 유일한 문제점은, 반전수를 빠르게 구하는 것이다. 이 또한 생각해보면 꽤나 직관적으로 풀리는데, 예를 들어 세그 a,b에 각각 x,y가 있고, x>y가 성립한다고 하자. 그렇다면 이 둘을 포함하며, 중간점을 잡았을 때 둘이 분리되는 구간을 나타내는 정점이 두 세그에게 모두 존재한다는 것은 굉장히 자명한 사실이다. 이때 x는 세그 a의 해당 노드의 오른쪽에 존재하고, y는 세그 b의 해당 노드의 왼쪽에 존재한다. 즉, 세그 a 기준 오른쪽 자식의 크기 * 세그 b 기준 왼쪽 자식의 크기를 반전수에 더하면 된다.
사실 이는 작-큰의 시간복잡도를 최적화함으로써 얻어낸 결과라고 볼 수 있다. 즉, 세그 머징은 세그먼트 트리에 작-큰 테크닉을 O(min(a,b))만에 적용할 수 있는 테크닉이라고 생각할 수 있다. 아님망고
이제 짜야 하는데 귀찮아서 자고 일어나서 해야겠다.
믕...지금 짜보고 있는데 생각해보니까 다이나믹 세그의 메모리는 나이브하게 짜면 O(nlogn)인데 이 경우에도 시복이 잘 bound 되나...? 유지성적 구현을 거칠 필요가 있을 것 같은데 어케 해야할지 모르겠다...
아 근데 생각해보니까 애초에 정수들 범위가 그닥 크지도 않고 어쨌든 뭔가 잘 되서 합쳐지는 횟수가 bound될 것 같긴 한데 음...
방금 알아냈는데, 그냥 한번 합쳐질 때마다 총 노드의 개수가 최소 1개 감소하기 때문에 합쳐지는 연산의 횟수가 bound되는거였다.
또 방금 알아낸 사실은 2번째 버전의 문제를 풀기엔 공간복잡도 이슈때문에 스플레이 트리같은걸 쓰는게 낫다고 하는 것 같긴 한데...잘 모르겠다.
4. 세그비츠
아마 이 시리즈들에서 다루는 가장 웰노운인 웰노운 테크닉중 하나가 되지 않을까? 물론 위에 있는 내용들도 그렇지만, 이렇게 '웰노운'적이면서 웰노운인 웰노운은 찾기 힘들다.
그래서, 대체 세그비츠는 무엇일까? 세그비츠는 어떤 애니메이션 '엔젤 비츠'에서 이름을 따왔다고 한다. 왜 그랬는진 모르겠다. 나였다면 코코아 트릭이라고 명명했을 것이다.
아무튼, 해당 알고리즘에 대한 좋은 intuition은 다음 문제가 있을 것이다: 17474번: 수열과 쿼리 26 (acmicpc.net)
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
www.acmicpc.net
간단히 말해서, 수열에 구간 최솟값 갱신 쿼리를 날리고, 합 질의와 최댓값 질의를 처리해야 한다. 몇가지 시도를 해볼 수야 있겠지만, 일단 레이지 세그가 가장 해볼법한 접근이라고 생각해보자. 구간 갱신과 질의를 동시에 관리 가능한, 일반적인 자료구조는 레이지 세그를 제외하곤 많지 않은 것 같다.
각 구간에 대한 노드마다, 구간 내에 있는 최댓값과 그 최댓값의 개수, 최댓값이 아닌 다른 값들중 최댓값을 저장한다고 하자. 일반적인 레이지라면 구간 업데이트에 대해 구간에 속하지 않음을 알아내고는 바로 return하거나(break), 혹은 구간에 완벽히 속함을 알고는 레이지 값을 매겨준 뒤 return한다(tag). 그러나, 우리는 이 return 조건들을 조금 더 수정할 것이다. 만약, 어떤 노드의 max가 갱신값보다 작다면, 그 노드 아래의 어디에서도 갱신이 일어나지 않음을 알 수 있다. 즉, 이는 break의 조건으로 추가해주면 될 것이다. tag의 경우에는 단순히 구간에 속하기만 한다고 해서 레이지를 남기기 애매할 것이다. 한 노드를 통해 우리가 알 수 있는 것은, 단지 그 구간의 최댓값과 두번째 최댓값들에 대한 정보뿐인데, 두 값보다 작은 값으로 갱신되는 쿼리가 주어질 경우에는 레이지 값을 남기기 애매하다. 따라서, 최댓값과 두번째 최댓값 사이의 값에 대한 갱신이 주어진 경우에만 레이지를 남겨보자.
이러한 관리하에, 두 자식의 최댓값과 두번째 최댓값을 알고 있다면 무조건 상위 노드에 대한 값도 계산 가능하다는 사실을 알 수 있다. 또한, 레이지의 전파가 가능한 이유는 두 자식 노드 전부 두번째 최댓값은 '무조건' 레이지값보다 작을수밖에 없기 때문에, 무조건 break 조건에 걸리거나 tag 조건에 걸리게 된다.
따라서 이러한 자료구조를 통해서 문제를 해결할 수 있다는 사실을 깨달았다! 하지만, 아직 우리는 문제를 '빠르게' 해결한다는 것에 대한 어떠한 관찰도 하지 못했다. break 조건과 tag 조건 둘 다에 걸리지 않는 갱신이 굉장히 많이 발생할 가능성을 배제할 수 없기 때문이다. 그러나, 이 자료구조는 놀랍게도 이 문제를 빠르게 해결할 수 있다.
이를 위해서, 각 노드들이 자신이 나타내는 구간까지도 가지고 있다고 생각해보자. 실제로 우리가 직접 갱신할 필요는 없이, 만약 3번째 경우가 발생하는 노드 v가 존재한다면, 그것은 그 노드가 나타내는 구간에서 서로 달랐던 두 값들이 동일해진다는 사실을 의미한다. 즉, 해당 노드 내에서 서로 다른 값의 개수가 1개 줄어들게 된다. 그런데, 모든 노드에 저장된 숫자들은 O(nlogn)이기 때문에, 3번째 경우는 많아야 O(nlogn)번 발생한다는 사실을 알 수 있다! 조금 더 간단히 말하자면, 크기 x인 구간을 가리키는 노드에서 3번째 경우는 많아야 x번 일어나고, 해당 논리를 통해 세그 전체에서 발생하는 3번째 경우의 횟수가 O(nlogn)으로 bound된다는 사실을 알 수 있는 것이다.
풀 수 있는 문제들의 티어에 비하면 그렇게 어려운 아이디어는 아니라고 생각한다. 물론 이걸 "발상"하는 것은 굉장한 노고가 필요할 것이고 정말로 그 티어에 걸맞는 난이도겠지만, 어쨌든 우리는 이미 이 테크닉을 배운 상태고, 이를 적용하면 간단히 풀리는 문제라는 것 또한 알 수 있다.
암튼 난 짜러가야겠다.
다1 동식 [감사합니다]. 엥 까고보니까 다2였네 암튼 코드는 다음과 같이 짜면 된다. 사실 아이디어적인 테크닉이라서 이해만 하면 코드를 짜는건 어렵지 않은 것 같다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct Node{
ll mx,mx2,mxcnt,sum;
Node(){
mx=0; mx2=-1; mxcnt=1; sum=0;
}
};
Node combine(Node x,Node y)
{
Node node;
node.mx=max(x.mx,y.mx);
if(x.mx==y.mx)
{
node.mx2=max(x.mx2,y.mx2);
node.mxcnt=x.mxcnt+y.mxcnt;
node.sum=x.sum+y.sum;
return node;
}
if(x.mx>y.mx)
swap(x,y);
node.mx=y.mx;
node.mx2=max(y.mx2,x.mx);
node.mxcnt=y.mxcnt;
node.sum=x.sum+y.sum;
return node;
}
Node seg[2200000];
ll n,m,i,j,x,y,z,l,r,q,t;
void propagate(ll x,ll y,ll z)
{
if(x==y)
return;
if(seg[z*2].mx>seg[z].mx)
{
seg[z*2].sum-=seg[z*2].mxcnt*(seg[z*2].mx-seg[z].mx);
seg[z*2].mx=seg[z].mx;
}
if(seg[z*2+1].mx>seg[z].mx)
{
seg[z*2+1].sum-=seg[z*2+1].mxcnt*(seg[z*2+1].mx-seg[z].mx);
seg[z*2+1].mx=seg[z].mx;
}
}
void update(ll x,ll y,ll z,ll v)
{
Node node=seg[z];
propagate(x,y,z);
if(y<l||x>r||node.mx<=v)
{
return;
}
if(l<=x&&y<=r&&node.mx2<v)
{
seg[z].sum-=(seg[z].mxcnt)*(node.mx-v);
seg[z].mx=v;
propagate(x,y,z);
return;
}
update(x,(x+y)/2,z*2,v);
update((x+y)/2+1,y,z*2+1,v);
seg[z]=combine(seg[z*2],seg[z*2+1]);
}
ll query1(ll x,ll y,ll z)
{
propagate(x,y,z);
if(y<l||x>r)
return 0;
if(l<=x&&y<=r)
{
return seg[z].sum;}
return query1(x,(x+y)/2,z*2)+query1((x+y)/2+1,y,z*2+1);
}
ll query2(ll x,ll y,ll z)
{
propagate(x,y,z);
if(y<l||x>r)
return 0;
if(l<=x&&y<=r)
return seg[z].mx;
return max(query2(x,(x+y)/2,z*2),query2((x+y)/2+1,y,z*2+1));
}
int main()
{
scanf("%lld",&n);
for(i=1048576;i<=2097151;i++)
{
seg[i].mxcnt=1;
seg[i].mx=0;
seg[i].mx2=-1;
seg[i].sum=0;
}
for(i=1;i<=n;i++)
{
scanf("%lld",&x);
seg[i+1048575].mxcnt=1;
seg[i+1048575].mx=x;
seg[i+1048575].mx2=-1;
seg[i+1048575].sum=x;
}
for(i=1048575;i>=1;i--)
{
seg[i]=combine(seg[i*2],seg[i*2+1]);
}
scanf("%lld",&q);
for(i=1;i<=q;i++)
{
scanf("%lld",&t);
if(t==1)
{
scanf("%lld %lld %lld",&x,&y,&z);
l=x; r=y;
update(1,1048576,1,z);
continue;
}
if(t==2)
{
scanf("%lld %lld",&x,&y);
l=x; r=y;
printf("%lld\n",query2(1,1048576,1));
continue;
}
if(t==3)
{
scanf("%lld %lld",&x,&y);
l=x; r=y;
printf("%lld\n",query1(1,1048576,1));
continue;
}
}
}
5. wavelet tree
wavelet tree란 무엇인가? 대충 머지소트트리를 값 기준으로 진행했다는 등의 표현이 꽤 나쁘지 않게 이 자료구조를 설명하고 있다. 일단 귀찮아서 던진다.
