首页 > 代码库 > 洛谷 P3730 曼哈顿交易

洛谷 P3730 曼哈顿交易

2024-10-11 06:29:01   216人阅读

https://www.luogu.org/problem/show?pid=3730

题目背景

will在曼哈顿开了一家交易所，每天，前来买卖股票的人络绎不绝。

现在，will想要了解持股的情况。由于来交♂易的人实在是太多了，需要你写一个程序来帮他完成这个任务。

题目描述

  • 前来交易的N个人排成了一行，为了简便起见，每个人都只持有一种股票。

  • 不同的的人可能会持有相同的股票。

  • 定义一种股票的热度为持有该股票的人数。

  • 每次，will会给出这样的询问：在一段连续区间的人之中，热度第k小的股票的热度是多少？

输入输出格式

输入格式：

 

  • 第一行两个正整数N，M，分别表示人数和询问的次数；

  • 接下来一行N个正整数，表示每个人所持的股票 技术分享。

  • 接下来M行，每行三个正整数l，r，k，表示询问区间技术分享中的第k小的热度，保证技术分享。

 

输出格式：

 

  • 对于每个询问，输出一行一个数，表示区间[l, r]中的第k小的热度值。

  • 如果k大于区间里股票的种类数，输出-1。

 

输入输出样例

输入样例#1：
4 4  2 3 3 3  1 4 1  1 4 2  1 3 21 3 3
输出样例#1：
1  3  2  -1

说明

对于20%的数据，技术分享；

对于另外10%的数据，所有的技术分享；

对于100%的数据，技术分享；

莫队

离散化

维护每种股票的出现次数sum

维护出现次数（热度）为i的有几种股票，即出现次数的出现次数cnt

同时，对cnt分块查询

#include<cmath>#include<cstdio>#include<algorithm>#define N 100001using namespace std;int n,m,siz;int key[N],hashh[N];int bl[N],ans[N];int sum[N],cnt[N],block[N],num;struct node{    int l,r,id,k;    bool operator < (node p)const    {         if(bl[l]!=bl[p.l]) return bl[l]<bl[p.l];         if(r!=p.r) return r<p.r;         return k<p.k;    }}e[N];void read(int &x){    x=0; char c=getchar();    while(c<‘0‘||c>‘9‘) c=getchar();    while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); }}    inline void update(int pos,int w){            block[bl[sum[hashh[pos]]]]--;    cnt[sum[hashh[pos]]]--;         if(w) sum[hashh[pos]]++;          else sum[hashh[pos]]--;        block[bl[sum[hashh[pos]]]]++;    cnt[sum[hashh[pos]]]++;}inline int query(int w){    int i;    for(i=1;i<=siz;i++)      if(w-block[i]>0) w-=block[i];     else break;    for(int j=(i-1)*siz+1;j<=i*siz;j++)    {        w-=cnt[j];        if(w<=0) return j;    }    return -1;}int main(){    read(n); read(m);    siz=sqrt(n);    for(int i=1;i<=n;i++) bl[i]=(i-1)/siz+1;     for(int i=1;i<=n;i++) read(key[i]),hashh[i]=key[i];    sort(key+1,key+n+1);    key[0]=unique(key+1,key+n+1)-(key+1);    for(int i=1;i<=n;i++) hashh[i]=lower_bound(key+1,key+key[0]+1,hashh[i])-key;    int l,r,w;    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].k); e[i].id=i;    }    sort(e+1,e+m+1);    int L=1,R=0;    for(int i=1;i<=m;i++)    {        while(L<e[i].l) update(L++,false);        while(L>e[i].l) update(--L,true);        while(R>e[i].r) update(R--,false);        while(R<e[i].r) update(++R,true);        ans[e[i].id]=query(e[i].k);    }    for(int i=1;i<=m;i++)  printf("%d\n",ans[i]);}

 

洛谷 P3730 曼哈顿交易


联系
我们