洛谷P2251 【质量检测】

时间:2024-09-07 10:07:44

无意中刷st表题看到的题目(抄模板),一看到题目,,,没想用st表,直接莫队?????跑起来也不是特别慢。。。

这里用flag数组记录出现次数,set维护最小值,用的时候直接取头部。

代码也很短

#include<bits/stdc++.h>
#define swap(a,b) {a^=b;b^=a;a^=b}
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define PII pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 1;
int n, m, mi = INF,flag[1000001], a[1000001];;
set<int>val;
int main()
{
scanf("%d%d", &n, &m);
rep(i, 1, n)scanf("%d", &a[i]);
int l = 1, r = 0;
int ll=1,rr=m;
rep(i, 0, n - m)
{
while(l < ll){flag[a[l]]--;if(!flag[a[l]])val.erase(a[l]); mi = *val.begin();++l;}
while(r < rr){++r;flag[a[r]]++;if(flag[a[r]] == 1)val.insert(a[r]);mi = *val.begin();}
cout << mi << endl;
ll++,rr++;
}
return 0;
}