알파벳과 쿼리 (Hard) (BOJ 31830)

문제

이미지클릭

문제 설명

• 문제에서는 구간에 대해서 연속이고 동일한 알파벳의 그룹이 몇 개인지 구해야 하는 문제이다.
• 예를 들어 AABBCCDD가 있으면 처음부터 끝까지 연속이고 동일한 알파벳의 개수는 AA, BB, CC, DD, 즉 4가지가 된다.
• 하지만 여기에서는 구간에 대해서 알파벳을 알파벳 순서에 대해서 다음 알파벳으로 변경해야 할 수도 있다. (Z는 A로)
• 예를 들어 AABBCCDD에서 2번째 부터 4번째를  변경해야 한다면 A를 B로 B를 C로 변경한다면 ABCCCCDD가 된다.

문제 해설

• 이 문제에서 서로 다른 그룹이하는 것을 판별하기 위해서 제일 중요한 것은 인접한 알파벳이 같은지 다른지를 판별해야 한다는 것이다.

AABBCCDD

위의 문자열에서 부분문자열인 "ABBC"가 있다면 서로 다른 문자열임을 파악하기 위해서는 A와 B 그리고 B와 C가 다르다는 것을 파악해 주면 된다! 

즉 세그트리에서 인접한 두 알페벳이 같은지 다른 지만을 확인하면서 트리를 업데이트해 주면 된다.

• 이외의 부분은 세그트리의 일반적인 문제들과 동일하다.

최종 코드

#include <bits/stdc++.h>
#define INF 200004
using namespace std;

int n, q, qr, ql, ans;
string s;
int d[INF], L[INF * 4], R[INF * 4], cnt[INF * 4], lazy[INF * 4];

void propagation(int node, int l, int r) {
    if (lazy[node]) {
        L[node] = (L[node] + lazy[node]) % 26;
        R[node] = (R[node] + lazy[node]) % 26;
        if (l != r) {
            lazy[node * 2] = (lazy[node * 2] + lazy[node]) % 26;
            lazy[node * 2 + 1] = (lazy[node * 2 + 1] + lazy[node]) % 26;
        }
        lazy[node] = 0;
    }
}

void Init(int node, int l, int r) {
    if (l == r) {
        L[node] = R[node] = d[l];
        cnt[node] = 1;
        return;
    }
    int middle = (l + r) / 2;
    Init(node * 2, l, middle);
    Init(node * 2 + 1, middle + 1, r);
    L[node] = L[node * 2];
    R[node] = R[node * 2 + 1];
    cnt[node] = cnt[node * 2] + cnt[node * 2 + 1] - (R[node * 2] == L[node * 2 + 1]);
}

void update(int node, int l, int r, int x, int y) {
    propagation(node, l, r);
    if (l > y || r < x) return;
    if (x <= l && r <= y) {
        lazy[node] = (lazy[node] + 1) % 26;
        propagation(node, l, r);
        return;
    }
    int middle = (l + r) / 2;
    update(node * 2, l, middle, x, y);
    update(node * 2 + 1, middle + 1, r, x, y);
    L[node] = L[node * 2];
    R[node] = R[node * 2 + 1];
    cnt[node] = cnt[node * 2] + cnt[node * 2 + 1] - (R[node * 2] == L[node * 2 + 1]);
}

void query(int node, int l, int r, int x, int y) {
    propagation(node, l, r);
    if (l > y || r < x) return;
    if (x <= l && r <= y) {
        if (ql == -1) {
            ql = L[node];
            qr = R[node];
            ans = cnt[node];
        } else {
            ans += cnt[node] - (qr == L[node]);
            qr = R[node];
        }
        return;
    }
    int middle = (l + r) / 2;
    query(node * 2, l, middle, x, y);
    query(node * 2 + 1, middle + 1, r, x, y);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q >> s;
    for (int i = 0; i < n; i++) {
        d[i + 1] = s[i] - 'A';
    }
    Init(1, 1, n);
    while (q--) {
        int x, l, r;
        cin >> x >> l >> r;
        if (x == 1) {
            qr = ql = ans = -1;
            query(1, 1, n, l, r);
            cout << ans << "\n";
        } else {
            update(1, 1, n, l, r);
        }
    }
}

• 기본적으로 변수들은 다음과 같이 사용된다.

int n, q, qr, ql, ans;
string s;
int d[INF], L[INF * 4], R[INF * 4], cnt[INF * 4], lazy[INF * 4];

//n: 알파벳 개수
//q: 쿼리의 개수
//qr: 구간에 대해서 값을 그룹의 개수를 불러올 때 오른쪽 끝의 알파벳
//ql: 구간에 대해서 값을 그룹의 개수를 불러올 때 왼쪽 끝의 알파벳
//ans: 범위에 대한 그룹의 개수
//d[]: 알파벳 저장
//:L[]: 제일 왼쪽에 있는 알파벳 개수
//R[]: 제일 오른쪽에 있는 알파벳 개수
//cnt[]: 그룹의 개수
//lazy[]: update를 했을 때 lazy에 update된 값을 저장

• Init 혹은 update를 해주는 방식은 다음과 같다.

void update(int node, int l, int r, int x, int y) {
    propagation(node, l, r);
    if (l > y || r < x) return; 
    if (x <= l && r <= y) {
        lazy[node] = (lazy[node] + 1) % 26; //알파벳은 26개 이기에 26의 나머지로 지정해줘야함
        propagation(node, l, r); // lazy_propagation
        return;
    }
    int middle = (l + r) / 2;
    update(node * 2, l, middle, x, y);
    update(node * 2 + 1, middle + 1, r, x, y);
    L[node] = L[node * 2]; //맨 왼쪽 값은 L에 저장
    R[node] = R[node * 2 + 1]; //맨 오른쪽 값은 R에 저장
    cnt[node] = cnt[node * 2] + cnt[node * 2 + 1] - (R[node * 2] == L[node * 2 + 1]);
    //왼쪽 부분과 오른쪽 부분을 기본적으로 더해줌!
    //cnt는 node*2를 기준으로 맨 오른쪽 값과 node*2+1 맨 왼쪽 값이 같으면 -1을 해주고 아니면 pass!
}

• query부분도 다음과 같이 설정해 준다.

void query(int node, int l, int r, int x, int y) {
    propagation(node, l, r); //lazy_propagation
    if (l > y || r < x) return;
    if (x <= l && r <= y) {
        if (ql == -1) { //아직 범위내의 값을 탐색을 하지 않았을 때
            ql = L[node]; 
            qr = R[node];
            ans = cnt[node];
        } else {
            ans += cnt[node] - (qr == L[node]); 
            //맨 왼쪽과 현제 까지 탐색한 맨 오른쪽이 같다면 1을 빼줌
            qr = R[node];
        }
        return;
    }
    int middle = (l + r) / 2;
    query(node * 2, l, middle, x, y);
    query(node * 2 + 1, middle + 1, r, x, y);
}

여기에서 그룹을 찾는 부분에서 왜 qr와 L [node]를 찾는지 의문일 수도 있다.

우리는 기본적으로 왼쪽부터 업데이트를 하기 때문에 다음과 같이 트리를 확인할 수 있다.

 2~3의 범위를 찾는다고 가정한다면 기본적으로 node=5인 부분(왼쪽)을 처음으로 탐색하게 된다. 

여기에서 ql, qr, ans를 초기화해 준다.

그 이후에 node=3인 부분(오른쪽)을 탐색하게 되는 데 지금은 이때는 qr과 L [3]와 비교하여서 그룹을 확인해야 한다.

즉 여기서 알 수 있는 부분은 트리의 왼쪽 부분부터 탐색을 시작하기 때문에 qr과 L [node] 값을 비교해야 한다!