-
Notifications
You must be signed in to change notification settings - Fork 0
/
1791 F. Range Update Point Query.cpp
155 lines (154 loc) · 4.59 KB
/
1791 F. Range Update Point Query.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
problem link: https://codeforces.com/contest/1791/problem/F
my solution on codeforces :https://codeforces.com/contest/1791/submission/192819736
problem name: F. Range Update Point Query
status: accepted
author: LELLO
*/
#include <bits/stdc++.h>
#include <iostream>
#include <chrono>
#include <vector>
#include <set>
#include <map>
#include<math.h>
#include <stack>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <utility>
#include <string>
#include <cctype>
#include <iomanip>
#include <numeric> // for NTH
#define bye return;
#define endl '\n'
#define ll long long
#define li long int
#define lli long long int
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((x).size())
#define ison(num, bit) (num & (1 << bit))
#define setoffif(num, bit) (num ^= (1 << bit)) // iff (num &(1<<bit))
#define setoff(num, bit) (num &= ~(1 << bit))
#define seton(num, bit) (num |= (1 << bit))
#define flipbit(num, bit) (num ^= (1 << bit))
#define LSB(num) (num & (-num))
#define pop_count_int(num) __builtin_popcount(num)
#define pop_count_l(num) __builtin_popcountl(num)
#define pop_count_ll(num) __builtin_popcountll(num)
#define clz(num) __builtin_clz(num)
#define clzll(num) __builtin_clzll(num)
#define ctz(num) __builtin_ctz(num)
#define ctzll __builtin_ctzll
#define Num_of_Digits(n) ((ll)log10(n) + 1)
#define ceill(n, m) (((n) / (m)) + (((n) % (m) ) ? 1 : 0))
#define lastOne(x) (__builtin_clzll(x))
#define fixed(n) fixed << setprecision(n)
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
#define Pi 3.14159265358979323846264
#define INF 0x3f3f3f3f
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define M 32
ll sgn(ll x){ if(x > 0) return 1; if(x < 0) return -1; return 0;}
ll mod = 1e9 + 7;
ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
const ll llmin = -1e18 ;
const ll llmax = 1e18 ;
const int imin = -1e9 ;
const int imax = 1e9 ;
const int N = 2e5 ;
using namespace std;
void AC() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); // or cin.tie(NULL)
cout.tie(nullptr); // or cout.tie(0)
}
void file_set(){ //string& file_name
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// freopen((file_name+".in").c_str(), "r", stdin);
// freopen((file_name+".out").c_str(), "w", stdout);
}
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
return (a.second < b.second);
}
// THOSE WHO CAN'T REMEMBER THE PAST'RE CONDEMNED TO REPEAT IT (USE DP -_-) - George Santayana
// PUSH HARDER THAN YESTERDAY IF YOU WANT A DIFFERENT TOMORROW !
//YOU DON'T HAVE TO BE A GENIUS , YOU NEED TO BE DETERMINED .
const ll int MAX = 1e5;
ll int dp[MAX] ;
const ll LOO = 0x3f3f3f3f3f3f3f3f;
const int OO = 0x3f3f3f3f;
ll conv(ll a){
string s = to_string(a);
ll sum(0) ;
for (auto x : s)
{
sum+=( x-'0' );
}
return sum ;
}
void LELLO(){
ll n , q ; cin >> n >> q ;
vector<ll> vc(n);
set <ll> st ;
for (int i = 0; i < n; i++)
{
cin >> vc[i] ;
if(vc[i] > 9) st.insert(i) ;
}
for (int i = 0; i < q; i++)
{
int x ; cin >> x ;
if(x == 1){
ll l , r ; cin >> l >> r ;
l--;
r--;
auto it = st.lower_bound(l);
while (it != st.end() && *it <= r)
{
vc[*it] = conv(vc[*it]);
if(vc[*it] < 10){
ll xx = *it ;
st.erase(it);
it = st.lower_bound(xx);
}else it++;
}
}else{
ll y ; cin >> y ;
cout<< vc[--y] <<endl;
}
}
}
void driver(ll t=1)
{
while (t--) LELLO();
Time
}
signed main()
{
AC();
// file_set();
ll test ; cin >> test ;
// chrono::time_point<chrono::system_clock> start, end;
// start = chrono::system_clock::now();
driver(test);
// end = chrono::system_clock::now();
// chrono::duration<double> elapsed_seconds = end - start;
// time_t end_time = chrono::system_clock::to_time_t(end);
// cout << "finished computation at " << ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "s\n";
}