洛谷 P4396 [AHOI2013]作業（莫隊 + 分塊 + 根号均攤）

很顯然有一個莫隊套樹狀數組的做法， 因為樹狀數組更新和查詢的複雜度都是 log ⁡ n \log n logn，複雜度是 n m log ⁡ n n \sqrt m \log n nm

​logn

通過學習了解到分塊資料結構可以做到 O ( 1 ) O(1) O(1) 查詢， O ( n ) O(\sqrt n) O(n

​) 更新 與 O ( n ) O(\sqrt n) O(n

​) 查詢， O ( 1 ) O(1) O(1) 更新的平衡。

由于 查詢是 1 0 6 10^6 106 級别，通過分塊資料結構 和 根号平衡在莫隊中更新可以做到 O ( 1 ) O(1) O(1)，總體複雜度為 O ( m n + n m ) O(m\sqrt n + n \sqrt m) O(mn

​+nm

​) ，理論上限大約為 3 ∗ 1 0 8 3*10^8 3∗108 左右

做法是對權值分塊，維護塊内數字出現的次數和以及不同數字的個數。

詳細見代碼：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n,m,a[maxn],block,cnt[maxn];
int ans[maxn],res[maxn];
struct node {
	int id,l,r,a,b;
	node(int idi = 0,int li = 0,int ri = 0,int ai = 0,int bi = 0) {
		id = idi;
		l = li;
		r = ri;
		a = ai;
		b = bi;
	}
	bool operator < (const node &rhs) const {
		return l / block == rhs.l / block ? r < rhs.r : l < rhs.l;
	} 
}q[maxn];
struct Block {
	int siz,num,p[maxn],sum[maxn],t[maxn],tot[maxn];
	void init() {
		siz = sqrt(n);
		num = n / siz + (n % siz > 0);
		memset(p,0,sizeof p);
		memset(t,0,sizeof t);
		memset(sum,0,sizeof sum);
		memset(tot,0,sizeof tot);
	}
	void update(int pos,int v) {
		int tp = pos / siz + (pos % siz > 0);
		p[pos] += v;
		sum[tp] += v;
	}
	void modify(int pos,int v) {
		int tp = pos / siz + (pos % siz > 0);
		t[pos] += v;
		tot[tp] += v;
	}
	int ask(int l,int r) {
		int lp = l / siz + (l % siz > 0);
		int rp = r / siz + (r % siz > 0);
		int ans = 0;
		for(int i = lp + 1; i < rp; i++)
			ans += sum[i];
		if(lp == rp) {
			for(int i = l; i <= r; i++)
				ans += p[i];
		} else {
			for(int i = l; i <= lp * siz; i++)
				ans += p[i];
			for(int i = (rp - 1) * siz + 1; i <= r; i++)
				ans += p[i];
		}
		return ans;
	}
	int qry(int l,int r) {
		int lp = l / siz + (l % siz > 0);
		int rp = r / siz + (r % siz > 0);
		int ans = 0;
		for(int i = lp + 1; i < rp; i++)
			ans += tot[i];
		if(lp == rp) {
			for(int i = l; i <= r; i++)
				ans += t[i];
		} else {
			for(int i = l; i <= lp * siz; i++)
				ans += t[i];
			for(int i = (rp - 1) * siz + 1; i <= r; i++)
				ans += t[i];
		}
		return ans;
	}
}B;
int curleft,curright;
void modify(int l,int r) {
	while(curleft < l) {
		B.update(a[curleft],-1);
		cnt[a[curleft]]--;
		if(cnt[a[curleft]] == 0) B.modify(a[curleft],-1);
		curleft++;
	}
	while(curleft > l) {
		curleft--;
		cnt[a[curleft]]++;
		B.update(a[curleft],1);
		if(cnt[a[curleft]] == 1) B.modify(a[curleft],1);
	}
	
	while(curright < r) {
		curright++;
		cnt[a[curright]]++;
		B.update(a[curright],1);
		if(cnt[a[curright]] == 1) B.modify(a[curright],1);
	}
	while(curright > r) {
		cnt[a[curright]]--;
		B.update(a[curright],-1);
		if(cnt[a[curright]] == 0) B.modify(a[curright],-1);
		curright--;
	}
}
int main() {
	scanf("%d%d",&n,&m);
	B.init();
	for(int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
	}
	for(int i = 1,l,r,a,b; i <= m; i++) {
		scanf("%d%d%d%d",&l,&r,&a,&b);
		q[i] = node(i,l,r,a,b);
	}
	block = sqrt(n);
	sort(q + 1,q + m + 1);
	curleft = curright = 0;
	for(int i = 1; i <= m; i++) {
		modify(q[i].l,q[i].r);
		int j = q[i].id;
		ans[j] = B.ask(q[i].a,q[i].b); 
		res[j] = B.qry(q[i].a,q[i].b);
	}
	for(int i = 1; i <= m; i++)
		printf("%d %d\n",ans[i],res[i]);
	return 0;
}