Solution

T1 出现次数

原题链接

4102: 出现次数

简要思路

利用类似前缀和的 “后缀和” 来记录下每个数后面有几个未重复出现的数，定义一个 \(f\) 数组来判断是不是第一次出现（实现去重）。

完整代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int MAXN=1e5+5;

int n,q;
int f[MAXN];//判断是否是第一次出现
int hzh[MAXN];//后缀和
int a[MAXN];

signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	
	for(int i=n;i>=1;i--){//倒序遍历
		if(f[a[i]]==0){//如果是第一次出现
			hzh[i]=hzh[i+1]+1;
			f[a[i]]=1;//标记已经出现
		}
		else{
			hzh[i]=hzh[i+1];
		}
	}
	
	while(q--){
		int x;
		cin>>x;
		cout<<hzh[x]<<endl;//直接输出就行
	}
	
	return 0;
}

T2 组模拟赛

原题链接

4103: 组模拟赛

处理出每个操作来看能刷到什么高度（也就是 \(K\) 个数的最小值），ST 表或单调队列。
看一个柱子的最大高度是经过该柱子的所有区间的最大值。
用贪心，在保证 \(1~i\) 已经到达了最大高度的前提下，让后面的柱子经可能得高。
如果未到达最大高度，我们就要进行多一次操作，但是要保证对后边的柱子影响越多。
在高度最大的条件下位置最右的区间。
记录延伸到了哪，高度是多少。
\(a_{i+1}=h,i+1<p\)，如果不满足就向后遍历，如果不符合就让答案加一并增加一个区间