首页 > 其他分享 >G1: Yunli‘s Subarray Queries (easy version)(1900)(定长区间众数)

G1: Yunli‘s Subarray Queries (easy version)(1900)(定长区间众数)

时间:2024-09-12 18:21:34浏览次数:12  
标签:cnt ma G1 int ll cin version 众数 区间

在这里插入图片描述

思路:因为是定长区间,因此我们可以利用滑动窗口维护定长区间的众数的数量

AC代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int N = 2e5 + 10;

ll a[N];
ll b[N];//前i个数的相同的数的最大值
int main()
{
	
	int t;
	cin >> t;
	while(t --){
		ll n, k, q;
		cin >> n >> k >> q;
		for(int i = 1; i <= n; i ++)
		{
			cin >> a[i];
			a[i] -= i;
		}
		//求每个区间为k的区间众数的数量
		//看到定长想到滑动区间
		map<ll, ll>ma, cnt;//记录数量
		for(int i = 1; i <= n; i ++)
		{
			if(cnt.count(ma[a[i]]))//相当于对右边界进行操作
			{
				cnt[ma[a[i]]] -= 1;
				if(!cnt[ma[a[i]]]) cnt.erase(ma[a[i]]);
			}
			ma[a[i]] += 1;
			cnt[ma[a[i]]] += 1;
			//前k个数还没到达窗口最远
			if(i < k) continue;
			//因为区间长度已经确定为k了,因此我们确定了左区间,右区间也随之确定了
			b[i - k + 1] = cnt.rbegin() ->first;//代表反向开始的第一个元素,即众数
		//	cout << b[1] << "sss" << endl;
			cnt[ma[a[i - k + 1]]] -= 1;//因为开始窗口滑动了因此也需要考虑左边界了
			if(!cnt[ma[a[i - k + 1]]]) cnt.erase(ma[a[i - k + 1]]);
			ma[a[i - k + 1]]  -= 1;//左边界ma也要参与了
			if(ma[a[i - k + 1]]) cnt[ma[a[i - k + 1]]] += 1;
		}
		while(q --){
			ll l, r;
			cin >> l >> r;
			cout << k - b[l] << endl;
		}
	}
	return 0;
}

标签:cnt,ma,G1,int,ll,cin,version,众数,区间
From: https://blog.csdn.net/2301_80882026/article/details/142180996

相关文章

  • 美团面试:G1 垃圾回收底层原理是什么?说说你的调优过程?
    文章很长,且持续更新,建议收藏起来,慢慢读!疯狂创客圈总目录博客园版为您奉上珍贵的学习资源:免费赠送:《尼恩Java面试宝典》持续更新+史上最全+面试必备2000页+面试必备+大厂必备+涨薪必备免费赠送:《尼恩技术圣经+高并发系列PDF》,帮你实现技术自由,完成职业升级,薪......
  • GC日志详细解析,非常详细GC(20) Pause Young (Normal) (G1 Evacuation Pause)
    在Java虚拟机(JVM)中,垃圾收集(GC)是内存管理的关键部分。分析GC日志可以帮助我们了解应用程序的内存使用情况和GC性能。以下是对一段GC日志的详细解析,涵盖了GC的不同阶段和相关信息。GC日志示例[16636.674s][info][gc,start]GC(20)PauseYoung(Normal)(G1Evacuati......
  • 如何在 VPS 上使用 NVM(Node Version Manager)安装 Node.js
    前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。介绍如果你已经知道Node.js是什么,它是用来做什么的,以及为什么它很酷,那么可以直接跳到安装说明。如果你想更多地了解Node及其生态系统,请继续阅读。对于那些还没有听说......
  • 论文笔记--See through Gradients. Image Batch Recovery via GradInversion
    SeethroughGradients.ImageBatchRecoveryviaGradInversion\(W^{FC}\in\mathbb{R}^{M\timesN}\),其输入为一个M维向量\(v\in\mathbb{R}^M\),\(\DeltaW^{FC}_{m,n,k}\)是损失函数对全连接层\(W\)的导数。对于一个特定的类别\(n\),(\(z\)为全连接层输出的logits),其......
  • 题单5:基础练习(rating1200)
    提醒对于下述语句,返回的是1(True)/0(False),即:条件语句的真假,而非后面的值之一。std::cout<<(a<b)?"Awin":"Bwin";如果需要返回值,则需要用括号包含整个条件运算符std::cout<<((a<b)?"Awin":"Bwin");题单492B.VanyaandLanterns......
  • 题单3:基础练习(rating1000)
    题单1A:TheatreSquare数学问题118A:StringTask字符串处理。在体量较小的情况下,用多个cout语句打印可以节省代码时间。倘若体量较大,一般需要用char[]先存储需要打印的内容,最后再一次性打印。本题属于前者。58A:Chatroom字符串处理。可以事先存储需要匹配的序列char[6]......
  • CF1534F2 Falling Sand (Hard Version) 题解
    题目链接点击打开链接题目解法做法1一个沙子消失,会带走所有它所在列下面的沙子我们记每列从下往上第\(a_i\)个沙子为关键点,第\(i\)列至少消失\(a_i\)个沙子等价于所有关键点都消失一个显然的事情是:记一列最上面的沙子为起始点,则我们只会干扰起始点第一感觉是找到一......
  • Spire.Doc for Java Version:12.9
    Spire.DocforJavaisaprofessionalWordAPIthatempowersJavaapplicationstocreate,convert,manipulateandprintWorddocumentswithoutdependencyonMicrosoftWord.Byusingthismultifunctionallibrary,developersareabletoprocesscopioustasks......
  • Spire.PDF for Java Version:10.9.0
    Spire.PDFforJavaisaPDFAPIthatenablesJavaapplicationstoread,writeandsavePDFdocumentswithoutusingAdobeAcrobat.UsingthisJavaPDFcomponent,developersandprogrammerscanimplementrichcapabilitiestocreatePDFfilesfromscratchor......
  • CF2002D2 DFS Checker (Hard Version) 题解
    https://codeforces.com/problemset/problem/2002/D2考虑找一个容易维护的必要条件,再证明充分性。最容易想到的是每个子树对应一个区间,子树根位于左端点sol1相邻的结点\(p_{i-1},p_i\)有两种情况:\(fa[p_i]=p_{i-1}\);叶子\(p_{i-1}\)在子树\(fa[p_i]\)中,回溯到\(fa[......