花儿朵朵
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 5
描述 春天到了，花儿朵朵盛开，hrdv是一座大花园的主人，在他的花园里种着许多种鲜花，每当这个时候，就会有一大群游客来他的花园欣赏漂亮的花朵，游客们总是会询问，某个时间有多少种花儿同时在盛开着？hrdv虽然知道每种花儿的开花时间段，但是他不能很快的答出游客的问题，你能编写一个程序帮助他吗？ 输入 第一行有个整数t,表示有t组测试数据，每组测试数据第一行为两个整数n,m(0<n<100000，0<m<100000);随后有n行，每一行有两个整数x,y(0<x<y<1000000000)，表示这一种花的盛开时间是从x到y；随后有m行，每行有一个整数，代表游客询问的时间。 输出 对于每次游客的询问，输出一个整数在单独的一行，表示这个时间盛开的花有多少种。 样例输入2 1 1 5 10 4 2 3 1 4 4 8 1 4 6 样例输出
0 1 2 1 和“士兵杀敌二”相像， 但是数据范围太大了，不能直接开数组，用离散化，或者哈希 数据有点水，我直接取余就水过了
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <map>
#define FLAG 0
#define M 999983
using namespace std;
int c[1000005];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int d)
{
while(x>0)
{
c[x]+=d;x-=lowbit(x);
}
}
int get(int x)
{
int sum=0;
while(x<1000000)
{
sum+=c[x];x=x+lowbit(x);
}
return sum;
}
int main()
{
#if(FLAG)
freopen("in.txt", "r", stdin);
#endif
int n;
int T,m,i,j,x,y;
scanf("%d",&T);
while(T--)
{
memset(c,0,sizeof(c));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
x=x%M;
y=y%M;
add(x-1,-1);
add(y,1);
}
for(i=0;i<m;i++)
{
scanf("%d",&x);
x=x%M;
printf("%dn",get(x));
}
}
return 0;
}
如果数据卡一点估肯定不过，还是离散化+去重的保险
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lowbit(a) a&-a
#define MaxN 300005
int m[MaxN], real[MaxN], N;
typedef struct
{
int val, pos;
}S;
S mm[MaxN];
bool cmp(S a, S b)
{
if(a.val==b.val) return a.pos>b.pos;
return a.val<b.val;
}
void Add(int i, int num)
{
while(i<=N)
{
m[i]+=num;
i+=lowbit(i);
}
}
int Sum(int i)
{
int res=0;
while(i>0)
{
res+=m[i];
i-=lowbit(i);
}
return res;
}
int main()
{
int T, temp, k, n;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
N=2*n+k;
memset(m,0,sizeof(m));
for(int i=1;i<=N;i++)
{
scanf("%d",&temp);
mm[i].pos=i;
mm[i].val=temp;
}
sort(mm+1,mm+N+1,cmp);
int x=0;
for(int i=1;i<=N;i++)
{
if( mm[i].val != mm[i-1].val)
real[mm[i].pos]=++x;
else
real[mm[i].pos]=x;
}
for(int i=1;i<=2*n;i+=2)
{
Add(real[i],1);
Add(real[i+1]+1,-1);
}
for(int i=2*n+1;i<=N;i++)
printf("%dn",Sum(real[i]));
}
return 0;
}
