求助修改思路
查看原帖
求助修改思路
866613
sansesantongshun楼主2024/4/20 23:06

修改怎么弄

#include<bits/stdc++.h>
using namespace std;
int n,m,nm,a[100005],b[100005][2],c[320][100005],d[320][320],e[100005],ee[320][100005],ll[320],rr[320],cc[100005],dd[320],k,l,r,x,y,z,bl;
int find(int x)
{
	return x==e[x]?x:e[x]=find(e[x]);
}
int main()
{
	cin>>n>>m;
	nm=round(sqrt(n));
	for (int i=1;i<=100000;++i)
	{
		b[i][1]=(i-1)/316+1;
		if (ll[b[i][1]]==0)
		ll[b[i][1]]=i;
		rr[b[i][1]]=i;
		e[i]=i;
	}
	for (int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		b[i][0]=(i-1)/nm+1;
		++c[b[i][0]][a[i]];
		++d[b[i][0]][b[i][1]];
	}
	for (int i=1;i<=nm;++i)
	{
		for (int j=1;j<=100000;++j)
		c[i][j]+=c[i-1][j];
		for (int j=1;j<=b[100000][1];++j)
		d[i][j]+=d[i-1][j];
	}
	while (m--)
	{
		scanf("%d",&k);
		if (k==1)
		{
			scanf("%d%d%d%d",&l,&r,&x,&y);
			//完全不会 
		}
		else
		{
			scanf("%d%d%d",&x,&y,&z);
			if (b[x][0]==b[y][0])
			{
				for (int i=x;i<=y;++i)
				{
					a[i]=a[find(i)];
					++cc[a[i]];
					++dd[b[a[i]][1]];
				}
				for (bl=1;bl<=b[100000][1];++bl)
				{
					if (z-dd[bl]<=0)
					break;
					z-=dd[bl];
				}
				for (int i=ll[bl];i<=rr[bl];++i)
				{
					if (z-cc[i]<=0)
					{
						cout<<i<<'\n';
						break;
					}
					z-=cc[i];
				}
				for (int i=x;i<=y;++i)
				{
					cc[a[i]]=0;
					dd[b[a[i]][1]]=0;
				}
			}
			else
			{
				for (int i=x;b[i][0]==b[x][0];++i)
				{
					a[i]=a[find(i)];
					++cc[a[i]];
					++dd[b[a[i]][1]];
				}
				for (int i=y;b[i][0]==b[y][0];--i)
				{
					a[i]=a[find(i)];
					++cc[a[i]];
					++dd[b[a[i]][1]];
				}
				for (bl=1;bl<=b[100000][1];++bl)
				{
					if (z-dd[bl]-d[b[y][0]-1][bl]+d[b[x][0]][bl]<=0)
					break;
					z-=dd[bl]+d[b[y][0]-1][bl]-d[b[x][0]][bl];
				}
				for (int i=ll[bl];i<=rr[bl];++i)
				{
					if (z-cc[i]-c[b[y][0]-1][i]+c[b[x][0]][i]<=0)
					{
						cout<<i<<'\n';
						break;
					}
					z-=cc[i]+c[b[y][0]-1][i]-c[b[x][0]][i];
				}
				for (int i=x;b[i][0]==b[x][0];++i)
				{
					cc[a[i]]=0;
					dd[b[a[i]][1]]=0;
				}
				for (int i=y;b[i][0]==b[y][0];--i)
				{
					cc[a[i]]=0;
					dd[b[a[i]][1]]=0;
				}
			}
		}
	}
}
2024/4/20 23:06
加载中...