[bzoj 5143][Ynoi 2018]五彩斑斓的世界

传送门

Descroption

Solution

Code 

#include<bits/stdc++.h>

#define ll long long

using namespace std;

char B[1<<26],*S=B;

inline int read(){

    int x;char c;

    while((c=*S++)<'0'||c>'9');

    for(x=c-'0';(c=*S++)>='0'&&c<='9';)x=x*10+c-'0';

    return x;

}

const int MN=1e5,T=650;

int a[MN+5],fa[MN/T+5][MN+5],sz[MN/T+5][MN+5],minn[T+5],maxx[T+5];

int getf(int*f,int k){return f[k]?f[k]=getf(f,f[k]):k;}

int main()

{

	B[fread(B,1,1<<26,stdin)]=0;

	int n,m,i,j,o,l,r,x,lk,rk,ans;

	n=read();m=read();

	for(i=1;i<=n;++i)a[i]=read(),++sz[(i-1)/T][a[i]];

	for(i=1;i<=n;i+=T) minn[i/T]=0,maxx[i/T]=MN;

	while(m--)

	{

		o=read();l=read();r=read();x=read();

		lk=(l-1)/T;rk=(r-1)/T;

		if(o==1)

		{

			for(i=l;i<=r&&i<=lk*T+T;++i)

				if((a[i]=getf(fa[lk],a[i]))-minn[lk]>x)--sz[lk][a[i]],++sz[lk][a[i]-=x];

			for(i=lk;++i<rk;)

				if(maxx[i]-minn[i]>2*x)

				{

					for(j=1;j<=x;++j)sz[i][fa[i][minn[i]+j]=minn[i]+j+x]+=sz[i][minn[i]+j];

					minn[i]+=x;

				}

				else

				{

					for(j=x+1;j<=maxx[i]-minn[i];++j)sz[i][fa[i][minn[i]+j]=minn[i]+j-x]+=sz[i][minn[i]+j];

					maxx[i]=min(maxx[i],minn[i]+x);

				}

			if(lk!=rk)for(i=r;i>rk*T;--i)

				if((a[i]=getf(fa[rk],a[i]))-minn[rk]>x)--sz[rk][a[i]],++sz[rk][a[i]-=x];

		}

		else

		{

			ans=0;

			for(i=l;i<=r&&i<=lk*T+T;++i)if(getf(fa[lk],a[i])-minn[lk]==x)++ans;

			for(i=lk;++i<rk;)if(x+minn[i]<=maxx[i])ans+=sz[i][x+minn[i]];

			if(lk!=rk)for(i=r;i>rk*T;--i)if(getf(fa[rk],a[i])-minn[rk]==x)++ans;

			printf("%d\n",ans);

		}

	}

}

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！