Codeforces Round #136 (Div. 2)D(codeforces221d) 暴力！！！！

2023-11-23 09:08:16

题目链接：点这里！！！！

题意：

给你一个长度为n(n<=1e5)的序列，a1,a2,a3,...an(1<=ai<=1e9)。

再给你m(m<=1e5)个询问，每个询问里[l,r]问你al...ar这个区间。假设x在这个区间里刚好出现x次，问你这个区间里有多少个这样的x。

题解：

我们猜下这样的x最多有多少个。1+2+3+...v<=1e5，v的最大值为460。我们可以知道最多有460个这样的x。然后我们直接处理可能满足条件的x。然后直接暴力就可以了。

时间复杂度O(n*460)。

题解：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define PI 2*asin(1.0)
#define LL long long
#define pb push_back
#define pa pair
#define clr(a,b) memset(a,b,sizeof(a))
#define lson lr<<1,l,mid
#define rson lr<<1|1,mid+1,r
#define bug(x) printf("%d++++++++++++++++++++%d\n",x,x)
#define key_value ch[ch[root][1]][0]C:\Program Files\Git\bin
const LL  MOD = 1000000007;
const LL N = 1e5+15;
const int maxn = 8e3+15;
const int letter = 130;
const LL INF = 1e18;
const double pi=acos(-1.0);
const double eps=1e-10;
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m,a[N],ps[N];
int vis[N],mark[N];
vectorpp;
int dis[N][500],vv[500];
struct node{int val,id,now;
}va[N];
int main(){int cnt=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i),ps[++cnt]=a[i];sort(ps+1,ps+cnt+1);cnt=unique(ps+1,ps+cnt+1)-(ps+1);for(int i=1;i<=n;i++){va[i].val=a[i];va[i].id=lower_bound(ps+1,ps+cnt+1,a[i])-ps;}for(int i=1;i<=n;i++){vis[va[i].id]++;if(vis[va[i].id]==va[i].val) mark[va[i].id]=1;}cnt=0;for(int i=1;i<=n;i++){if(mark[va[i].id]) ps[++cnt]=va[i].id;}sort(ps+1,ps+cnt+1);cnt=unique(ps+1,ps+cnt+1)-(ps+1);for(int i=1;i<=n;i++){if(mark[va[i].id]){va[i].now=lower_bound(ps+1,ps+cnt+1,va[i].id)-ps;vv[va[i].now]=va[i].val;}}for(int i=0;i<=n;i++){for(int j=1;j<=cnt;j++) dis[i][j]=dis[i-1][j];if(!mark[va[i].id]) continue;dis[i][va[i].now]++;}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);int sum=0;for(int i=1;i<=cnt;i++){if(dis[y][i]-dis[x-1][i]==vv[i]) sum++;}printf("%d\n",sum);}return 0;
}
/*
13 5
2 2 4 4 4 4 3 5 5 5 5 5 5
1 13
2 5
2 6
7 9
3 8
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！

标签：技术

上一篇 > CodeForces 221D Little Elephant and Array （前缀和）
下一篇 > codeforces 221D Little Elephant and Array

Duilib中list控件支持ctrl和shif多行选中的实现

[ICML2015]Batch Normalization:Accelerating Deep Network Training by Reducing Internal Covariate Shif

win10系统微软输入法于eclipse ctrl+shif+f冲突间接处理办法

Codeforces Round #259 (Div. 2) B. Little Pony and Sort by Shif

读LDD3，内存映射与DMA--PAGE_SHIF…

VMware虚拟机安装XP【要先分区，再设置BOOT 启动CD，shif+上移】

更换iBus五笔的左与右Shif

sublime ctrl+shif+f 没用解决办法

idea 对 ctrl + z 的撤销是 ctrl + shif + z

计算机最早的设计师应用于,计算机应用基础选择题doc.doc

win10自带截图神器：Win+Shift+S

Python基础之文件目录操作

python简述目录_Python基础之文件目录操作(示例代码)

tp5 如何做数据采集

任务2-7(服务器字体+阿里巴巴矢量库)

html标签（1)：h1~h6,p,br,pre,hr

TI 电量计介绍与芯片选型指南

几款TI电源芯片简介

TI DSP芯片C2000系列读取FLASH数据

德州仪器(Ti)平台嵌入式开发基础

TI三相电机智能栅极驱动芯片特点分类

省选模拟（12.08） T3 圈圈圈圈圈圈圈圈

Hadoop生态圈技术栈（上）

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之6.Impala交互式查询

小猿圈之Linux下Mysql 操作命令

大数据Hadoop生态圈常用面试题

大数据开发基础入门与项目实战（三）Hadoop核心及生态圈技术栈之4.Hive DDL、DQL和数据操作

备战Noip2018模拟赛11（B组）T3 Monogatari 物语

【智能优化算法-圆圈搜索算法】基于圆圈搜索算法Circle Search Algorithm求解单目标优化问题附matlab代码

NYOJ 78 圈水池

递归问题跑道汽车绕圈问题 Python实现

Hadoop生态圈（三）：MapReduce

Codeforces Round #136 (Div. 2)D(codeforces221d) 暴力！！！！

相关文章