莫隊/se 優雅的暴力

沒有完成的暴力筆記

莫隊算法

發明者：隊爺莫濤

基于分塊的一種暴力算法， 複雜度最慢可以被卡到\(n^2\)正常情況下的複雜度大約在\(O（n\sqrt{n}）\)左右分塊的大小對複雜的影響很大其中最優分塊的大小為\(\dfrac {s}{\sqrt{m}}\) 最優複雜度為\(O（n\sqrt{m}）\)

證明

用處：維護區間資訊

具體做法

• 對求的\(l-r\)區間進行排序，根據\(l\)和\(r\)所在塊的位置，進行排序
• 對排序後的\(l-r\)的區間進行維護，觀察維護的資料具有什麼特點

注意：

• 4個\(while\)循環不能亂，根據先後關系進行确定（24中全排列，6中正确）

  莫隊的枚舉順序與區間有很大的關系

  如果先枚舉 \(l\to l', r\to r'\)就會發現\(r \to l'\)這一塊會先減一遍然後再加一遍，但是會出現一個問題\(r\to l'\)第一遍減的時候不會減到負的隻會變成 0 是以會挂掉，推薦一個枚舉的順序：

\(l--, r--, r++, l++\)對稱的比較好記

• 莫隊比較卡常，注意寫小常數

  例題

  這個就是機率問題

• 例子1 eg:3 3 4 5 6 4

  \(ans = \dfrac{2}{6} \times \dfrac{1}{5} + \dfrac{2}{6} \times \dfrac{1}{5} = \dfrac{2}{15}\)

  莫隊的過程就是

l = 1 ，r = 0 ,son = 0
l = 1 ，r = 1 ,son = 0 
l = 1 ，r = 2 ,son = 2 * ( 2 - 1 ) / 2
l = 1 ，r = 3 ,son = 2 * ( 2 - 1 ) / 2
l = 1 ，r = 4 ,son = 2 * ( 2 - 1 ) / 2
l = 1 ，r = 5 ,son = 2 * ( 2 - 1 ) / 2
l = 1 ，r = 6 ,son = 2 * ( 2 - 1 ) / 2 + 2 * (2 - 1) / 2
mo = 6 * (6 - 1) / 2
           

• 例子1 eg: 3 3 3 4 5 6 4

l = 1 ，r = 0 ,son = 0
l = 1 ，r = 1 ,son = 2 * ( 2 - 1 ) / 2
l = 1 ，r = 2 ,son = 3 * ( 3 - 1 ) / 2
l = 1 ，r = 3 ,son = 3 * ( 3 - 1 ) / 2
l = 1 ，r = 4 ,son = 3 * ( 3 - 1 ) / 2
l = 1 ，r = 5 ,son = 3 * ( 3 - 1 ) / 2
l = 1 ，r = 6 ,son = 3 * ( 3 - 1 ) / 2 + 2 * (2 - 1) / 2
mo = 7 * (7 - 1) / 2
           

過程中先删去前一個的貢獻再加上後一個的貢獻

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#define orz puts("LKP AK IOI")
#define ll long long
using namespace std;
const int N = 5e4+100;
int read(){
	int s = 0 ,f = 1; char ch = getchar();
	while(ch < '0'||ch > '9'){if(ch == '-') f = -1 ; ch = getchar();}
	while(ch >= '0'&&ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
	return s * f;
}
ll sqrtn , l = -1, r = 0, ans;
ll son[N], mo[N];
struct node {
	int l, r, id;
	bool operator < (const node &x) const {
		if( l / sqrtn != x.l / sqrtn) return l < x.l;
		if((l/sqrtn) & 1) return r < x.r;
		return r > x.r;  
	}
}wa[N];
int cs[N],c[N];
ll ANS(ll  x) {
	return x < 2 ? 0: x * (x - 1) ;	
}
void del(int pos) {
	ll temp = --cs[c[pos]];
	ans -= ANS(temp+1);	ans += ANS(temp);
} 
void add(int pos) {
	ll temp = ++cs[c[pos]];
	ans -= ANS(temp-1);	ans += ANS(temp); 
}
ll gcd(ll a,ll b) {
	return b == 0 ? a : gcd(b, a%b); 
} 
bool cmp(node a,node b) {
	if(a.l/sqrtn == b.l/sqrtn)	return a.r < b.r;
	return a.l < b.l; 
}
int main(){
	int n = read() ,m = read()	;
	for(int i = 1 ; i <= n ; i++) 	c[i] = read();
	for(int i = 1 ; i <= m ;i++) 	wa[i].l = read() , wa[i].r = read() , wa[i].id = i; 
	sqrtn = sqrt(0.5+n );
	sort(wa+1,wa+1+m);
	//sort(wa+1 , wa+1+m, cmp); 
	//orz;
	for(int i = 1 ; i <= m ;i++) {
		while (l < wa[i].l) del(l),l++;
		while (l > wa[i].l) l--,add(l);
		while (r < wa[i].r) r++,add(r);
		while (r > wa[i].r) del(r),r--;
		son[wa[i].id] = ans;
		mo[wa[i].id] = ANS(r-l+1);
	}
	for(int i = 1; i <= m ;i++) {
		if(son[i] == 0) {
			cout<<"0/1\n";
			continue;
		}
		ll temp = gcd(son[i],mo[i]);
		printf("%lld/%lld\n",son[i]/temp,mo[i]/temp);
	}
	return 0;
}
           

upd:2021.3.13

今天突然發現自己記得莫隊修改順序不大對勁（好怪啊

突然感覺

--L
  ++R
  L--
  R++
           

打着也挺順手的

Future never has to do with past time,but present time dose.