AT1219 歴史の研究[回滚莫队学习笔记]

回滚莫队例题。

这题的意思大概是

设 \(cnt_i\) 为 l ~ r 这个区间 \(i\) 出现的次数

求\(m\) 次询问求 l~r 的 max {\(a_i\) * \(cnt_i\)}

\(n\) , \(m\) 同阶 \(1e5\)

没有强制在线？我们考虑普通的莫队？如果最大值在某一段，当你把指针移到另一段，这个答案就失效了。

所以考虑回滚莫队。

回滚莫队的做法是

按左端点所在的块排序 如果相同 按右端点排序

然后对于每个块求解。弄个右指针在块的最右边。

分类讨论一下 如果左右指针共处一个块内 直接暴力 就是根号级别的

如果不在一个块内 由于右端点是递增的 考虑移动右端点

左边的贡献直接从 q[i].l ~ 块的最右边 暴力就行了

易证复杂度：

对于整块的询问一共有 \(\sqrt n\) 个块右端点每次都是当前块的右端点 所以最多移动\(n\)的长度

对于每个询问考虑左边的端点由于按左端点排序左端点和右端点最多相差 \(\sqrt n\) 的长度

这样就可以做到 \(O(n \sqrt n)\) 了

// Isaunoya

#include<bits/stdc++.h>

using namespace std ;

using LL = long long ;

using uint = unsigned int ;

#define int long long

#define fir first

#define sec second

#define pb push_back

#define mp(x , y) make_pair(x , y)

template < typename T > inline void read(T & x) { x = 0 ; int f = 1 ; register char c = getchar() ;

  for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;

  for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c & 15) ;

  x *= f ;

}

template < typename T > inline void print(T x) {

  if(! x) { putchar('0') ; return ; }

  static int st[105] ;

  if(x < 0) putchar('-') , x = -x ;

  int tp = 0 ;

  while(x) st[++ tp] = x % 10 , x /= 10 ;

  while(tp) putchar(st[tp --] + '0') ;

}

template < typename T > inline void print(T x , char c) { print(x) ; putchar(c) ; }

template < typename T , typename ...Args > inline void read(T & x , Args & ...args) { read(x) ; read(args...) ; }

template < typename T > inline void sort( vector < T > & v) { sort(v.begin() , v.end()) ; return ; }

template < typename T > inline void unique( vector < T > & v) { sort(v) ; v.erase(unique(v.begin() , v.end()) , v.end()) ; }

template < typename T > inline void cmax(T & x , T y) { if(x < y) x = y ; return ; }

template < typename T > inline void cmin(T & x , T y) { if(x > y) x = y ; return ; }

const int N = 1e5 + 10 ;

int n , m ;

int a[N] , b[N] ;

struct node { int l , r , id ; } q[N] ;

int bl[N] ;

inline bool cmp(node x , node y) {

  if(bl[x.l] == bl[y.l]) return x.r < y.r ;

  return bl[x.l] <  bl[y.l] ;

}

int cnt[N] , cnt2[N] ;

inline int calc(int l , int r) { int ret = 0 ;

  for(register int i = l ; i <= r ; i ++) { cnt2[a[i]] = 0 ; }

  for(register int i = l ; i <= r ; i ++) { ++ cnt2[a[i]] ; cmax(ret , 1LL * (cnt2[a[i]]) * b[a[i]]) ; }

  return ret ;

} int unt ;

int ans , Ans[N] ;

inline void add(int x) {

  ++ cnt[a[x]] ;

  cmax(ans , 1LL * cnt[a[x]] * b[a[x]]) ;

} int now = 1 ;

inline void solve(int id) {

  int qr = min(id * unt , n) , pr = qr ; memset(cnt , 0 , sizeof(cnt)) ;

  ans = 0 ;

  for( ; bl[q[now].l] == id ; now ++) {

    if(bl[q[now].l] == bl[q[now].r]) { Ans[q[now].id] = calc(q[now].l , q[now].r) ; continue ; }

    while(pr < q[now].r) { add(++ pr) ; } int last = ans ;

    for(register int i = q[now].l ; i <= qr ; i ++) add(i) ;

    Ans[q[now].id] = ans ;

    for(register int i = q[now].l ; i <= qr ; i ++) -- cnt[a[i]] ;

    ans = last ;

  }

}

signed main() {

  read(n , m) ;

  for(register int i = 1 ; i <= n ; i ++) read(a[i]) , b[i] = a[i] ;

  sort(b + 1 , b + n + 1) ; int len = unique(b + 1 , b + n + 1) - b - 1 ;

  for(register int i = 1 ; i <= n ; i ++) a[i] = lower_bound(b + 1 , b + len + 1 , a[i]) - b ;

  unt = sqrt(n) ;

  for(register int i = 1 ; i <= n ; i ++) bl[i] = (i - 1) / unt + 1 ;

  for(register int i = 1 ; i <= m ; i ++) read(q[i].l , q[i].r) , q[i].id = i ;

  sort(q + 1 , q + m + 1 , cmp) ;

  for(register int i = 1 ; i <= bl[n] ; i ++) solve(i) ;

  for(register int i = 1 ; i <= m ;i ++) print(Ans[i] , '\n') ;

  return 0 ;

}

巴特西

AT1219 歴史の研究[回滚莫队学习笔记]

最新文章

热门文章