10541번: 싸리와 버드의 피라미드

https://www.acmicpc.net/problem/10541


$O(lk+k\lg k)$

각 문자에 대한 누적합을 알고 있다하자. 이를 통해 어떤 구간에서 어떤 문자의 개수를 상수 시간 안에 알 수 있다.
a번째 줄의 어떤 문자의 개수를 구해야 하는데 이것은 a-1번째 줄에서 잘린 문자열과 a번째 문자열을 가지고 계산할 수 있다.
주어지는 n값이 매우 크므로 a의 제곱연산은 long long int 범위에 들어오지 않음을 유의해서 미리 문자열 길이로 나눈 나머지를 가지고 곱하는 방법을 사용하자.
각 문자에 대한 누적합을 배열에 미리 저장해 놓으려고 하면 메모리가 부족할 것이다.
따라서 입력으로 주어지는 쿼리들을 미리 받아놓고 알파벳순으로 정렬한뒤 필요한 문자에 대해서 그때마다 누적합을 구해 놓아야 한다.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAX_L = 1e6, MAX_K = 5e4;
typedef long long ll;
ll n, res[MAX_K + 1], x, t;
int k, len, s[MAX_L + 1];
char str[MAX_L + 2];
struct st {
    ll idx, a;
    char c;
    bool operator<(st i) const {
        return c < i.c;
    }
}q[MAX_K + 1];
int main() {
    scanf("%lld %s %d", &n, str + 1, &k);
    len = strlen(str + 1);
    char c;
    for (int i = 1; i <= k; i++) scanf("%lld %c", &x, &c), q[i] = { i,x,c };
    sort(q + 1, q + 1 + k);
    for (int i = 1; i <= k; i++) {
        if (q[i - 1].c != q[i].c)
            for (int j = 1; j <= len; j++) s[j] = s[j - 1] + (str[j] == q[i].c);
        t = q[i].a % 2 ? (q[i].a - 1) / 2 % len*(q[i].a%len) % len
            : (q[i].a - 1) % len*(q[i].a / 2 % len) % len;
        res[q[i].idx] = (q[i].a + t) / len*s[len] + s[(q[i].a + t) % len] - s[t];
    }
    for (int i = 1; i <= k; i++) printf("%lld\n", res[i]);
    return 0;
}