题解：P4117 [Ynoi2018] 五彩斑斓的世界

第二分块。

题意

给定一个长度为

n

的序列

a

，有

m

次操作，共有两种：

1.将

a

的区间

[l,r]

内大于

x

的数减去

x

。
2.查询

a

的区间

[l,r]

中

x

出现的次数。

n\le10^6,m\le5\times10^5,0\le x\le10^5+1

。

做法

将序列分块，设块长为

\sqrt n

，对于每个块记录最大值上界

mx

。

考虑整块操作，因为每个位置的修改后的值只和修改前的值有关，所以我们可以对于每个块内，用并查集维护数值相同的位置，且额外维护每个数值对应并查集中集合的根，然后分两种情况讨论：

$mx\le2\times x$
对于值域 $(x,mx]$ ，将并查集中这些值对应的集合向 $-x$ 后的集合合并，此时 $mx$ 减少为 $x$ 。
$mx>2\times x$
对于值域 $[0,x]$ ，将并查集中这些值的集合向 $+x$ 后的集合合并，再给当前块打上整体 $-x$ 的标记（因为给大于 $x$ 的数 $-x$ 等价于给不大于 $x$ 的数 $+x$ 再全局 $-x$ ），此时令 $mx$ 减少 $x$ 。

注意到每次给

mx

减少的值和做出实际操作的值数量是只相差常数的，所以这个部分的时间复杂度复杂度可以均摊为

O(V\sqrt n)

。

对于散块修改，直接把整块重构然后暴力改掉；对于整块查询，出现次数就是

x

在当前块并查集中所对应的集合大小；对于散块查询，我们在并查集中额外维护每个联通块对应的数值即可。

如果按照一般方式开空间，空间复杂度为

O(V\sqrt n)

，显然不可接受；观察到修改和查询时每块独立，因此离线下来逐块处理即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define max(...) max({__VA_ARGS__})
#define min(...) min({__VA_ARGS__})
#define tomx(x,...) ((x)=max((x),__VA_ARGS__))
#define tomn(x,...) ((x)=min((x),__VA_ARGS__))
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define N 2000005
#define V 100005
#define M 1000005
#define len 660
bool op[M];
int L[M],R[M],X[M],ans[M],rt[V],tag,mx,cnt[V];
int n,q;
int a[N];
struct node{
	int fa,v;
}d[N];
int find(int u){
	for(;u^d[u].fa;) u=d[u].fa=d[d[u].fa].fa;
	return u;
}
void merge(int x,int y){
    //x->y
	if(!rt[y]){
		rt[y]=rt[x];
		d[rt[y]].v=y;
	}else{
		d[rt[x]].fa=rt[y];
	}
	rt[x]=0;
	cnt[y]+=exchange(cnt[x],0);
}
void solve(int id){
	int lp=(id-1)*len+1;
	int rp=id*len;
	tomn(rp,n);
	mx=tag=0;
	rep(i,lp,rp){
		tomx(mx,a[i]);
		if(!rt[a[i]]) rt[a[i]]=d[i].fa=i,d[i].v=a[i];
		else d[i].fa=rt[a[i]];
		cnt[a[i]]++;
	}
	rep(iq,1,q){
		int l=L[iq],r=R[iq],x=X[iq];
		if(r<lp||rp<l) continue;
		if(l<=lp&&rp<=r){
			if(!op[iq]){
				if(!x) continue;
				if(mx-tag<=2*x){
					rep(i,x+1+tag,mx){
						if(rt[i]) merge(i,i-x);
					}
					tomn(mx,x+tag);
				}else{
					per(i,x+tag,0+tag){
						if(rt[i]) merge(i,i+x);
					}
					tag+=x;
				}
			}else{
				if(x+tag<V)	ans[iq]+=cnt[x+tag];
			}
		}else{
			if(!op[iq]){
				if(!x) continue;
				rep(i,lp,rp) a[i]=d[find(i)].v;
				rep(i,lp,rp) rt[a[i]]=cnt[a[i]]=0;
				rep(i,lp,rp) a[i]-=tag;
				rep(i,lp,rp) d[i].v=0;
				rep(i,max(l,lp),min(r,rp)) a[i]-=x&-(a[i]>x);
				mx=tag=0;
				rep(i,lp,rp){
					tomx(mx,a[i]);
					if(!rt[a[i]]) rt[a[i]]=d[i].fa=i,d[i].v=a[i];
					else d[i].fa=rt[a[i]];
					cnt[a[i]]++;
				}
			}else{
				if(x+tag<V) rep(i,max(l,lp),min(r,rp)) ans[iq]+=(d[find(i)].v-tag==x);
			}
		}
	}
	rep(i,lp,rp) a[i]=d[find(i)].v,rt[a[i]]=cnt[a[i]]=0;
}
main(){
#ifdef LOCAL
    auto start=clock();
#endif
    ios::sync_with_stdio(0),cin.tie(nullptr);
	cin>>n>>q;
	rep(i,1,n) cin>>a[i];
	rep(i,1,q){
		int c;
		cin>>c>>L[i]>>R[i]>>X[i];
		op[i]=c-1;
	}
	rep(i,1,(n-1)/len+1) solve(i);
	rep(i,1,q){
		if(op[i]) cout<<ans[i]<<"\n";
	}
#ifdef LOCAL
    clog<<"\ntime: "<<clock()-start<<" ms\n";
#endif
}

题解：P4117 [Ynoi2018] 五彩斑斓的世界

文章操作

题意

做法

代码

相关推荐

评论

题解：P4117 [Ynoi2018] 五彩斑斓的世界