公主的朋友 - NekoMio's Blog

题目描述#

由于 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

题解#

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

1
/**
2
******************************************************************************
3
* @file Wulala
4
* @author   WildRage
5
* @version v 0.9
6
* @date 2017-8-10 10:58:12
7
* @brief
8
******************************************************************************
9
*/
10
#include <cstdio>
11
#include <cstring>
12
#include <algorithm>
13
using namespace std;
14
const int N = 100001, M = 301;
15
int a[N], in[N], n, m;
16
int Sum[500][305], Change[500];
17
int block;
18
int lp[500], rp[500];
19
int Query(int l, int r)
20
{
21
    int L = in[l], R = in[r];
22
    int ans = 0;
23
    bool flag = 0;
24
    if (L == R)
25
    {
26
        if (Change[L])
27
            return r - l;
28
        for (int i = l + 1; i <= r; i++)
29
        {
30
            if (a[i] == a[l])
31
                ans++;
32
            a[i] = a[l];
33
        }
34
        for (int i = lp[L]; i < l; i++)
35
            if (a[i] != a[l])
36
            {
37
                flag = 1;
38
                break;
39
            }
40
        if (flag == 1)
41
            return ans;
42
        for (int i = r + 1; i <= rp[R]; i++)
43
        {
44
            if (a[i] != a[l])
45
            {
46
                flag = 1;
47
                break;
48
            }
49
        }
50
        if (flag == 0)
51
            Change[L] = a[l];
52
        return ans;
53
    }
54
    else
55
    {
56
        if (Change[L] == a[l])
57
            ans += (rp[L] - l);
58
        else
59
        {
60
            flag = 0;
61
            for (int i = l + 1; i <= rp[L]; i++)
62
            {
63
                if (a[i] == a[l])
64
                    ans++;
65
                a[i] = a[l];
66
            }
67
            for (int i = lp[L]; i < l; i++)
68
                if (a[i] != a[l])
69
                {
70
                    flag = 1;
71
                    break;
72
                }
73
            if (!flag)
74
                Change[L] = a[l];
75
        }
76
        if (Change[R])
77
        {
78
            if (Change[R] == a[l])
79
                ans += (r - lp[R] + 1);
80
            else
81
            {
82
                for (int i = lp[R]; i <= r; i++)
83
                    a[i] = a[l];
84
                Change[R] = 0;
85
            }
86
        }
87
        else
88
        {
89
            flag = 0;
90
            for (int i = lp[R]; i <= r; i++)
91
            {
92
                if (a[i] == a[l])
93
                    ans++;
94
                a[i] = a[l];
95
            }
96
            for (int i = r + 1; i <= rp[R]; i++)
97
                if (a[i] != a[l])
98
                {
99
                    flag = 1;
100
                    break;
101
                }
102
            if (!flag)
103
                Change[R] = a[l];
104
        }
105
        for (int i = L + 1; i < R; i++)
106
        {
107
            if (Change[i])
108
            {
109
                if (Change[i] == a[l])
110
                    ans += block;
111
                else
112
                {
113
                    for (int j = lp[i]; j <= rp[i]; j++)
114
                        a[j] = a[l];
115
                    Change[i] = a[l];
116
                }
117
            }
118
            else
119
            {
120
                for(int j = lp[i];j<=rp[i];j++)
121
                {
122
                    if(a[j]==a[l])
123
                        ans++;
124
                    a[j] = a[l];
125
                }
126
                Change[i] = a[l];
127
            }
128
        }
129
        return ans;
130
    }
131
}
132
int main()
133
{
134
    int c, b;
135
    scanf("%d%d", &n, &m);
136
    block = 316;
137
    for (int i = 1; i <= n; i++)
138
    {
139
        scanf("%d", &a[i]);
140
        in[i] = (i - 1) / block + 1;
141
        Sum[in[i]][a[i]]++;
142
    }
143
    for (int i = 1; i <= in[n]; i++)
144
        lp[i] = (i - 1) * block + 1, rp[i] = min(n, i * block);
145
    int T;
146
    scanf("%d", &T);
147
    while (T--)
148
    {
149
        scanf("%d%d", &c, &b);
150
        int ans = Query(c, b);
151
        printf("%d\n", ans);
152
    }
153
}