洛谷P10288 [GESP样题 八级] 区间

原题

题目描述

小杨有一个长度为 \(n\) 的正整数序列 \(A\)。

小杨有 \(q\) 次询问。第 \(i\) 次（\(1\le i\le q\)）询问时，小杨会给出 \(l_i,r_i,x_i\)，请你求出 \(x_i\) 在 \(A_{l_i}, A_{l_i+1}, \dots A_{r_i}\) 中出现的次数。

输入格式

第一行包含一个正整数 \(T\)，表示数据组数。

对于每组数据：第一行包含一个正整数 \(n\)，表示序列 \(A\) 的长度。
第二行包含 \(n\) 个正整数 \(A_1,A_2,\dots,A_n\)，表示序列 \(A\)。
第三行包含一个正整数 \(q\)，表示询问次数。接下来 \(q\) 行，每行三个正整数 \(l_i,r_i,x_i\)，表示一组询问。

输出格式

对于每组数据，输出 \(q\) 行。第 \(i\) 行（\(1\le i\le q\)）输出一个非负整数，表示第 \(i\) 次询问的答案。

输入输出样例 #1

输入 #1

2
5
7 4 6 1 1
2
1 2 3
1 5 1
5
1 2 3 4 5
2
5 5 3
1 4 3

输出 #1

0
2
0
1

说明/提示

子任务	分值	\(n\)	\(q\)	\(\max A_i\)
\(1\)	\(30\)	\(\le 100\)	\(\le 100\)	\(\le 10\)
\(2\)	\(30\)	\(\le 10^5\)	\(\le 10^5\)	\(\le 10^5\)
\(3\)	\(40\)	\(\le 10^5\)	\(\le 10^5\)	\(\le 10^9\)

对于全部数据，保证有 \(1 \leq T\le 5\)，\(1 \le n,q\le 10^5\)，\(1 \le A_i\le 10^9\)。

解释

这道题首先就是可以通过暴力打到30pts: 统计x的出现次数。

代码来自无名之雾

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
inline void write(int x){if(x==0){putchar('0');return;}int len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}
int a[100005];
signed main(){ int t=read();while(t--){ int n=read();for(int i=1;i<=n;i++)a[i]=read();int q=read();while(q--){int l=read(),r=read(),x=read();int cnt=0;for(int i=l;i<=r;i++){if(a[i]==x)cnt++;}cout<<cnt<<"\n";}} return 0;
}

然而，我们要的是能够AC的完整代码。这里可以采取一个类似于前缀和的策略：
可以建这样的一个结构

{{1: 1}, {1:1, 2:1}, {1:1, 2:2}} // {1, 2, 2}

然而，这样会MLE。
那么我们为何不把umap省略成单个数字呢？
直接在a[i]存储当前数组出现的次数，然后再用一个umap<int, vector<int>>存储每个数字对应的位置——直接在区间末尾找到对应的数字位置，然后减去区间开始前的数字位置：

#include<bits/stdc++.h>
#define umap unordered_map
using namespace std;constexpr int maxn=1e5+5;
int T, n, q;
int a[maxn]; 
umap<int, vector<int>> mp; int search(int from, int x) {for(int i=mp[x].size()-1;i>=0;i--) {if(mp[x][i]<=from) return a[mp[x][i]];}return 0;
}signed main() {scanf("%d",&T);while(T--) {scanf("%d",&n);umap<int, int> store;for(int i=1;i<=n;i++) {int x;scanf("%d",&x);(store.count(x))?(store[x]++):(store[x]=1);a[i] = store[x];mp[x].push_back(i);}scanf("%d",&q);while(q--) {int l, r, x;scanf("%d%d%d",&l,&r,&x);printf("%d\n",search(r, x)-search(l-1, x));}mp.clear();}return 0;	
}

AC快乐！