題解 AT1219 【歴史の研究】

莫隊

簡單分析：題面含有IOI（驚），可知此題是IOI（數字三角形）難度（逃）。

思路：復原莫隊

當然很多人都是抱着學復原莫隊的目标來看這道題的，是以這裡介紹一下復原莫隊。

1、按莫隊的思路講詢問排序。

2、查詢時枚舉每個區間，我們需要保證右端點是保持單調遞增的，同時左端點每次在一個塊中移動，以此來計算每個詢問的值。

3、每一次到下一個塊就講左端點移回右端點，移的過程不需要再像莫隊一樣一個個移，隻需要将莫隊中改變的資料清0，然後将右端點指派到左端點就可以了。

是以其實這道題是復原莫隊闆子題。

代碼

#include<stdio.h>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
struct kkk{
    int x,y,id,flag,ans;
}a[1000001];
struct ggg{
    int a,b,p;
}a1[1000001];
int block,blo[1000001],v[1000001],vis[1000001],cnt[1000001],sum[1000001],aa[1000001];
int Vis[1000001],maxx,maxy,pos;
int n,C,m,l,r;
bool cmp1(ggg a,ggg b){
    return a.a<b.a||(a.a==b.a&&a.p<b.p);
}
bool comp(kkk a,kkk b){
    return a.id<b.id;
}
bool cmp(kkk a,kkk b){
    if(blo[a.x]!=blo[b.x])return a.x<b.x;
    return a.y<b.y;
}
void add(int x){
    vis[v[x]]++;maxx=max(maxx,vis[v[x]]*aa[x]);
}
void re(int x){vis[v[x]]--;}
int check(int l,int r){maxy=0;
    for(int i=l;i<=r;i++)Vis[v[i]]=0;
    for(int i=l;i<=r;i++){
        Vis[v[i]]++;
        maxy=max(maxy,Vis[v[i]]*aa[i]);
    }
    return maxy;
}
int Mo(int pos,int bl){
    maxx=0;int last=0,i=pos;
    for(int j=1;j<=n;j++)vis[j]=0;
    int L=min(block*bl,n);
    int l=L+1,r=L;
    for(;blo[a[i].x]==bl;i++){
        if(blo[a[i].x]==blo[a[i].y]){a[i].ans=check(a[i].x,a[i].y);continue;}
        while(r<a[i].y){add(++r);}
        last=maxx;
        while(l>a[i].x){add(--l);}
        a[i].ans=maxx;
        while(l<L+1)re(l++);
        maxx=last;
    }
    return i;
}
signed main(){
    int num;
    scanf("%lld%lld",&n,&m);block=sqrt(n);
    //離散化
    for(int i=1;i<=n;i++){scanf("%lld",&a1[i].a);aa[i]=a1[i].a;a1[i].p=i,blo[i]=(i-1)/block+1;num=blo[i];}
    sort(a1+1,a1+n+1,cmp1);
    for(int i=1,j=0;i<=n;i++)
    {
        if(i==1||a1[i].a!=a1[i-1].a)j++;
        v[a1[i].p]=j;
    }
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&a[i].x,&a[i].y);
        a[i].id=i;
    }
    pos=1;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=num;i++){
    	pos=Mo(pos,i);
    }
    sort(a+1,a+m+1,comp);
    for(int i=1;i<=m;i++){
        printf("%lld\n",a[i].ans);
    }
    return 0;
}
           

點贊嗷 ~ \ QwQ / *