[UESTC 1342]郭大侠与甲铁城

郭大侠与甲铁城

全世界被产业革命的波澜推动，自近世变迁至近代之时，不死的怪物突然出现。被钢铁的皮膜包覆，只要心脏不被破坏就不会消灭，被它啃咬的人似乎也会在死过一次之后复生，并开始袭击人类。之后被称为卡巴内的这些怪物爆发性地增殖，并覆盖了全世界。
远东岛国日本的人们，为了对抗卡巴内的威胁而在各地建造名为“驿”的城寨，并困守在其中，想方设法残存下去。能够在驿之间来往的只有装甲蒸汽机车（通称骏城），驿之间通过各自生产物的融通，总算是保证了生活。
住在以炼铁和蒸汽机的生产为业的显金驿的蒸汽锻冶少年，郭大侠。他为了打倒卡巴内，开发出独自的武器“贯筒”，同时期盼着有朝一日能够发挥出自己的力量。
某天，穿越前线的骏城之一甲铁城来到了显金驿。为了车辆的清扫整备而被召唤的郭大侠，目击到了从义务性的卡巴内检阅中被免除的不可思议少女。
当晚，郭大侠与自称为无名的那位白天的少女再会，此时骏城突然暴走并突入了显金驿。乘务员全灭，而且全部变成了卡巴内！
卡巴内从显金驿中溢出。如同要从被恐慌袭击的人浪中逆行一般，郭大侠奔跑着。这一次不能逃避，我要用贯筒打倒卡巴内！
——于是，为了成为真正能闪耀光辉的男人，郭大侠的战斗开始了。
……
现在在这个城市中有n个卡巴内，每个卡巴内都有他自身的属性a[i]，郭大侠的贯筒能够一次性击穿[L,R]区间中拥有不同属性的怪物！
为了足够强的发挥自己的武器的实力，郭大侠必须提前知道自己的一次性贯筒能够击杀多少只怪物。
现在开始计算吧！
Input

第一行给你n，q，表示有n个卡巴内，q次询问
第二行有n个整数，表示每一个卡巴内的属性a[i]
接下来q行，每行两个整数Li，Ri，表示询问。
1<=n,q<=100000
1<=Li<=Ri<=n
1<=a[i]<=10000

Output

对于每一个询问，输出答案！

样例输入1：

5 3
1 2 3 1 1
1 3
1 4
3 5

样例输出1：

3
3
2 

题解：莫队算法，分块暴力求解。。。不是很懂常数为什么这么优秀。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
#define LiangJiaJun main
#define LL long long
#define pa pair<int,int>
using namespace std;
int n,Q,block,belong[100004];
int temp[100004];
struct data{int l,r,ans,sit;
}q[100004];
int a[100004];
inline bool dex(data x,data y){return (belong[x.l]==belong[y.l])?(x.r<y.r):(belong[x.l]<belong[y.l]);
}
inline bool cmp(data x,data y){return x.sit<y.sit;}
void solve(){int l=0,r=0,ans=0;for(int i=1;i<=Q;i++){while(r<q[i].r){r++;if(!temp[a[r]])++ans;temp[a[r]]++;}while(l>q[i].l){l--;if(!temp[a[l]])++ans;temp[a[l]]++;}while(r>q[i].r){if(temp[a[r]]==1)--ans;temp[a[r]]--;r--;}while(l<q[i].l){if(temp[a[l]]==1)--ans;temp[a[l]]--;l++;}q[i].ans=ans;}
}
int LiangJiaJun(){scanf("%d%d",&n,&Q);block = (int)sqrt((double)n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)belong[i] = (i-1)/block + 1;for(int i=1;i<=Q;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].sit = i;}sort(q+1,q+Q+1,dex);solve();sort(q+1,q+Q+1,cmp);for(int i=1;i<=Q;i++)printf("%d\n",q[i].ans);return 0;
}