题目链接

明明标着前缀和却不是用前缀和写的让人有些费解

数组线段树做法

int min(int a, int b)
{
    if (a > b)
        return b;
    else
        return a;
}

int t(char ch) //将碱基转换成数字
{
    if (ch == 'A')
        return 1;
    else if (ch == 'C')
        return 2;
    else if (ch == 'G')
        return 3;
    else if (ch == 'T')
        return 4;
}

void build(int l, int r, int k, int num[], int m[])
{
    if (l == r)
    {
        m[k] = num[l];
        return;
    }
    int mid = (l + r) >> 1;
    if (l <= mid)
        build(l, mid, k << 1, num, m);
    if (mid < r)
        build(mid + 1, r, (k << 1) + 1, num, m);
    m[k] = min(m[k * 2], m[k * 2 + 1]);
}

int query(int l, int r, int ql, int qr, int k, int m[])
{
    if (l >= ql && r <= qr)
        return m[k];
    int res = (1 << 31) - 1; //初始化为inf
    int mid = (l + r) >> 1;
    if (mid >= ql)
        res = min(res, query(l, mid, ql, qr, k << 1, m));
    if (mid < qr)
        res = min(res, query(mid + 1, r, ql, qr, (k << 1) + 1, m));
    return res;
}
struct Results solution(char *S, int P[], int Q[], int M)
{
    struct Results result;
    static int m[500000]; //维护最小值 最小需要4N的空间
    static int num[100010]; 
    static int ans[50010]; 
    int len = strlen(S);
    for (int i = 1; i <= len; i++)
        num[i] = t(S[i - 1]);//将字符串转换成数字存入num中
    build(1, len, 1, num, m);
    for (int i = 0; i < M; i++)
    {
        ans[i]=query(1, len, P[i] + 1, Q[i] + 1, 1, m); //这里P和Q的下标问题找了好久都没发现
    }
    result.A=ans;
    result.M=M;
    return result;
}