2023牛寒1--鸡格线CF Round #849 (Div. 4)--F. Range Update Point Query

article/2023/12/3 1:42:52

2023牛寒1--鸡格线

你有一个长为n的数组a,你需要支持以下两种操作:
1、输入l,r,k,对区间[l,r]中所有数字执行ai=f(ai)操作kkk次(式中等号表示赋值操作),之中f(x)=round(10x),round为四舍五入函数。
2、输出当前数组所有数字的和,你需要正确处理m次这样的操作。

输入描述:
输入第一行包含两个整数n,m(1≤n,m≤10^5),表示数组长度与操作次数。
接下来一行输入n个整数,第i个整数ai(0≤ai≤10^9)表示数组第i个数。
接下来m行,每行先输入一个操作类别op(op∈{1,2}),表示两类操作之一,若op=1,则继续输入三个整数l,r,k(1≤l≤r≤n,1≤k≤10^5),含义如题目所示。

输出描述:

对于所有第二类操作,输出一个整数表示当前数组所有数字的和。

输入:

3 5
0 2 114514
2
1 1 2 2
2
1 1 3 1
2

输出:

114516
114551
3445

结论:1~1e9之间的数最多不超过20次f( )就可以变为一个定值。

解析:由结论,我们可以利用set来存那些还没有成为定值的数,然后每次操作1,我们在set中找到合法的区间,将其进行f( )操作,如果操作之后它变成了一个定值,就将他从set中删除,期间更新下sum和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N];
int f(int x)
{return round(sqrt(x)*10);
}
set<int> st;
int main()
{int n,m;scanf("%d%d",&n,&m);ll sum=0;for(int i=1;i<=n;i++){scanf("%lld",&a[i]);sum+=a[i];if(f(a[i])!=a[i]) st.insert(i);//如果还不是定值,存入set}st.insert(n+1);//存一个最大值,后面就方便点,不用特判while(m--){int op;scanf("%d",&op);if(op==1){int l,r,k;scanf("%d%d%d",&l,&r,&k);while(1){int pos=(*st.lower_bound(l));if(pos>r) break;//不在区间中了,直接退出for(int i=1;i<=min(k,20);i++){sum-=a[pos];a[pos]=f(a[pos]);sum+=a[pos];}if(a[pos]==f(a[pos])) st.erase(pos);//如果已经成为定值,就从set中删除l=pos+1;}}else printf("%lld\n",sum);}return 0;
}

CF Round #849 (Div. 4)--F. Range Update Point Query

Given an array a1,a2,…,an, you need to handle a total of q updates and queries of two types:

  • 1 l r — for each index ii with l≤i≤r, update the value of ai to the sum of the digits of ai.
  • 2 x — output ax.

Input

The first line of the input contains an integer t (1≤t≤1000) — the number of testcases.

The first line of each test case contains two integers nn and q (1≤n,q≤2⋅10^5) — the size of the array and the number of queries, respectively.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9).

The next q lines of each test case are of two forms:

  • 1 l r (1≤l≤r≤n) — it means, for each index ii with l≤i≤r, you should update the value of ai to the sum of its digits.
  • 2 x (1≤x≤n) — it means you should output ax.

There is at least one query of the second type.

The sum of n over all test cases does not exceed 2⋅10^5.

The sum of q over all test cases does not exceed 2⋅10^5.

Output

For each test case, output the answers of queries of the second type, in the order they are given.

输入:

3
5 8
1 420 69 1434 2023
1 2 3
2 2
2 3
2 4
1 2 5
2 1
2 3
2 5
2 3
9999 1000
1 1 2
2 1
2 2
1 1
1
2 1

输出:

6
15
1434
1
6
7
36
1
1

解析:两道题几乎一模一样😯,就是f( )函数改一下,加上多组测试就可以。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200005];
int f(int x)
{int sum=0;while(x) sum+=x%10,x/=10;return sum;
}
set<int> st;
void solve()
{int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);if(f(a[i])!=a[i]) st.insert(i);}st.insert(n+1);while(m--){int op;scanf("%d",&op);if(op==1){int l,r;scanf("%d%d",&l,&r);while(1){int pos=(*st.lower_bound(l));if(pos>r) break;a[pos]=f(a[pos]);if(a[pos]==f(a[pos])) st.erase(pos);l=pos+1;}}else{int x;scanf("%d",&x);printf("%lld\n",a[x]);}}st.clear();
}
int main()
{int t;scanf("%d",&t);while(t--) solve();return 0;
}

http://www.ngui.cc/article/show-861290.html

相关文章

通用视觉框架OpenMMLab图像分类与基础视觉模型

文章目录流程传统方法&#xff1a;设计图像特征(1990s~2000s)特征工程的天花板从特征工程到特征学习层次化特征的实现方式AlexNet 的诞生& 深度学习时代的开始图像分类的数学表示AlexNet (2012)Going Deeper (2012~2014)VGG (2014)GoogLeNet (Inception v1, 2014)精度退化问…

【Linux】Linux中的特权 | SUID | Linux Capabilities

1.获得特权的两种方式 Linux中&#xff0c;特权任务&#xff08;privileged tasks&#xff09;可以通过两种方式执行&#xff1a; Using SUID Using capabilities 2.关于SUID 通过SUID拿到root权限&#xff0c;参考 https://blog.csdn.net/qq_39441603/article/details/125…

零碎的算法笔记(1)

From算法竞赛入门经典 第2版1.判断 n 是否为完全平方数2. 比较大的数组应尽量声明在 main 函数外&#xff0c;否则程序可能无法运行 3.开灯问题1.判断 n 是否为完全平方数 可以先求出其平方根&#xff0c;然后看它是否为整数&#xff0c;即用一个 int 型变量 m 存储 sqrt(n&am…

分享115个图片切换JS特效,总有一款适合您

分享115个图片切换JS特效&#xff0c;总有一款适合您 115个图片切换JS特效下载链接&#xff1a;https://pan.baidu.com/s/1QX7b5LDlY6lBqMVjgBKSwA?pwdk05d 提取码&#xff1a;k05d Python采集代码下载链接&#xff1a;https://wwgn.lanzoul.com/iKGwb0kye3wj jQuery多图…

嵌入式C语言基础

嵌入式开发中常用的C语言基础语法并不多&#xff0c;因此&#xff0c;对于想学习或者进入嵌入式领域的同学&#xff0c;可以通过快速学习常用的C语言基础&#xff0c;进而着手尝试开发小项目&#xff0c;在开发过程中不断扩展知识库。 嵌入式C语言基础1、const用法修饰变量/数组…

Appium+Python+pytest自动化测试框架

先简单介绍一下目录&#xff0c;再贴一些代码&#xff0c;代码里有注释Basic目录下写的是一些公共的方法&#xff0c;Data目录下写的是测试数据&#xff0c;image存的是测试失败截图&#xff0c;Log日志文件&#xff0c;Page测试的定位元素&#xff0c;report测试报告&#xff…

2023-02-01 读书笔记:《有趣的统计》-1-基础知识

2023-02-01 读书笔记&#xff1a;《有趣的统计》-1-基础知识 75招学会数据分析 —— 2014 Doctor.Bruce Frey 序 统计学&#xff1a; 最初&#xff0c;用于确定某些事情发生的可能性&#xff1b;不断发展&#xff0c;根据样本数据准确推断总体数据特征的方法&#xff08;推…

一文让你彻底懂Redis

1.NoSQL介绍 1.1 什么是NoSQL 非关系型数据库就是NoSQL&#xff0c;关系型数据库代表MySQL。 对于关系行数据库&#xff0c;是需要把数据存储到库、表、行、字段里&#xff0c;查询的时候根据条件一行一行地去匹配&#xff0c;当量非常大的时候就很耗费时间和资源&#xff0c…

4.6 Python元组

列表非常适合用于存储在程序运行期间可能变化的数据集。Python将不能修改的值称为不可变的&#xff0c;而不可变的列表被称为元组。4.5.1 定义元组元组看起来犹如列表&#xff0c;但使用圆括号而不是方括号来标识。定义元组后&#xff0c;就可以使用索引来访问其元素&#xff0…

车-电-路网时空分布负荷预测研究(Matlab代码)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…