题解：P8146 [JRKSJ R4] risrqnis

对于

m=1

的情况，任意发现每个

a_i

只会被加入集合一次。上个 ODT 考虑新增数，随便做做即可，但是一定要

\mathcal{O}(q \log n)

不然过不了。

对于一般情况，考虑对集合操作次数阈值分治，设阈值为

B

。

对于操作次数 $>B$ 的集合：

这种集合至多存在 $\mathcal{O}(\dfrac{q}{B})$ 个。考虑使用与 $m=1$ 类似的做法。

每个集合最多加入 $n$ 个不同 $a_i$ ，则 $a_i$ 被加入集合总共有 $\mathcal{O}(\dfrac{nq}{B})$ 次。

使用 $\mathcal{O}(1)-\mathcal{O}(\sqrt{n})$ 的分块即可，这部分复杂度为 $\mathcal{O}(\dfrac{nq}{B}+q\sqrt{n})$ 。
对于操作次数 $\le B$ 的集合：

插入区间的次数是 $\mathcal{O}(B)$ 的，则所有被加入集合的数，在数轴上构成了 $\mathcal{O}(B)$ 个区间。

查询时，枚举这些区间 $[L,R]$ 。

就变为了 $\mathcal{O}(B)$ 次查询有几个位置满足 $l \le i \le r,L \le a_i \le R$ 。

离线后二维数点，使用 $\mathcal{O}(\sqrt{n})-\mathcal{O}(1)$ 的分块维护即可。

这部分复杂度为 $\mathcal{O}(n\sqrt{n}+qB)$ 。

但是空间是 $\mathcal{O}(nB)$ 的，因为值域区间加入后不会删掉，可以直接维护每个区间的插入时间然后扫描时枚举区间即可将空间变为线性。

认为

n,q

同阶。

取

B=\mathcal{O}(\sqrt{n})

，时间复杂度为

\mathcal{O}(n\sqrt{n})

。空间线性。

然后拿下了目前的最优解加最短解。

CPP

#include<bits/stdc++.h>
#define IT set<node>::iterator
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
	register int x=0,s=gc;while(!isdigit(s))s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
	return x;
}
const int N=1000005,B=800,blk=300,S=N/blk+5;
int n,m,q,tot,cnt,a[N],p[N],P[N],bl[N],ans[N],L[S],R[S];bool fl[N];
inline bool cmp(int x,int y){return a[x]<a[y];}
struct qu{
	int op,l,r,k,id;
	inline bool operator <(const qu &o)const{return k==o.k?id<o.id:k<o.k;}
}c[N];vector<qu> e;vector<pair<int,int> > nw,h[N];
struct gr{int d,k,id;};vector<gr> f[N];
struct ODT{
	struct node{
		mutable int l,r,w;
		inline bool operator <(const node &o)const{return l<o.l;}
	};set<node> s;
	inline IT split(int p){
		IT it=s.lower_bound({p,0,0});
		if(it!=s.end()&&it->l==p)return it;
		--it;int r=it->r;it->r=p-1;
		return s.insert({p,r,it->w}).first;
	}
	inline void assign(int l,int r){
		IT itr=split(r+1),itl=split(l);
		for(IT i=itl;i!=itr;++i)
			if(!i->w)nw.push_back({i->l,i->r});
		s.erase(itl,itr),s.insert({l,r,1});
	}
	inline void clr(){s.clear(),s.insert({0,(int)2e9,0});}
}T;
struct BIT{
	int s[N];
	inline void U(int x){for(;x<=n;x+=x&-x)++s[x];}
	inline int Q(int r){int res=0;for(;r;r^=r&-r)res+=s[r];return res;}
	inline int Q(int l,int r){return Q(r)-Q(l-1);}
}E;
struct B1{
	int z[S],s[N];
	inline void clr(){memset(z,0,sizeof(z)),memset(s,0,sizeof(s));}
	inline void U(int x){++z[bl[x]],++s[x];}
	inline int Q(int l,int r){
		if(bl[l]==bl[r]){int res=0;for(int i=l;i<=r;++i)res+=s[i];return res;}
		int res=Q(l,R[bl[l]])+Q(L[bl[r]],r);for(int i=bl[l]+1;i<bl[r];++i)res+=z[i];
		return res;
	}
}E1;
struct B2{
	int z[S],s[N];
	inline void U(int x){
		for(int i=x;i<=R[bl[x]];++i)++s[i];
		for(int i=bl[x]+1;i<=tot;++i)++z[i];
	}
	inline int Q(int r){return r?z[bl[r]]+s[r]:0;}
	inline int Q(int l,int r){return l<=r?Q(r)-Q(l-1):0;}
}E2;
inline void U(int l,int r){
	l=lower_bound(p+1,p+n+1,l)-p,r=upper_bound(p+1,p+n+1,r)-p-1;
	for(int i=l;i<=r;++i)E1.U(P[i]);
}
inline void u(int l,int r){
	l=lower_bound(p+1,p+n+1,l)-p,r=upper_bound(p+1,p+n+1,r)-p-1;
	for(int i=l;i<=r;++i)E.U(P[i]);
}
inline void sol(){
	T.clr();
	for(int i=1,op,l,r;i<=q;++i){
		op=rd,l=rd,r=rd,rd;
		if(op==1){
			T.assign(l,r);
			for(auto [vl,vr]:nw)u(vl,vr);
			nw.clear();
		}else cout<<E.Q(l,r)<<'\n';
	}
}
inline void sol1(){
	T.clr(),E1.clr();
	for(auto [op,l,r,k,id]:e)
		if(op==1){
			T.assign(l,r);
			for(auto [vl,vr]:nw)U(vl,vr);
			nw.clear();
		}else ans[id]=E1.Q(l,r);
	e.clear();
}
inline void sol2(int k){
	T.clr(),k=++cnt;
	for(auto [op,l,r,k,id]:e)
		if(op==1)T.assign(l,r);
		else f[r].push_back({nw.size(),cnt,id}),
			f[l-1].push_back({nw.size(),cnt,-id});
	for(auto &[l,r]:nw)l=lower_bound(p+1,p+n+1,l)-p,r=upper_bound(p+1,p+n+1,r)-p-1;
	e.clear(),h[k]=nw,nw.clear();
}
signed main(){
	n=rd,q=rd,m=rd,tot=(n-1)/blk+1;
	for(int i=1;i<=n;p[P[i]=i]=a[i],bl[i]=(i-1)/blk+1,++i)a[i]=rd;	
	sort(p+1,p+n+1),sort(P+1,P+n+1,cmp);if(m==1)return sol(),0;
	for(int i=1;i<=tot;++i)L[i]=R[i-1]+1,R[i]=i*blk;R[tot]=n;
	for(int i=1;i<=q;fl[i]=(c[i].op==2),++i)c[i]={rd,rd,rd,rd,i};sort(c+1,c+q+1);
	for(int l=1,r=1;l<=q;l=r){
		while(c[l].k==c[r].k)e.push_back(c[r]),++r;
		e.size()>B?sol1():sol2(c[l].k);
	}
	for(int i=1;i<=n;++i){
		E2.U(lower_bound(p+1,p+n+1,a[i])-p);
		for(auto [d,k,id]:f[i]){
			int res=0,b=0;
			for(auto [l,r]:h[k])
				if((++b)<=d)res+=E2.Q(l,r);
				else break;
			if(id<0)ans[-id]-=res;else ans[id]+=res;
		}
	}
	for(int i=1;i<=q;++i)if(fl[i])cout<<ans[i]<<'\n';
	return 0;
}

题解：P8146 [JRKSJ R4] risrqnis

文章操作

相关推荐

评论

题解：P8146 [JRKSJ R4] risrqnis