Luogu T14448 区间开方
题面版权来自Shlw。题目链接
题目背景
无
题目描述
给定一个数列,元素均为正整数,对其以下两种操作:
1.将某区间每一个数变为其算术平方根(取整)
2.求出某区间内所有数的最大值
输入输出格式
输入格式:
第一行包含两个整数$n$,$m$,分别表示该数列数字的个数和操作的总个数。第二行包含n个用空格分隔的整数,表示给定的数列。接下来m行,每行包含3个整数,表示一个操作,具体如下:
操作1:1 $x$ $y$ 含义:将区间[$x$,$y$]内每个数进行开方。
操作2:2 $x$ $y$ 含义:输出区间[$x$,$y$]内所有数的最大值。
输出格式:
输出包含若干行整数,即为所有操作2的结果。
输入输出样例
9 7
71 25 69 41 75 91 12 76 24
1 1 2
1 1 2
1 1 1
1 3 7
2 9 9
1 7 7
2 1 2
24
2
说明
对于20%的数据,n,m<=1000。
对于60%的数据,n,m<=10000。
对于100%的数据,n,m<=200000。
数据全部随机。
题解:
20分做法:
直接暴力。复杂度O($n*m$)。
60分做法:
我不知道。网上有关于线段树处理区间开方区间求和的题,只是自己不会写,不知道能不能迁移到区间最值上。(其实是为了看起来有部分分才设置60%数据的)
100分做法:
注意到数据是较为随机的,也就是说$m$次操作中差不多有$m/2$次开方操作,区间随机时每个元素被开方$m/4$次。然而一个9位数开方几十次之后就会变成1,以后的所有开方操作都是毫无意义的。考虑到元素最小值为1,所以在查询最大值时也没有必要将1考虑进去。
总而言之,1是“无需处理的元素”,然而在$m$次操作后期序列中会出现很长很长的一段全为1的元素,可以在区间操作时考虑跳过。
关于跳过一些未来可能会合并但一定不会分裂的区间可以使用并查集。
与之相似的一道题: CodeVS 4874 染色 题目链接
设fa[i]为“i以及i以后第一个不为1的数的编号”。换句话说,若$a_i$不为1,则$fa_{i}=i$;若$a_i$为1,则$fa_{i}$为$i$后第一个不为1的数的编号。发现$fa$可以进行路径压缩,在处理开方和求$max$时,从$find(i)$开始,逐次开方或求$max$,处理后若当前元素为1,将当前元素与下一个进行合并,否则开始处理下一个元素。
复杂度:O(跑得过)(手动滑稽)
代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=2e5+10;
4 int a[maxn],fa[maxn];
5 int n,m;
6 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
7 void change(int l,int r)
8 {
9 int i,j;
10 i=l;
11 do
12 {
13 i=find(i);
14 if(i>r){break;}
15 a[i]=(int)(sqrt(a[i]));
16 if(a[i]==1){fa[i]=find(i+1);}
17 else{i++;}
18 }while(i<=r);
19 //for(i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;
20 }
21 void query(int l,int r)
22 {
23 int i=l,j,ans=1;
24 do
25 {
26 i=find(i);
27 if(i>r){break;}
28 ans=max(ans,a[i]);
29 if(a[i]==1){fa[i]=find(i+1);}
30 else{i++;}
31 }while(i<=r);
32 printf("%d\n",ans);
33 }
34 int main()
35 {
36 int i,j,flag,l,r;
37 //freopen("data.in","r",stdin);
38 //freopen("test.out","w",stdout);
39 cin>>n>>m;
40 for(i=1;i<=n;i++){scanf("%d",&a[i]);}
41 for(i=1;i<=n+1;i++){fa[i]=i;}
42 for(i=1;i<=m;i++)
43 {
44 scanf("%d%d%d",&flag,&l,&r);
45 if(flag==1){change(l,r);}
46 else{query(l,r);}
47 }
48 return 0;
49 }
最新文章
- 【淘淘】Quartz作业存储与管理
- WPS Office Pro 2016 专业版
- 用一个简单的例子来理解python高阶函数
- HighChats报表使用C#mvc导出本地图片
- 导入DXF文件
- 用MSBuild和Jenkins搭建持续集成环境(1)
- JS读取client端的文件的代码片段
- 解决CSDN的code功能,无法git clone多个项目的问题
- HTML5 程序设计笔记(一)
- 连接Xively云
- 分页:T-SQL存储过程和EF存储过程的使用
- Angular2入门-数据绑定
- lasy load图片的实现
- 2、FreeRTOS任务相关API函数
- PAT (Basic Level) Practice (中文)1001 害死人不偿命的(3n+1)猜想
- chat.css
- matlab数据导入verilog仿真
- 什么是物理像素、虚拟像素、逻辑像素、设备像素,什么又是 PPI, DPI, DPR 和 DIP
- 【PMP】组织级项目管理(OPM)和战略
- Delphi - 让Delphi10.2在Windows下开发的图形界面程序运行在64位Linux中!
热门文章
- 利用Python下载:You-Get的安装及使用方法
- Redis的sentinel(哨兵)部署
- nginx: [emerg] bind() to 0.0.0.0:80 failed (10013:
- Java并发包源码学习系列:挂起与唤醒线程LockSupport工具类
- 简单解析一下 Mybatis 常用的几个配置
- C语言补码(C语言学习笔记)
- Netty学习:伪共享
- Java中的NIO进阶
- jQuery库 之 jquery slimscroll插件使用
- TCP三次握手Linux源码解析