题目链接:HDU5199
【分析】离散化一下所有高度,统计每个高度有饥渴树,然后按查询输出并归零就好了。也是水题,看数据量有10^6就手写了一个hash,终测竟然只跑了405ms
【AC CODE】1045ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <map> //#include <unordered_map> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 1000000+10, MOD = 1000007; struct HASH{ int head[MOD], next[MAXN], sum[MAXN], cnt, node[MAXN], num[MAXN]; void clear(){ cnt = 0; clc(head,-1); clc(sum,0); } int hash(int s){ return s%MOD; } void insert(int s, int v){ int id = hash(s); int u = head[id]; while(~u){ if(s == node[u]) { sum[u]++; return; } u = next[u]; } sum[cnt] = 1; num[cnt] = v; node[cnt] = s; next[cnt] = head[id]; head[id] = cnt++; } int find(int s){ int id = hash(s); int u = head[id]; while(~u){ if(node[u] == s) return num[u]; u = next[u]; } return -1; } }vis; int sum[MAXN], cnt; int in()//快速读入 { int ch,ans; while((ch = getchar()) < '0' || '9' < ch); ans = ch-'0'; while((ch = getchar()) >= '0' && '9' >= ch) ans = (ans<<3)+(ans<<1)+ch-'0'; return ans; } int get_id(int x) { int ans = vis.find(x); if(-1 == ans) { vis.insert(x,cnt++); return cnt-1; } return ans; } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n,m; while(~scanf("%d %d%*c", &n, &m)) { clc(sum,0); vis.clear(); cnt = 0; rep(i,0,n) sum[get_id(in())]++; rep(i,0,m) { int h = get_id(in()); printf("%d\n", sum[h]); sum[h] = 0; } } return 0; }