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

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;
}