[COCI 2010/2011 #7] UPIT

admin LV 10 SU @ 2026-4-28 16:02:26

分块。

将不同操作分开分析，每个操作都是分块的一个经典应用。

操作一：区间赋值。
- 对整块打赋值标记，散块暴力处理。
操作二：区间加等差数列。
- 考虑到相邻位置增量差值相同，考虑差分，对整块打两个标记，分别表示当前块第一个元素应该增加的数和等差数列的公差。第一个标记也相当于是等差数列的首项。散块暴力处理。
- 等差数列的懒标记也可以累加。
操作三：单点插入。
- 使用 vector 的插入操作处理。由于这个操作的时间复杂度是 $O(n)$ 的，所以需要使用定期重构来保证时间复杂度。
- 具体的，当一个块的大小超过某个范围时，就需要将这个块拆分。为方便实现，直接将整个序列重新分块。
- 因为每个 vector 的大小不同且不断地在更新，所以不能用数组记录每个点对应的块，而是在需要时重新找到对应的块和块内的对应位置。
操作四：区间求和。
- 维护整块的块内元素总和，散块暴力处理。
时间复杂度 $O(n\sqrt n)$ 。
代码细节还是很多的，下面总结一些容易出错的点。
- 空间需要开两倍。
- vector 的下标是从 0 开始的，如果嫌不舒服也可以在最初重构的时候在下标 0 的位置插入一个占位置的数。
- 赋值标记需要初始化为 -1。虽然实测测试点中并没有赋值为 0 的操作，赋值为 0 也可以通过。
- 重构、修改散块、查询散块操作之前都需要先处理对应块的懒标记。
- 赋值操作会覆盖加法操作，整块打赋值操作标记的时候需要将加等差数列的懒标记清空。
- 在单点插入时也需要更新块内元素总和。

参考代码如下。

#include <bits/stdc++.h> //分块 
using namespace std;

namespace Cherry {
	const int N=2e5+10;
	int n,q,B,cnt;
	long long a[N],sum[N],cov[N],al[N],ad[N];
	vector<long long> p[N];
	
	pair<int,int> get_block(int x) { //找到x对应的块和块内位置 
		int cur=1;
		while(cur<=cnt&&(int)p[cur].size()<x) x-=p[cur++].size();
		return make_pair(cur,x-1); //注意vector从0开始 
	}
	void reset(int x) { //处理块内的tag 
		if(cov[x]!=-1) {
			for(int i=0;i<(int)p[x].size();i++) p[x][i]=cov[x];
			cov[x]=-1;
		}
		if(al[x]||ad[x]) {
			for(int i=0;i<(int)p[x].size();i++) p[x][i]+=al[x]+i*ad[x];
			al[x]=ad[x]=0;
		}
	}
	void rebuild() { //重构 
		n=0;
		for(int i=1;i<=cnt;i++) {
			reset(i);
			for(auto j:p[i]) a[++n]=j;
			p[i].clear();
		}
		B=sqrt(n),cnt=(n-1)/B+1;
		for(int i=1;i<=cnt;i++) sum[i]=al[i]=ad[i]=0,cov[i]=-1;
		for(int i=1;i<=n;i++) sum[(i-1)/B+1]+=a[i],p[(i-1)/B+1].push_back(a[i]);
	}
	void change1(int l,int r,long long x) { //区间赋值 
		auto L=get_block(l),R=get_block(r);
		int bl=L.first,pl=L.second,br=R.first,pr=R.second;
		if(bl==br) {
			reset(bl);
			for(int i=pl;i<=pr;i++) sum[bl]+=x-p[bl][i],p[bl][i]=x;
			return;
		}
		reset(bl),reset(br);
		for(int i=pl;i<(int)p[bl].size();i++) sum[bl]+=x-p[bl][i],p[bl][i]=x;
		for(int i=0;i<=pr;i++) sum[br]+=x-p[br][i],p[br][i]=x;
		for(int i=bl+1;i<=br-1;i++) sum[i]=p[i].size()*x,cov[i]=x,al[i]=ad[i]=0; //注意等差数列加法标记会清空 
	}
	void change2(int l,int r,long long x) { //区间加等差数列 
		auto L=get_block(l),R=get_block(r);
		int bl=L.first,pl=L.second,br=R.first,pr=R.second;
		if(bl==br) {
			reset(bl);
			for(int i=pl,j=1;i<=pr;i++,j++) sum[bl]+=j*x,p[bl][i]+=j*x;
			return;
		}
		reset(bl),reset(br);
		int now=1; 
		for(int i=pl;i<(int)p[bl].size();i++,now++) sum[bl]+=now*x,p[bl][i]+=now*x;
		for(int i=bl+1;i<=br-1;now+=p[i].size(),i++) {
			long long start=now*x,end=start+(p[i].size()-1)*x;
			sum[i]+=(start+end)*p[i].size()/2;
			al[i]+=start,ad[i]+=x;
		}
		for(int i=0;i<=pr;i++,now++) sum[br]+=now*x,p[br][i]+=now*x;
	}
	void change3(int x,int y) { //单点插入 
		auto L=get_block(x);
		int bl=L.first,pl=L.second;
		reset(bl),p[bl].insert(p[bl].begin()+pl,y),sum[bl]+=y; 
		if((int)p[bl].size()>10*B) rebuild();
	}
	long long query(int l,int r) { //区间求和 
		auto L=get_block(l),R=get_block(r);
		int bl=L.first,pl=L.second,br=R.first,pr=R.second;
		long long res=0;
		if(bl==br) {
			reset(bl);
			for(int i=pl;i<=pr;i++) res+=p[bl][i];
			return res;
		}
		reset(bl),reset(br);
		for(int i=pl;i<(int)p[bl].size();i++) res+=p[bl][i];
		for(int i=0;i<=pr;i++) res+=p[br][i];
		for(int i=bl+1;i<=br-1;i++) res+=sum[i];
		return res;
	}
	
	int main() {
		scanf("%d%d",&n,&q);
		B=sqrt(n),cnt=(n-1)/B+1;
		for(int i=1;i<=n;i++) {
			scanf("%lld",&a[i]);
			sum[(i-1)/B+1]+=a[i];
			p[(i-1)/B+1].push_back(a[i]);
		}
		for(int i=1;i<=cnt;i++) cov[i]=-1;
		while(q--) {
			int opt,l,r;
			long long x;
			scanf("%d%d%d",&opt,&l,&r);
			if(opt==1) scanf("%lld",&x),change1(l,r,x);
			else if(opt==2) scanf("%lld",&x),change2(l,r,x);
			else if(opt==3) change3(l,r);
			else printf("%lld\n",query(l,r));
		}

		return 0;
	}
}

int main() {
	Cherry::main();

	return 0;
}

然而，通过每次都插入在序列的末尾，实测上面的代码会被卡得很惨。考虑对操作三的插入操作，使用 块状链表 代替 vector 维护。
- 只需要使用数组而非 vector 维护块内的元素，重构时也只需要将单块分裂为两块而不用整个序列重构。
- 注意块长不能设置为 $\sqrt n$ ，因为如果 $n$ 初始很小而插入操作很多，可能会导致最后块长过小而超时。
时间复杂度 $O(n\sqrt n)$ 。

参考代码如下。

#include <bits/stdc++.h> //分块（块状链表） 
using namespace std;

namespace Cherry {
	const int N=2e5+10,M=1605;
	int n,q,B,cnt;
	
	struct chain { //块状链表 
		int len,nextt;
		long long sum,cov,al,ad;
		long long a[M];
	}p[M];
	pair<int,int> get_block(int x) { //找到x对应的块和块内位置 
		int cur=1;
		while(p[cur].nextt&&p[cur].len<x) x-=p[cur].len,cur=p[cur].nextt;
		return make_pair(cur,x);
	}
	void reset(int x) { //处理块内的tag 
		if(p[x].cov) {
			for(int i=1;i<=p[x].len;i++) p[x].a[i]=p[x].cov;
			p[x].cov=0;
		}
		if(p[x].al||p[x].ad) {
			for(int i=1;i<=p[x].len;i++) p[x].a[i]+=p[x].al+(i-1)*p[x].ad;
			p[x].al=p[x].ad=0;
		}
	}
	void rebuild(int x) { //重构（分裂） 
		cnt++;
		reset(x); //注意要先处理完tag 
		for(int i=B+1;i<=p[x].len;i++) {
			p[cnt].a[++p[cnt].len]=p[x].a[i];
			p[x].sum-=p[x].a[i],p[cnt].sum+=p[x].a[i]; //注意更新总和 
		}
		p[x].len=B,p[cnt].nextt=p[x].nextt,p[x].nextt=cnt;
	}
	void change1(int l,int r,long long x) { //区间赋值 
		auto L=get_block(l),R=get_block(r);
		int bl=L.first,pl=L.second,br=R.first,pr=R.second;
		if(bl==br) {
			reset(bl);
			for(int i=pl;i<=pr;i++) p[bl].sum+=x-p[bl].a[i],p[bl].a[i]=x;
			return;
		}
		reset(bl),reset(br);
		for(int i=pl;i<=p[bl].len;i++) p[bl].sum+=x-p[bl].a[i],p[bl].a[i]=x;
		for(int i=1;i<=pr;i++) p[br].sum+=x-p[br].a[i],p[br].a[i]=x;
		for(int i=p[bl].nextt;i!=br;i=p[i].nextt) p[i].sum=p[i].len*x,p[i].cov=x,p[i].al=p[i].ad=0; //注意等差数列加法标记会清空 
	}
	void change2(int l,int r,long long x) { //区间加等差数列 
		auto L=get_block(l),R=get_block(r);
		int bl=L.first,pl=L.second,br=R.first,pr=R.second;
		if(bl==br) {
			reset(bl);
			for(int i=pl,j=1;i<=pr;i++,j++) p[bl].sum+=j*x,p[bl].a[i]+=j*x;
			return;
		}
		reset(bl),reset(br);
		int now=1; 
		for(int i=pl;i<=p[bl].len;i++,now++) p[bl].sum+=now*x,p[bl].a[i]+=now*x;
		for(int i=p[bl].nextt;i!=br;now+=p[i].len,i=p[i].nextt) {
			long long start=now*x,end=start+(p[i].len-1)*x;
			p[i].sum+=(start+end)*p[i].len/2;
			p[i].al+=start,p[i].ad+=x;
		}
		for(int i=1;i<=pr;i++,now++) p[br].sum+=now*x,p[br].a[i]+=now*x;
	}
	void change3(int x,int y) { //单点插入 
		auto L=get_block(x);
		int bl=L.first,pl=L.second;
		reset(bl);
		p[bl].len++,p[bl].sum+=y;
		for(int i=p[bl].len;i>=pl+1;i--) p[bl].a[i]=p[bl].a[i-1];
		p[bl].a[pl]=y;
		if(p[bl].len>=2*B) rebuild(bl);
	}
	long long query(int l,int r) { //区间求和 
		auto L=get_block(l),R=get_block(r);
		int bl=L.first,pl=L.second,br=R.first,pr=R.second;
		long long res=0;
		if(bl==br) {
			reset(bl);
			for(int i=pl;i<=pr;i++) res+=p[bl].a[i];
			return res;
		}
		reset(bl),reset(br);
		for(int i=pl;i<=p[bl].len;i++) res+=p[bl].a[i];
		for(int i=1;i<=pr;i++) res+=p[br].a[i];
		for(int i=p[bl].nextt;i!=br;i=p[i].nextt) res+=p[i].sum;
		return res;
	}
	
	int main() {
		scanf("%d%d",&n,&q);
		B=800,cnt=(n-1)/B+1;
		for(int i=1;i<=n;i++) {
			int x;
			scanf("%d",&x);
			int bl=(i-1)/B+1;
			p[bl].sum+=x;
			p[bl].a[++p[bl].len]=x;
		}
		for(int i=1;i<=cnt;i++) p[i].nextt=(i<cnt)?i+1:0;
		while(q--) {
			int opt,l,r;
			long long x;
			scanf("%d%d%d",&opt,&l,&r);
			if(opt==1) scanf("%lld",&x),change1(l,r,x);
			else if(opt==2) scanf("%lld",&x),change2(l,r,x);
			else if(opt==3) change3(l,r);
			else printf("%lld\n",query(l,r));
		}

		return 0;
	}
}

int main() {
	Cherry::main();

	return 0;
}

附数据生成器。

#include <bits/stdc++.h>
using namespace std;

namespace Cherry {
	const int N=15;
	int n,q;
	int main() {
		srand(time(NULL)); 
		n=rand()%N+2,q=rand()%N+1;
		printf("%d %d\n",n,q);
		for(int i=1;i<=n;i++) {
			int x=rand()%N+1;
			printf("%d ",x);
		}
		printf("\n");
		while(q--) {
			int opt,l,r,x;
			opt=rand()%4+1,l=rand()%(n-1)+1,r=rand()%(n-l),x=rand()%N+1;
			printf("%d ",opt);
			if(opt==1) printf("%d %d %d\n",l,l+r,x);
			if(opt==2) printf("%d %d %d\n",l,l+r,x);
			if(opt==3) {
				n++,l=rand()%n+1,x=rand()%N+1;
				printf("%d %d\n",l,x);
			}
			if(opt==4) printf("%d %d\n",l,l+r);
		}
		
		return 0;
	}
}

int main() {
	freopen("data.in","w",stdout);
	Cherry::main();
	
	return 0;
}

ID

4853

时间

1000ms

内存

128MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

信息

状态

开发

支持

关于

1 条题解

[COCI 2010/2011 #7] UPIT

信息

状态

开发

支持

关于

还没有账户？

登录