2018百度之星资格赛B 区间查询+ 前缀和（线段树）

题目链接：http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=820&pid=1002

题目大意:
多样例测试 第一行 T 样例次数
第二行n, q，（n字符串长度， q询问次数）
第三行输入字符串只包含大写字母
**接下来m行每行输入l, r **
1<=T<=20, 1<= n,q<=10^5
先输出一行信息 “Case #x:”（不含引号），其中 x 表示这是第 x 组测试数据
在对每一行输出 [l, r]，

输出区间[l, r]中字典序最小的字母的个数

思路：如果对于每一次询问在相应的区间查询，时间复杂度O(n^2),肯定超时
如果能把查询的时间复杂度变成O(lgn)，应该能AC， 区间首先就想到了线段树
思路一：线段树维护区间最小字母的个数，和最小字母
果断AC，看了一下运行时间1500ms左右，而有个AC只用了700，800ms左右，我以为是自己的线段树模板太复杂了，便去一个ACM讨论群问他们的用的什么模板
我： 你们都用的什么模板怎么只用了700ms
大佬：这道题不用模板，
我： 你们没有用线段树？？？
大佬：前缀和就了，这是签到题啊
我：…
思路二：前缀和

思考：前缀和很强大，当看到区间时应该考虑线段树和前缀和

线段树

#include <bits/stdc++.h>
using namespace std;
#define MAX_NODE 400005

struct NODE{
    int l, r;

}node[MAX_NODE];

int sum[MAX_NODE];
char ch[MAX_NODE];

void js(int i, int l, int r)
{
    node[i].l=l;
    node[i].r=r;

    if(l==r)
    {
        scanf("%c",&ch[i]);
        sum[i]=1;
        return;
    }

    int mid=(l+r)/2;
    js(i*2,l,mid);
    js(i*2+1,mid+1,r);

    if(ch[i*2]==ch[i*2+1])//维护区间信息
    {
        sum[i]=sum[i*2]+sum[i*2+1];
        ch[i]=ch[i*2];
    }
    else
    {
        if(ch[i*2]<ch[i*2+1])
        {
            sum[i]=sum[i*2];
            ch[i]=ch[i*2];
        }
        else
        {
            sum[i]=sum[i*2+1];
            ch[i]=ch[i*2+1];
        }
    }
}

int s=0;
char str='z'+1;

void cx(int i, int l, int r)
{
    if(node[i].l==l&&node[i].r==r)
    {
        if(ch[i]==str)
        {
            s+=sum[i];
        }
        else
        {
            if(ch[i]<str)
            {
                s=sum[i];
                str=ch[i];
            }
        }
        return;
    }

    //到相应的区间进行查找
    int mid=(node[i].l+node[i].r)/2;
    if(r<=mid)
        cx(i*2,l,r);
    else if(l>mid)
        cx(i*2+1,l,r);
    else
    {
        cx(i*2, l, mid);
        cx(i*2+1, mid+1, r);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        int n, q;
        scanf("%d%d%*c",&n,&q);
        js(1, 1, n);
        printf("Case #%d:\n",i);
        while(q--)
        {
            s=0;
            str='z'+1;
            int l, r;
            scanf("%d%d",&l,&r);
            cx(1, l, r);
            printf("%d\n",s);
        }
    }


    return 0;
}

前缀和

#define mm(a) memset(a,0,sizeof(a));
#define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
#define Fopen freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
#define rep(i,n) for(int i=1;i<=(n);i++)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = (int)2e5+5;

int T,tin[MAXN][30];
int n,q,l,r;
char s[MAXN];

int main() {
    scanf("%d",&T);
    rep(cas,T) 
	{
        scanf("%d%d",&n,&q);
        scanf("%s",s+1);
        mm(tin);
        rep(i,n) 
		{
            for(int j=0; j<26; j++) 
			{
                tin[i][j]=tin[i-1][j];
            }
            tin[i][s[i]-'A']++;
        }
        printf("Case #%d:\n",cas);
        
        rep(qq,q) 
		{
            scanf("%d%d",&l,&r);
            for(int i=0;; i++) 
			{
                if(tin[r][i]-tin[l-1][i]) 
				{
                    printf("%d\n",tin[r][i]-tin[l-1][i]);
                    break;
                }
            }
        }
    }
    return 0;
}