CF840D. Destiny

Solution

發現問題只有詢問沒有修改，且要維護類似眾數的東西，瞟了一眼數據范圍$n,m\le 3e5$，果斷莫隊，一點不虛，寫到一半發現刪除不好直接維護，用$set$會多一個$log$，必然$TLE$，于是果斷回滾莫隊，維護所有數的出現次數以及出現次數最多的五個數即可。

時間復雜度：大常數 $O(n\sqrt{n})$。
$CF$實測$1600ms$，優秀！

Code

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int a[MAXN],cnt[MAXN],Ans[MAXN],mx[10],Mx[10]; struct Qnode{ int l,r,x,id; } Q[MAXN]; void add(int x) {cnt[x]++;for (int j=0;j<5;j++) if (mx[j]==x) return;int mn=0;for (int j=1;j<5;j++) if (cnt[mx[j]]<cnt[mx[mn]]) mn=j;if (cnt[mx[mn]]<cnt[x]) mx[mn]=x; } void Add(int x) {cnt[x]++;for (int j=0;j<5;j++) if (Mx[j]==x) return;int mn=0;for (int j=1;j<5;j++) if (cnt[Mx[j]]<cnt[Mx[mn]]) mn=j;if (cnt[Mx[mn]]<cnt[x]) Mx[mn]=x; } int get(int x) {int ans=INF;for (int j=0;j<5;j++)if (cnt[mx[j]]>=x) upmin(ans,mx[j]);if (ans==INF) return -1;return ans; } int Get(int x) {int ans=INF;for (int j=0;j<5;j++)if (cnt[Mx[j]]>=x) upmin(ans,Mx[j]);if (ans==INF) return -1;return ans; } signed main() {int n=read(),m=read(),sz=floor(sqrt(n));for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=m;i++) Q[i]=(Qnode){read(),read(),read(),i};sort(Q+1,Q+m+1,[&](Qnode x,Qnode y){ return ((x.l-1)/sz<(y.l-1)/sz)||((x.l-1)/sz==(y.l-1)/sz&&x.r<y.r); });Q[0].l=-sz;for (int i=1,l,r;i<=m;i++){if ((Q[i].l-1)/sz!=(Q[i-1].l-1)/sz) {for (int j=1;j<=n;j++) cnt[j]=0;for (int j=0;j<5;j++) mx[j]=0;l=((Q[i].l-1)/sz+1)*sz,r=l-1;}if ((Q[i].r-1)/sz==(Q[i].l-1)/sz){for (int j=Q[i].l;j<=Q[i].r;j++) add(a[j]);Ans[Q[i].id]=get((Q[i].r-Q[i].l+1)/Q[i].x+1);for (int j=Q[i].l;j<=Q[i].r;j++) cnt[a[j]]--;continue;}while (r<Q[i].r) r++,add(a[r]);for (int j=0;j<5;j++) Mx[j]=mx[j];for (int j=Q[i].l;j<l;j++) Add(a[j]);Ans[Q[i].id]=Get((Q[i].r-Q[i].l+1)/Q[i].x+1);for (int j=Q[i].l;j<l;j++) cnt[a[j]]--;}for (int i=1;i<=m;i++) printf("%d\n",Ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的CF840D. Destiny的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。