• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

AT1219 / bzoj4241 历史研究

开发技术 开发技术 3小时前 1次浏览

Description

给定长度为 (n) 的序列 (a)(m) 次询问,求:

[max_{iin[l,r]}cnt[a_i]times a_i
]

即带权众数。

(1le n,mleq 10^5,1le a_i le 10^9)

Solution

前置芝士:莫队(不会的可以戳这里)

我们考虑正常莫队的操作,可以发现加入一个数很舒服,但是删除操作就很……

所以我们考虑不删除,只加入。

接下来的内容比较抽象,建议画个图理解一下:

首先我们仍然将序列分成 (frac n {sqrt m}) 段,对于每段的询问,我们分别处理。

首先我们先将莫队的左端点 (L) 定位到该块的右端点 (+1) 的位置,右端点 (R) 定位到该块右端点的位置。

每段的询问无非分两种情况:

  1. ([l,r]) 在同一段内,此时我们直接暴力求答案,复杂度为块长。

  2. ([l,r]) 不在同一段内,我们先将 (R) 移动到 (r),记录下此时的答案 (A),然后将 (L) 移动到 (l),此时的答案就是真正的答案。接着把 (L) 定为该块的右端点 (+1) 的位置,然后我们把 (L) 左移带来的影响去除掉。就得出了答案,且删除操作对维护答案没有影响!由于块内右端点递增,所以复杂度可以保证。

Code


constexpr int N = 1e5 + 10;
ll data[N],ans,Ans[N];
int n,m,a[N],cnt[N],bl[N],siz,tot,l,r,R;
struct Q{int l,r,id;}q[N];
inline int pos(const int x) {return (x-1)/siz + 1;}
inline void add(const int x) {++cnt[a[x]],ans = max(1ll*cnt[a[x]]*data[a[x]],ans);}
inline void del(const int x) {--cnt[a[x]];}
inline void Clear(const int x) {
    ans = 0,r = R = min(x*siz,n),l = r + 1;
    memset(cnt,0,sizeof cnt);
} //初始左右端点
inline ll Calc(const int l,const int r) {
    static int C[N];
   // std::cout <<"here "<< l << "  " << r << 'n';
    ll res = 0;
    for(int i = l;i <= r;++i) C[a[i]] = 0;
    for(int i = l;i <= r;++i) ++C[a[i]],res = max(res,1ll*C[a[i]]*data[a[i]]);
    return res;
}//同一块内爆算
inline void Init() {
    read(n,m),siz = sqrt(n),tot = pos(n);
    for(int i = 1;i <= n;++i) read(a[i]),data[i] = a[i],bl[i] = pos(i);
    std::sort(data+1,data+1+n);
    const int len = std::unique(data + 1,data + 1 + n) - data - 1;
    for(int i = 1;i <= n;++i) a[i] = std::lower_bound(data+1,data+1+len,a[i]) - data ;
    for(int i = 1;i <= m;++i)  read(q[i].l,q[i].r),q[i].id = i;
//    std::cout << "data[39] = " << data[a[39]] << 'n';
    std::sort(q + 1,q + 1 + m,[](Q a,Q b) {return bl[a.l]^bl[b.l] ? a.l < b.l : a.r < b.r;});
} //初始化
inline void Solve() {
    for(int i = 1,j = 1;i <= tot;++i) {
        Clear(i);ll tmp;
        for(;bl[q[j].l] == i;++j) {
            if(bl[q[j].r] == i) {
                Ans[q[j].id] =  Calc(q[j].l,q[j].r);
                continue;
            }//在同一块内
            while(r < q[j].r) add(++r);//先加入右端点
            tmp = ans;
            while(l > q[j].l) add(--l);//在加入左端点
            Ans[q[j].id] = ans;
            while(l <= R) del(l++);//去除影响
            ans = tmp;
        }
    }
}
int main(int argc,const char **argv) {
    Init(),Solve();
    for(int i = 1;i <= m;++i) print('n',Ans[i]);
    return STD::flush(),0;
}

程序员灯塔
转载请注明原文链接:AT1219 / bzoj4241 历史研究
喜欢 (0)