题解：P13977 数列分块入门 2

翻了一圈发现没有

\Theta(n\sqrt{n\log n})

的做法，来发交一发题解。

首先，我们考虑分块，维护每个块的 tag 表示这个块每个数都要加上的数。

其次，每个块维护一个 vector 存下这个块内的数从小到大排序后的结果以方便查询。

发现修改散块暴力重构

\Theta(B\log B)

的，整块是

\Theta(\frac nB)

的。

查询散块枚举可以做到

\Theta(B)

，整块用 lower_bound 二分可以做到

\Theta(\frac nB\log B)

。

此时，取

B=\sqrt n

可以做到

\Theta(n\sqrt n\log{\sqrt n})

。

但我们发现，其实修改散块时可以做到

\Theta(B)

。具体的，修改一个散块时，把散块分为两部分，一部分为不修改的，一部分为修改的。发现这两部分提取出来后的相对顺序不会变，然后把这两部分归并即可。

于是可以做到

\Theta(n(B+\frac nB\log B))

，取

B=\sqrt{n\log n}

可以做到

\Theta(n\sqrt{n\log n})

。

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,m,a[N];
int b;
vector<pair<int,int>>r[N];
int g[N];
void re(int x,int ql,int qr){
	vector<pair<int,int>>o,d;
	for(int i=0,sz=r[x].size();i<sz;i++){
		int p=r[x][i].second;
		if(p>qr||p<ql)o.push_back({a[p],p});
		else d.push_back({a[p],p});
	}
	merge(o.begin(),o.end(),d.begin(),d.end(),r[x].begin());
}
void up(int ql,int qr,int v){
	if(ql/b==qr/b){
		for(int i=ql;i<=qr;i++)a[i]+=v;
		re(ql/b,ql,qr);
	}
	else{
		for(int i=ql;i<ql/b*b+b;i++)a[i]+=v;
		re(ql/b,ql,ql/b*b+b-1);
		for(int i=qr/b*b;i<=qr;i++)a[i]+=v;
		re(qr/b,qr/b*b,qr);
		for(int i=ql/b+1;i<qr/b;i++)g[i]+=v;
	}
}
int qy(int ql,int qr,int v){
	int ans=0;
	if(ql/b==qr/b){
		for(int i=ql;i<=qr;i++)ans+=(a[i]+g[ql/b]<v);
	}
	else{
		for(int i=ql;i<ql/b*b+b;i++)ans+=(a[i]+g[ql/b]<v);
		for(int i=qr/b*b;i<=qr;i++)ans+=(a[i]+g[qr/b]<v);
		for(int i=ql/b+1;i<qr/b;i++)ans+=lower_bound(r[i].begin(),r[i].end(),make_pair(v-g[i],-1))-r[i].begin();
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;b=sqrt(n*log(n));
	for(int i=0;i<n;i++)cin>>a[i],r[i/b].push_back({a[i],i});
	for(int i=0;i<=(n-1)/b;i++)sort(r[i].begin(),r[i].end());
	for(int i=1;i<=n;i++){
		int op,l,r,c;cin>>op>>l>>r>>c;
		--l,--r;
		if(op==0)up(l,r,c);
		else cout<<qy(l,r,c*c)<<'\n';
	}
	return 0;
}

题解：P13977 数列分块入门 2

文章操作

题解：P13977 数列分块入门 2

相关推荐

评论

题解：P13977 数列分块入门 2