AT1219 歴史の研究（回滚莫队）

题目描述

$I O I国历史研究的第一人——$

日记中记录了连续

事件有种类之分。第

选择日记中连续的一些天作为分析的时间段

事件种类t的重要度为t*(这段时间内重要度为t的事件数)

计算出所有事件种类的重要度，输出其中的最大值现在你被要求制作一个帮助教授分析的程序，每次给出分析的区间，你需要输出重要度的最大值。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn=100005;
int n,m;
ll aa[maxn],a[maxn],b[maxn];//原序列，离散化序列，桶 
int size,pos[maxn];
ll ans[maxn],nowans;
struct question{
    int l,r,id;
}q[maxn];

template<class T>inline void read(T &x){
    x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}

ll max(ll x,ll y){return x>y ? x : y ;}

bool cmp(question a,question b){
    if(pos[a.l]==pos[b.l]) return a.r<b.r;
    return pos[a.l]<pos[b.l];
}

ll cx[maxn];//暴力使用 

ll nice(int l,int r){
    for(int i=l;i<=r;i++) cx[a[i]]=0;
    ll ret=0;
    for(int i=l;i<=r;i++){
        cx[a[i]]++;
        ret=max(ret,aa[a[i]]*cx[a[i]]);
    }
    return ret;
}

void add(int x){
    b[a[x]]++;
    nowans=max(nowans,aa[a[x]]*b[a[x]]);
}

void del(int x){
    b[a[x]]--;
}

int mo(int i,int id){
    int R=min(n,id*size),nowl=R,nowr=nowl-1;
    nowans=0;
    memset(b,0,sizeof(b));
    for(;pos[q[i].l]==id;i++){
        if(pos[q[i].l]==pos[q[i].r]) {ans[q[i].id]=nice(q[i].l,q[i].r);continue;}
        while(nowr<q[i].r) add(++nowr);
        ll ret=nowans;
        while(nowl>q[i].l) add(--nowl);
        ans[q[i].id]=nowans;
        while(nowl<R) del(nowl++);
        nowans=ret;
    }
    return i;
}

int main(){
    read(n);read(m);
    size=sqrt(n+0.5);
    for(int i=1;i<=n;i++){read(aa[i]);a[i]=aa[i];pos[i]=(i-1)/size+1;}
    sort(aa+1,aa+n+1);
    int tot=unique(aa+1,aa+n+1)-aa-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(aa+1,aa+tot+1,a[i])-aa;
    for(int i=1;i<=m;i++){read(q[i].l);read(q[i].r);q[i].id=i;}
    sort(q+1,q+m+1,cmp);
    for(int i=1,id=1;id<=pos[n];id++)
     i=mo(i,id);
    for(int i=1;i<=m;i++) printf("%lld
",ans[i]);
}

View Code

AT1219 歴史の研究（回滚莫队）

题目描述

题解