首页 > Different Integers
头像 回归梦想
发表于 2020-11-11 21:13:56
题目描述 题解: 个人感觉这个题真不错。。。emmm。。为什么这么说,这个题有多种做法:1.树状数组2.莫队算法3.主席树4.线段树想讲讲我的做题过程,再讲正解 做题过程 第一反应就是树状数组我想的很简单,只将第一次出现的数字插入到树状数组中,最后记录[r,n]和[1,l]的答案ll w=get 展开全文
头像 19-大数据一班-杨文冠
发表于 2021-07-29 17:25:19
题意: 给出个数,求 ,这两个区间不同数的个数 思路: 其实只要把区间扩大一倍,就是求这个区间了 定义数组中第一次出现的数的后缀为,第次出现的数的后缀为该数第次出先时的下标。比如:原数组为,扩大一倍后为,每个数对应的后缀为。 如果某个数出现多次,而我们只算最右边的那个,我们会发现最右边的那个数的后缀 展开全文
头像 已经死了
发表于 2023-07-13 22:17:42
思路离线查询,树状数组维护 查询按右端点r排序,遍历查询,当一个数字全出现了,那就把这个数字第一次出现的下标单点+1 查询[l+1,r-1]的区间和,用总的去减就可以了 import sys,random,bisect from collections import deque,defaultdic 展开全文
头像 陌研
发表于 2021-10-04 21:36:14
【Different Integers题解】 模板题,扔一个比较简洁的代码。 将指针起始位置定义在L=0,R=n+1,然后随着查询操作(l,r)进行移动,使得L=l,R=r。 需要注意的是查询的边界问题,l和r也包含在被查询的区间中。 #include <bits/stdc++.h> u 展开全文
头像 left_right_steady
发表于 2021-10-06 19:18:07
题意:有一个数组 a[] 长度为n. q组询问,每组询问[L,R]表示询问a1……aL,aR……an中有多少个不同的数字。n,q=1e5. 令an+i=ai,将原数组a[]的长度扩大为2n 原询问等价于[R,n+L],即询问aR……an,an+1,……,an+L中有多少个不 展开全文

等你来战

查看全部