首页 > 代码库 > acdreamoj1108(The kth number)
acdreamoj1108(The kth number)
题目链接:http://acdream.info/problem?pid=1108
题意:n个数的数列,m次查询某个区间出现次数第k多的数出现的次数。n,m<=100000
解法:这个因为是离线的所以可以先统一处理,然后再输出。可以维护一个left和right指针,pre,pre[i]表示此时区间内出现次数大于等于i的数的种类。为了减少复杂度,关键是left和right的移动方式,即查询区间如何排序,如果紧靠区间左端点排序,那么右端点每次一定最大回是n,如果按照右端点排序,左端点每次一定最大是n。这里有个很好的处理办法,就是模糊排序,先左端点非严格排序,即除以sqrt(n)再排序,这样复杂度最大是n*sqrt(n)
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const int INF=1e9+7; int num[Max]; int help[Max]; int r[Max]; int l[Max]; int k[Max]; int pre[Max]; int cnt[Max]; int tool; bool cmp(int i,int j) { if(l[i]/tool==l[j]/tool&&r[i]!=r[j]) return r[i]<r[j]; return l[i]<l[j]; } int ans[Max]; int n,m; int findans(int t) { int l=1,r=n; while(l<=r) { int middle=(l+r)/2; if(pre[middle]>=t) l=middle+1; else r=middle-1; } return l-1; } int main() { int t; cin>>t; while(t--) { scanf("%d%d",&n,&m); tool=sqrt(n); for(int i=0; i<n; i++) scanf("%d",num+i),help[i]=i; for(int i=0; i<m; i++) scanf("%d%d%d",l+i,r+i,k+i),l[i]--,r[i]--; sort(help,help+m,cmp); memset(cnt,0,sizeof cnt); memset(pre,0,sizeof pre); int left=0,right=-1; for(int i=0;i<m;i++) { int L=l[help[i]],R=r[help[i]]; while(left<L){ pre[cnt[num[left++]]--]--;} while(L<left){ pre[++cnt[num[--left]]]++;} while(right<R){ pre[++cnt[num[++right]]]++;} while(R<right){ pre[cnt[num[right--]]--]--;} ans[help[i]]=findans(k[help[i]]); } for(int i=0;i<m;i++) printf("%d\n",ans[i]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。