Codeforces 체육관 100971 M 좋 은 문자열 DP + 데이터 구조 로 분해

제목 의 대의:
k 개의 서로 다른 문자 가 있 는 문자열 을 좋 은 문자열 로 정의 합 니 다.현재 문자열 을 보 여 줍 니 다. 이 문자열 의 모든 접두사 Si 는 최소한 몇 개의 좋 은 문자열 로 연결 되 어 있 는 지, 좋 은 문자열 로 연결 되 지 않 으 면 출력 - 1 입 니 다.예: k = 2 abac 는 적어도 ab 와 ac 라 는 두 문자열 의 연결 입 니 다.문자열 길이 < = 2e5
방법:
비교적 직관 적 인 dp 방정식 은 다음 과 같다.
그러나 데이터 구 조 를 사용 하여 시간 복잡 도 를 O (nlogn) 로 낮 출 수 있다.먼저 모든 i, j 의 범위 가 얼마나 되 는 지 에 대해 Sj... i 는 좋 은 문자열 이 고 j 의 구간 을 l [i] 와 r [i] 로 표시 합 니 다.뒤에서 앞으로 O (n) 시간 내 에 l [i] 와 r [i] 를 미리 처리 할 수 있 습 니 다.다음은 구간 의 최소 치 를 구하 기 위해 문 제 를 바 꾸 고, 이어서 선분 수 를 사용 하여 유지 할 수 있다.
코드:
Accepted
10012kb
109ms
GNU G++ 4.9.2
2190Bytes

#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 1e5 * 2 + 10;

char buf[maxn];

int cha[26];

int ql[maxn], qr[maxn];

void init(int len, int k)
{
    memset(qr, -1, sizeof qr);
    int l = len, ct = 0;
    for (int i = len ; i > 0 ; i--)
    {
        while(ct < k && l > 0)
        {
            if (!cha[buf[l] - 'a'])
                ct++;
            cha[buf[l] - 'a']++;
            --l;
        }
        if (ct == k)
            qr[i] = l + 1;
        if (--cha[buf[i] - 'a'] == 0)
            --ct;
    }
    memset(cha, 0, sizeof cha);

    memset(ql, -1, sizeof ql);
    l = len, ct = 0;
    for (int i = len ; i > 0 ; i--)
    {
        while(ct <= k && l > 0)
        {
            if (!cha[buf[l] - 'a'])
                ct++;
            cha[buf[l] - 'a']++;
            --l;
        }
        if (ct == k + 1)
            ql[i] = l + 2;
        else if (ct == k && l == 0)
            ql[i] = l + 1;
        if (--cha[buf[i] - 'a'] == 0)
            --ct;
    }
}

struct tree
{
    int num;
    int m;
}t[maxn * 4];

void build(int l, int r, int p)
{
    t[p].num = maxn;
    if (l == r)
        return;
    t[p].m = (l + r) / 2;
    build(l, t[p].m, 2 * p);
    build(t[p].m + 1, r, 2 * p + 1);
}

int query(int l, int r, int ll, int rr, int p)
{
    if (l == ll && r == rr)
        return t[p].num;
    if (ll > t[p].m)
        return query(t[p].m + 1, r, ll, rr, 2 * p + 1);
    else if (rr <= t[p].m)
        return query(l, t[p].m, ll, rr, 2 * p);
    return min(
        query(l, t[p].m, ll, t[p].m, 2 * p),
        query(t[p].m + 1, r, t[p].m + 1, rr, 2 * p + 1));
}

void modify(int l, int r, int p, int pp, int num)
{
    if (l == r)
    {
        t[p].num = num;
        return;
    }
    if (pp <= t[p].m)
        modify(l, t[p].m, 2 * p , pp, num);
    else
        modify(t[p].m + 1, r, 2*p + 1, pp, num);
    t[p].num = min(t[p].num, num);
}

int main()
{
    int k, len;
    scanf("%d%s", &k, buf + 1);
    len = strlen(buf + 1);
    init(len, k);
    build(0, len, 1);
    for (int i = 1 ; i <= len ; i++)
    {
        int ans = -1;
        if (ql[i] == 1)
            modify(0, len, 1, i, ans = 1);
        else if (ql[i] != -1)
        {
            ans = query(0, len, ql[i] - 1, qr[i] - 1, 1);
            //printf("%d
", ans);
            if (ans != maxn)
                modify(0, len, 1, i, ++ans);
            else
                ans = -1;
        }
        printf("%d ", ans);
    }
    return 0;
}