题目描述#

由于 Wulala 在上个问题中的精彩表现，公主认为 Wulala 是一个很棒的人，就把 Wulala 留在了 X 国。这时正好公主的一位传教士朋友来拜访公主，于是想找 wulala 帮忙X 国如同一条直线，其中有 n 个城市,从东向西分别编号为 1~n。而他的国家中有 m 种宗教，每个城市一定会有一种信仰的宗教。

有时候有些城市为了获得更多的认可，会派出信仰本城市宗教的传教士前往其他国家。X 国 的传教士都十分厉害，只要是他途经的地方都会改信他所传播的宗教。 传教士们在路上碰到自己宗教的城市自然就不用传教了，可以停下来看看里番啥的，所以每 一个传教士在旅行前都会计算自己可以在多少城市停下来(不包括起始的城市)。 而传教士们都是文科僧，数学是很差的，所以他希望 Wulala 能帮他计算。可 Wulala 数学也不好，但他又不想在公主面前丢脸，你能帮帮他吗？

输入#

第一行两个整数 n，m 第二行 n 个整数第 i 个整数代表第 i 各城市信仰的宗教 第三行一个整数 T 代表传教士的个数 接下来 T 行每行两个整数 x，y 代表 x 城向 y 城派遣了一个传教士(保证 x < y)

输出#

输出 T 行，第 i 行代表第 i 个传教士询问的答案

样例输入#

2 2
1 2
2
1 2
1 2

样例输出#

0
1

提示#

对于 30%的数据 n <= 100000, m <= 10, T <= 100 对于 60%的数据 n <= 100000, m <= 10, T <= 100000 对于 100%的数据 n <= 100000, m <= 300, T <= 100000

题解#

分块直接维护就可以了
原来分块也可以是正解

/**
******************************************************************************
* @file Wulala
* @author   WildRage
* @version v 0.9
* @date 2017-8-10 10:58:12
* @brief 
******************************************************************************
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100001, M = 301;
int a[N], in[N], n, m;
int Sum[500][305], Change[500];
int block;
int lp[500], rp[500];
int Query(int l, int r)
{
    int L = in[l], R = in[r];
    int ans = 0;
    bool flag = 0;
    if (L == R)
    {
        if (Change[L])
            return r - l;
        for (int i = l + 1; i <= r; i++)
        {
            if (a[i] == a[l])
                ans++;
            a[i] = a[l];
        }
        for (int i = lp[L]; i < l; i++)
            if (a[i] != a[l])
            {
                flag = 1;
                break;
            }
        if (flag == 1)
            return ans;
        for (int i = r + 1; i <= rp[R]; i++)
        {
            if (a[i] != a[l])
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
            Change[L] = a[l];
        return ans;
    }
    else
    {
        if (Change[L] == a[l])
            ans += (rp[L] - l);
        else
        {
            flag = 0;
            for (int i = l + 1; i <= rp[L]; i++)
            {
                if (a[i] == a[l])
                    ans++;
                a[i] = a[l];
            }
            for (int i = lp[L]; i < l; i++)
                if (a[i] != a[l])
                {
                    flag = 1;
                    break;
                }
            if (!flag)
                Change[L] = a[l];
        }
        if (Change[R])
        {
            if (Change[R] == a[l])
                ans += (r - lp[R] + 1);
            else
            {
                for (int i = lp[R]; i <= r; i++)
                    a[i] = a[l];
                Change[R] = 0;
            }
        }
        else
        {
            flag = 0;
            for (int i = lp[R]; i <= r; i++)
            {
                if (a[i] == a[l])
                    ans++;
                a[i] = a[l];
            }
            for (int i = r + 1; i <= rp[R]; i++)
                if (a[i] != a[l])
                {
                    flag = 1;
                    break;
                }
            if (!flag)
                Change[R] = a[l];
        }
        for (int i = L + 1; i < R; i++)
        {
            if (Change[i])
            {
                if (Change[i] == a[l])
                    ans += block;
                else
                {
                    for (int j = lp[i]; j <= rp[i]; j++)
                        a[j] = a[l];
                    Change[i] = a[l];
                }
            }
            else
            {
                for(int j = lp[i];j<=rp[i];j++)
                {
                    if(a[j]==a[l])
                        ans++;
                    a[j] = a[l];
                }
                Change[i] = a[l];
            }
        }
        return ans;
    }
}
int main()
{
    int c, b;
    scanf("%d%d", &n, &m);
    block = 316;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        in[i] = (i - 1) / block + 1;
        Sum[in[i]][a[i]]++;
    }
    for (int i = 1; i <= in[n]; i++)
        lp[i] = (i - 1) * block + 1, rp[i] = min(n, i * block);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &c, &b);
        int ans = Query(c, b);
        printf("%d\n", ans);
    }
}