【YNOI2016】【BZOJ4939】【LOJ6199】【洛谷P4688】掉進兔子洞（莫隊）（bitset）

BZOJ傳送門

LOJ傳送門

洛谷傳送門

解析：

顯然這個玩意不是什麼鬼畜資料結構能夠維護的，我們考慮暴力。

顯然可以用離散化+bitset處理出每個區間的數出現情況。

由于一個數出現多次我們需要特殊處理，離散化後記錄一個cnt，然後每次改變一個數的存在情況就在cnt+pos處将位取反。

顯然這個過程可以用莫隊來實作。

然後需要注意的就是，由于詢問的存儲空間開不下那麼多bitset（也不可能開下），我們可以講詢問多分幾次處理，我選擇分5次。

代碼：

#include<bits/stdc++.h>
#define ll long long
#define re register
#define gc getchar
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<20|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	inline int getint(){
		re char c;
		while(!isdigit(c=gc()));re int num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
}
using namespace IO;

cs int N=1e5+10;
int n;

int a[N],b[N],cnt[N],Ans[N/3];
std::bitset<N> s[N/3],R;

inline void ins(int val){
	R[val+cnt[val]]=1;
	++cnt[val];
}

inline void del(int val){
	--cnt[val];
	R[val+cnt[val]]=0;
}

int l,r;

int bsiz;
int block[N];
struct Query{
	int l,r,id;
	friend bool operator<(cs Query &a,cs Query &b){
		return block[a.l]==block[b.l]?((block[a.l]&1)?(a.r>b.r):(a.r<b.r)):block[a.l]<block[b.l];
	}
}q[N];
int qcnt;

inline void solve(int m){
	qcnt=0;
	for(int re i=0;i<m;++i){
		s[i].set();Ans[i]=0;
		q[qcnt].l=getint()-1,q[qcnt].r=getint()-1,q[qcnt].id=i;Ans[i]+=q[qcnt].r-q[qcnt].l+1;++qcnt;
		q[qcnt].l=getint()-1,q[qcnt].r=getint()-1,q[qcnt].id=i;Ans[i]+=q[qcnt].r-q[qcnt].l+1;++qcnt;
		q[qcnt].l=getint()-1,q[qcnt].r=getint()-1,q[qcnt].id=i;Ans[i]+=q[qcnt].r-q[qcnt].l+1;++qcnt;
	}
	std::sort(q,q+qcnt);
	for(int re i=0;i<qcnt;++i){
		while(q[i].l<l)ins(a[--l]);
		while(q[i].r>r)ins(a[++r]);
		while(q[i].l>l)del(a[l++]);
		while(q[i].r<r)del(a[r--]);
		s[q[i].id]&=R;
	}
	for(int re i=0;i<m;++i)std::cout<<Ans[i]-s[i].count()*3<<"\n";
}

signed main(){
	l=0,r=-1;
	std::ios::sync_with_stdio(false);
	n=getint();int m=getint();
	bsiz=std::max(1.,sqrt((double)n*n/m));
	for(int re i=0;i<n;++i)block[i]=i/bsiz,a[i]=b[i]=getint();
	std::sort(b,b+n);
	for(int re i=0;i<n;++i)a[i]=std::lower_bound(b,b+n,a[i])-b;
	solve(m/3);
	solve((m+1)/3);
	solve((m+2)/3);
	return 0;
}