郭大侠与甲铁城

Time Limit: 1500/800MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

cdoj 1342 郭大侠与甲铁城  树状数组+离线-LMLPHP

全世界被产业革命的波澜推动,自近世变迁至近代之时,不死的怪物突然出现。被钢铁的皮膜包覆,只要心脏不被破坏就不会消灭,被它啃咬的人似乎也会在死过一次之后复生,并开始袭击人类。之后被称为卡巴内的这些怪物爆发性地增殖,并覆盖了全世界。

远东岛国日本的人们,为了对抗卡巴内的威胁而在各地建造名为“驿”的城寨,并困守在其中,想方设法残存下去。能够在驿之间来往的只有装甲蒸汽机车(通称骏城),驿之间通过各自生产物的融通,总算是保证了生活。

住在以炼铁和蒸汽机的生产为业的显金驿的蒸汽锻冶少年,郭大侠。他为了打倒卡巴内,开发出独自的武器“贯筒”,同时期盼着有朝一日能够发挥出自己的力量。

某天,穿越前线的骏城之一甲铁城来到了显金驿。为了车辆的清扫整备而被召唤的郭大侠,目击到了从义务性的卡巴内检阅中被免除的不可思议少女。

当晚,郭大侠与自称为无名的那位白天的少女再会,此时骏城突然暴走并突入了显金驿。乘务员全灭,而且全部变成了卡巴内!

卡巴内从显金驿中溢出。如同要从被恐慌袭击的人浪中逆行一般,郭大侠奔跑着。这一次不能逃避,我要用贯筒打倒卡巴内!

——于是,为了成为真正能闪耀光辉的男人,郭大侠的战斗开始了。

……

现在在这个城市中有n个卡巴内,每个卡巴内都有他自身的属性a[i],郭大侠的贯筒能够一次性击穿[L,R]区间中拥有不同属性的怪物!

为了足够强的发挥自己的武器的实力,郭大侠必须提前知道自己的一次性贯筒能够击杀多少只怪物。

现在开始计算吧!

Input

第一行给你n,q,表示有n个卡巴内,q次询问

第二行有n个整数,表示每一个卡巴内的属性a[i]

接下来q行,每行两个整数Li,Ri,表示询问。

1<=n,q<=1000001<=n,q<=100000

1<=Li<=Ri<=n1<=Li<=Ri<=n

1<=a[i]<=100001<=a[i]<=10000

Output

对于每一个询问,输出答案!

Sample input and output

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

思路:对于区间r排序,记录一个数的前驱,在更新这个数的同时,如果前驱有值,将前面改成0;

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define esp 1e-10
const int N=1e5+,M=1e6+,mod=1e9+,inf=1e9+;
vector<int>v[N];
struct is
{
int l,r;
int pos;
}a[N];
int b[N];
int ans[N];
int cmp(is x,is y)
{
if(x.r!=y.r)
return x.r<y.r;
return x.l<y.l;
}
int tree[N];
int lowbit(int x)
{
return x&-x;
}
void update(int x,int change)
{
while(x<=)
{
tree[x]+=change;
x+=lowbit(x);
}
}
int query(int x)
{
int sum=;
while(x)
{
sum+=tree[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
int x,y,z,i,t;
while(~scanf("%d%d",&x,&y))
{
memset(tree,,sizeof(tree));
for(i=;i<=;i++)
v[i].clear();
for(i=;i<=x;i++)
{
scanf("%d",&b[i]);
v[b[i]].push_back(i);
}
for(i=;i<=y;i++)
scanf("%d%d",&a[i].l,&a[i].r),a[i].pos=i;
sort(a+,a+y+,cmp);
int st=;
for(i=;i<=y;i++)
{
while(st<=a[i].r)
{
if(query(v[b[st]][])-query(v[b[st]][]-)==)
update(v[b[st]][],-),v[b[st]].erase(v[b[st]].begin());
update(v[b[st]][],);
st++;
}
ans[a[i].pos]=query(a[i].r)-query(a[i].l-);
}
for(i=;i<=y;i++)
printf("%d\n",ans[i]);
}
return ;
}
04-25 11:27