首页 > 其他分享 >Luogu P4168 [Violet] 蒲公英 题解

Luogu P4168 [Violet] 蒲公英 题解

时间:2023-10-29 22:15:40浏览次数:44  
标签:cnt int 题解 复杂度 sqrt Luogu cnt2 ans P4168

题目链接

[Violet] 蒲公英

分析

可以先将 \(a[i]\) 离散化
然后考虑分块
对于询问 \(x,y\), \(x\) 属于 \(p\), \(y\) 属于 \(q\)

当 \(q-p<=1\) 时

直接暴力枚举即可,时间复杂度为 \(O(\sqrt{n})\)

\(else\) 如图

image
中间为分好块的地方
我们发现, \(ans\) 只可能为中间的众数或两边的的数
对于中间的众数,我们可以预处理出 \(z[i][j]\) 代表块 \(i\) 与块 \(j\) 之间的众数,时间复杂度为 \(O(n\sqrt{n})\)
对于两边的数,由于要考虑它们在中间出现的个数,所以先预处理出 \(cnt[i][j]\) 代表块 \(i\) 前, \(a[j]\) 的个数,时间复杂度为 \(O(n\sqrt{n})\)
再暴力枚举左右两侧,时间复杂度为, \(O(\sqrt{n})\)

所以总时间复杂度为 \(O(n\sqrt{n})\)

代码

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

#define int long long

const int N=40005,SN=405;

int id[N],a[N];
struct C{int id,w;}c[N];
bool cmp(C a,C b){return a.w<b.w;}

int fmp[N];
int tot=0;
int z[SN][SN],cnt[SN][N];
int cnt1[N],cnt2[N];
struct NODE{int l,r;}no[SN];

signed main(){
	int n,m;
	scanf("%lld %lld", &n, &m);
	int L=sqrt(n);
	for(int i=1;i<=n;i++){
		id[i]=(i-1)/L+1;
		if(id[i]!=id[i-1]) no[id[i]].l=i;
		if(i%L==0) no[id[i]].r=i;
		scanf("%lld", &a[i]);
		c[i].w=a[i];c[i].id=i;
	}
	no[id[n]].r=n;
	
	sort(c+1,c+n+1,cmp);//离散化 
	for(int i=1;i<=n;i++){
		if(c[i].w!=c[i-1].w) a[c[i].id]=++tot;
		else a[c[i].id]=tot;
		fmp[tot]=c[i].w;
	}
	
	for(int i=1;i<=n;i++){//预处理前缀和 
		if(id[i]!=id[i-1]) for(int j=1;j<=tot;j++) cnt[id[i]][j]=cnt[id[i-1]][j];
		cnt[id[i]][a[i]]++;
	}
	
	for(int i=1;i<=id[n];i++){//预处理众数 
		int ma=0;
		for(int j=i;j<=id[n];j++){
			int l=no[j].l,r=no[j].r;
			for(int k=l;k<=r;k++){
				int d=a[k];
				cnt1[d]++;
				if(cnt1[d]>cnt1[ma]) ma=d;
				else if(cnt1[d]==cnt1[ma]&&fmp[d]<fmp[ma]) ma=d;
			}
			z[i][j]=ma;
		}
		for(int j=1;j<=tot;j++) cnt1[j]=0;
	}
	
	int ans=0;
	for(int i=1;i<=m;i++){
		int x,y;scanf("%lld %lld", &x, &y);
		x=(x+ans-1)%n+1;y=(y+ans-1)%n+1;if(x>y) swap(x,y);
		
		int p=id[x],q=id[y];
		if(p==q||p==q-1){//情况一 
			ans=0;
			for(int j=x;j<=y;j++){
				int d=a[j];
				cnt2[d]++;
				if(cnt2[d]>cnt2[ans]) ans=d;
				else if(cnt2[d]==cnt2[ans]&&fmp[d]<fmp[ans]) ans=d;
			}				
			ans=fmp[ans];
			printf("%lld\n", ans);
			for(int j=x;j<=y;j++) cnt2[a[j]]=0;
		}
		else{//情况二 
			p++;q--;
			ans=z[p][q];
			for(int j=x;j<=no[p-1].r;j++){//左边 
				int d=a[j];
				cnt2[d]++;
				if(cnt2[d]+cnt[q][d]-cnt[p-1][d]>cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]) ans=d;
				else if(cnt2[d]+cnt[q][d]-cnt[p-1][d]==cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]&&fmp[d]<fmp[ans]) ans=d;
			}
			for(int j=no[q+1].l;j<=y;j++){//右边 
				int d=a[j];
				cnt2[d]++;
				if(cnt2[d]+cnt[q][d]-cnt[p-1][d]>cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]) ans=d;
				else if(cnt2[d]+cnt[q][d]-cnt[p-1][d]==cnt2[ans]+cnt[q][ans]-cnt[p-1][ans]&&fmp[d]<fmp[ans]) ans=d;
			}
			ans=fmp[ans];printf("%lld\n", ans);
			//归零 
			for(int j=x;j<=no[p].l-1;j++) cnt2[a[j]]--;
			for(int j=no[q].r+1;j<=y;j++) cnt2[a[j]]--;
		}
	}
	return 0;
}

标签:cnt,int,题解,复杂度,sqrt,Luogu,cnt2,ans,P4168
From: https://www.cnblogs.com/Idtwtei/p/17796613.html

相关文章

  • 2023年10月第四周题解------输入与输出
     问题A:ly喜欢玩石头 解题思路题目告诉我们(1<=a,b<=1e9),那么int类型就够了。因为这两个数相加最大为20亿定义两个变量a和b输入a和b的值打印a加b的值#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<time.h>intmain......
  • 题解:「NOIP2022 提高组」种花
    题解:「NOIP2022提高组」种花题目大意:给定一个\(n\timesm\)的01矩阵,0表示可以种花,1表示土坑(无法种花),现在要在图上种出一个C型或F型(C,F横着的两条线的长度都可以不同,但一定是面向右边的),现在问你种C和F分别有多少种方案(除了这个形状外不能在任何地方种花),多组数据,\(T\leq5\)。......
  • 【梦熊联盟】10月28日 NOIP十连测 第五场 题解
    目录T1男女排队简要题意:题解:T2树上最多不相交路径简要题意:题解:T3生日T4组队比赛简要题意:题解:T1男女排队简要题意:求长度为\(n\)的01序列不包含字串101或111的个数。\((n\leqslant10^{18})\)题解:一开始往容斥的思路去想,但是在推式子的时候发现其实很难容斥掉一个子串......
  • 常见问题解决 --- 安卓12关闭phantom processes killer杀后台功能
    1.adb连接成功后,执行adbdevices2.执行adbshell3.执行device_configset_sync_disabled_for_testspersistentdevice_configputactivity_managermax_phantom_processes2147483647settingsputglobalsettings_enable_monitor_phantom_procsfalse......
  • 常见问题解决 --- adb连接失败
    可能原因有,手机问题,电脑问题,线材问题。手机问题有:没有开启adb调试usb连接模式不是文件传输模式电脑问题有:adb驱动安装版本不匹配adb没有正确安装安卓驱动没有安装线材质量不好,断开 ......
  • VMware VCSA 5480 后台登录提示无法登陆问题解决
     通过控制台登入启用shell使用service-control--status--all查看applmgmt服务状态(显示已停止) 使用service-control--startapplmgmt启动服务 回车后会自动退出命令行模式 此时回到浏览器新建标签页重新登录5480端口成功    使用官网说明使用SingleS......
  • 【题解】P9753 [CSP-S 2023] 消消乐(字符串哈希,DP)
    【题解】P9753[CSP-S2023]消消乐不知道考场脑子是抽了还是有病,全程都不知道在放什么屁。特别鸣谢:@dbxxx给我讲解了解法一的满分做法,并让我对哈希有了更加深刻的认识;@Daidly给我讲解了解法二。题目链接P9753[CSP-S2023]消消乐题意概述给定一个长度为\(n\)的只含小......
  • AtCoder Beginner Contest 326 题解
    首先,\(\text{HappyBirthdaytome!}\)A-2UP3DOWN常规ABCA...//If,oneday,Ifinallymanagetomakemydreamsareality...//Iwonder,willyoustillbetherebymyside?#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false)#defineTI......
  • P2514 [HAOI2010] 工厂选址 题解
    目录DescriptionSolutionCodeDescription有\(m\)座煤矿,每一座煤矿有\(a_i\)吨煤,第\(i\)座煤矿到第\(j\)号发电厂的运费为\(c_{i,j}\)每吨。有一座发电厂(标号为0),需要恰好\(b\)吨煤矿发电,初始运行费用为\(h\)。还有\(n\)座待运行的发电厂(标号为1~n),每座发电厂初......
  • ctf_show Web的Web8题解
    好久没写博客,上次写还是在上次(三年前)。如题,写一次CTF的题解 根据题目提示得知这应该是一个注入,什么注入还不知道,进入靶场。 仅有三个地方可点,都点进去看看。从URL处可以看到前端是传了一个参数id给后端(另外两个类似,就不贴图了)。那很明显了是SQL注入。 首先在参数后......