正題

題目鏈接:https://www.luogu.com.cn/problem/AT1219

---

題目大意

$n$個數字，$m$次詢問一個區間內$$t_i?i$$的最大值，$t_i$即區間內$i$的出現次數。

---

解題思路

用回滾莫隊的思想，對于在不同塊中的詢問，我們把左端點所在塊的右端點作為分界點，顯然以后所有與左端點在同一個塊中的詢問的右端點會單調上升，我們用指針維護這個答案和信息。

那在分界點左邊的部分因為不會超過$\sqrt{n}$個，所以我們直接暴力搞就好了。

時間復雜度$O(n\sqrt{n})$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std; const ll N=1e5+10; struct node{ll l,r,id; }q[N]; ll n,m,T,a[N],b[N],v[N],pr[N],c[N]; bool cmp(node x,node y){if(x.l/T==y.l/T)return x.r<y.r;return x.l<y.l; } int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i];sort(b+1,b+1+n);ll cnt=unique(b+1,b+1+n)-b-1;for(ll i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;T=sqrt(n);for(ll i=1;i<=m;i++){scanf("%lld%lld",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+1+m,cmp);q[0].l=-T;ll r=0,bf_ans=0;for(ll x=1;x<=m;x++){if(q[x].l/T==q[x].r/T){ll ans=0;for(ll i=q[x].l;i<=q[x].r;i++)v[a[i]]++,ans=max(ans,v[a[i]]*b[a[i]]);pr[q[x].id]=ans;for(ll i=q[x].l;i<=q[x].r;i++)v[a[i]]=0;q[x].l=q[x-1].l;continue;}int tail=q[x].l/T*T+T-1;if(q[x].l/T!=q[x-1].l/T){for(ll i=1;i<=cnt;i++)c[i]=0;bf_ans=0;r=tail;}while(r<q[x].r)c[a[++r]]++,bf_ans=max(bf_ans,c[a[r]]*b[a[r]]);ll ans=bf_ans;for(ll i=tail;i>=q[x].l;i--)v[a[i]]++,ans=max(ans,(c[a[i]]+v[a[i]])*b[a[i]]);for(ll i=tail;i>=q[x].l;i--)v[a[i]]=0;pr[q[x].id]=ans;}for(ll i=1;i<=m;i++)printf("%lld\n",pr[i]);return 0; }

總結

以上是生活随笔為你收集整理的AT1219-歴史の研究(历史研究)【回滚莫队】的全部內容，希望文章能夠幫你解決所遇到的問題。

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