NYOJ 600 花兒朵朵 樹狀數組

花兒朵朵

時間限制： 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//一個很大的素數，因為我數組取的是100萬，是以取了100萬以下的最大素數
using namespace std;//這裡可能存在問題，就是沒有去重，如果取餘之後有重複，這樣就不行了
                    //我想是這一題的資料出的太水了，是以蒙混過關了

int c[1000005];//全局變量數組c 用lowbit函數建立成樹狀數組

int lowbit(int x)//重要建樹、查找、連接配接函數
{
    return x&(-x);
}

void add(int x,int d)//區間修改，如果給定阿健a——b上各加d ，
{                   //需要調用兩次：add(a-1,-d);add(b,d);
    while(x>0)
    {
        c[x]+=d;x-=lowbit(x);
    }
}
int get(int x)  //擷取單點的值（查詢）
{
    int sum=0;
    while(x<1000000)//1000000是數組的最大長度，就是取餘後資料的最大範圍
    {
        sum+=c[x];x=x+lowbit(x);
    }
    return sum;
}
int main()
{
	#if(FLAG)
        freopen("in.txt", "r", stdin);
		//freopen("out.txt", "w", stdout);
	#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;//每次都對x，y進行處理之後進行運算
	        add(x-1,-1);
	        add(y,1);
	    }
	    for(i=0;i<m;i++)
	    {
	        scanf("%d",&x);
	        x=x%M;//詢問的時候做同樣的運算
	        printf("%d\n",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("%d\n",Sum(real[i]));
    }
	return 0;
}