本文主要是介绍bzoj 5143 [Ynoi2018]五彩斑斓的世界，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二阶堂真红给了你一个长为n的序列a，有m次操作
1.把区间[l,r]中大于x的数减去x
2.查询区间[l,r]中x的出现次数
题解：
今天模拟赛第一题=_=，把题看错，然后暴力打了30分跑路了。
由乃题肯定是分块了。
由于数字的大小只有十万，可以先假装做本道题的基本方法是每次以o(x)的复杂度将每个块内的极差减小x。
我们对于每一个块维护一个maxx[i]与dat[i]表示这个块内的最大值与这个块整体减小的值，便可以对maxx[i]与x的关系进行分类讨论。
1）对于maxx[i]<=x 不用考虑。
2）对于x<maxx[i]<=2*x的情况，那么，我们可以从x+1到maxx[i]枚举，将每一个存在的数字y合并y-x去，但是这里合并我们并不能直接进行查找，所以我们可以用并查集来维护每一个位置的所属情况，具体方法为：数组pos[i][j]表示在第i个块中第j个数字第一个出现的位置，siz[pos[i][j]]表示pos[i][j]表示的数字在第i个块里出现的次数，那么对于一个块内同样的数字我们先把它合并到一起，接着如果要将一个数y合并到y-x去，那们我们就在并查集中将它的fa连向y-x即可，然后将它的siz，加到y-x的siz中即可，这一步通过maxx[i]-x次枚举将极差减少了maxx[i]-x，可行。
3）对于maxx[i]>2*x的情况，我们如果继续如上面枚举的话，复杂度极高，那么我们可以反过来想，我们将1-x的数字加一个x，再给整个块减去一个x，这样我们就通过o(x)的复杂度将极差减少了x，合并方法同上，复杂度也可行。
这样我们就解决了这道题了，由于bzoj卡常，原本40s，256m改成了20s，128m...所以下面只能附tle代码。
下附tle代码。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define maxn 100005
using namespace std;
int n,m,q;
inline int read()
{register int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
//基本数组
int a[maxn],val[maxn],fa[maxn];
//分块数组
short bel[maxn];
int l[maxn],r[maxn],maxx[maxn],pos[318][maxn],siz[maxn],dat[maxn];
inline int getfa(int now)
{return fa[now]==now ? now : fa[now]=getfa(fa[now]);
}
inline void update(register int now)
{while(!pos[now][maxx[now]])maxx[now]--;
}
inline void build(register int now)
{maxx[now]=100000;for(register int i=l[now];i<=r[now];i++) a[i]=val[getfa(i)],pos[now][a[i]]=0;for(register int i=l[now];i<=r[now];i++) fa[i]=i,siz[i]=1;for(register int i=l[now];i<=r[now];i++){if(pos[now][a[i]]){siz[pos[now][a[i]]]+=siz[i];fa[i]=pos[now][a[i]];}else{pos[now][a[i]]=i;val[i]=a[i];}}update(now);
}
inline void modify(register int now,register int nl,register int nr,register int x)
{for(register int i=l[now];i<=r[now];i++) a[i]=val[getfa(i)];for(register int i=l[now];i<=r[now];i++) pos[now][a[i]]=0;for(register int i=nl;i<=nr;i++)if(a[i]-dat[now]>x)a[i]-=x;for(register int i=l[now];i<=r[now];i++)val[i]=a[i],fa[i]=i;build(now);
}
inline void update(register int nl,register int nr,register int x)
{modify(bel[nl],nl,min(nr,r[bel[nl]]),x);for(register int i=bel[nl]+1;i<=bel[nr]-1;i++){if(x*2<=maxx[i]-dat[i]){for(register int j=dat[i]+1;j<=dat[i]+x;j++){if(pos[i][j]){if(!pos[i][j+x]){pos[i][j+x]=pos[i][j];val[pos[i][j+x]]=j+x;pos[i][j]=0;}else{siz[pos[i][j+x]]+=siz[pos[i][j]];fa[pos[i][j]]=pos[i][j+x];pos[i][j]=0;}}}dat[i]+=x;}else{for(register int j=dat[i]+x+1;j<=maxx[i];j++)if(pos[i][j]){if(!pos[i][j-x]) {pos[i][j-x]=pos[i][j];val[pos[i][j-x]]=j-x;pos[i][j]=0;}else{siz[pos[i][j-x]]+=siz[pos[i][j]];fa[pos[i][j]]=pos[i][j-x];pos[i][j]=0;}}update(i);}}if(bel[nl]!=bel[nr]){modify(bel[nr],l[bel[nr]],nr,x);}
}
inline int query(register int nl,register int nr,register int x)
{register int ans=0;register int temp=min(nr,r[bel[nl]]);for(register int i=nl;i<=temp;i++)if(val[getfa(i)]-dat[bel[i]]==x)ans++;for(register int i=bel[nl]+1;i<=bel[nr]-1;i++)if(x+dat[i]<=100000)ans+=siz[pos[i][x+dat[i]]];if(bel[nl]!=bel[nr]){for(register int i=l[bel[nr]];i<=nr;i++)if(val[getfa(i)]-dat[bel[i]]==x)ans++;}return ans;
}
inline void write(register int x)
{if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');
}
int main()
{n=read();q=read();m=sqrt(n);for(register int i=1;i<=n;i++){a[i]=read(); val[i]=a[i];bel[i]=(i-1)/m+1;if(!l[bel[i]])l[bel[i]]=i;r[bel[i]]=i;fa[i]=i;}for(register int i=1;i<=bel[n];i++)build(i);while(q--){register int op,x,y,z;op=read();x=read();y=read();z=read();if(op==1)update(x,y,z);elsewrite(query(x,y,z)),puts("");}
}这篇关于bzoj 5143 [Ynoi2018]五彩斑斓的世界的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
