题目描述
由于 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);
}
}