#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector <vector <pair <int, int> > > treeleft, treeright;
vector <ll> treeans;
bool cmp(pair <int, int> a, pair <int, int> b)
{
return a.second < b.second;
}
void update(int v, int l, int r, int ind, int val)
{
if(l == r){
treeleft[v].clear();
treeright[v].clear();
if(val == 1){
treeans[v] = 0;
}
else
{
treeans[v] = 1;
}
int val1 = val;
for(int j = 2; j * j <= val; j++)
{
if(val1 % j == 0)
{
treeleft[v].push_back({j, l});
treeright[v].push_back({j, l});
}
while(val1 % j == 0)
{
val1 = val1 / j;
}
}
if(val1 != 1)
{
treeleft[v].push_back({val1, l});
treeright[v].push_back({val1, r});
}
return;
}
if(ind <= (r + l) / 2)
{
update(v * 2, l, (r + l) / 2, ind, val);
}
else
{
update(v * 2 + 1, (r + l) / 2 + 1, r, ind, val);
}
treeleft[v].clear();
treeright[v].clear();
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
{
if(treeright[v * 2 + 1][i].second == (r + l) / 2 + 1)
{
int ind = lower_bound(treeright[v * 2].begin(), treeright[v * 2].end(), make_pair(treeright[v * 2 + 1][i].first, 0)) - treeright[v * 2].begin();
if(ind == treeright[v * 2].size() || treeright[v * 2][ind].first != treeright[v * 2 + 1][i].first)
{
treeright[v].push_back(treeright[v * 2 + 1][i]);
}
else
{
treeright[v].push_back(treeright[v * 2][ind]);
}
}
else
{
treeright[v].push_back(treeright[v * 2 + 1][i]);
}
}
for(int i = 0; i < treeleft[v * 2].size(); i++)
{
if(treeleft[v * 2][i].second == (r + l) / 2)
{
int ind = lower_bound(treeleft[v * 2 + 1].begin(), treeleft[v * 2 + 1].end(), make_pair(treeleft[v * 2][i].first, 0)) - treeleft[v * 2 + 1].begin();
if(ind == treeleft[v * 2+ 1].size() || treeleft[v * 2 + 1][ind].first != treeleft[v * 2][i].first)
{
treeleft[v].push_back(treeleft[v * 2][i]);
}
else
{
treeleft[v].push_back(treeleft[v * 2 + 1][ind]);
}
}
else
{
treeleft[v].push_back(treeleft[v * 2][i]);
}
}
treeans[v] = treeans[v * 2] + treeans[v * 2 + 1];
sort(treeright[v * 2].begin(), treeright[v * 2].end(), cmp);
int minl = 0;
for(int i = 0; i < treeright[v * 2].size(); i++)
{
int iter = lower_bound(treeleft[v * 2 + 1].begin(), treeleft[v * 2 + 1].end(), make_pair(treeright[v * 2][i].first, 0)) - treeleft[v * 2 + 1].begin();
if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == treeright[v * 2][i].first)
{
minl = max(minl, treeleft[v * 2 + 1][iter].second - (r + l) / 2);
}
if(i != treeright[v * 2].size() - 1)
{
treeans[v] += 1LL * (treeright[v * 2][i + 1].second - treeright[v * 2][i].second) * minl;
}
else
{
treeans[v] += 1LL * ((r + l) / 2 + 1 - treeright[v * 2][i].second) * minl;
}
}
sort(treeright[v * 2].begin(), treeright[v * 2].end());
}
ll ans(int v, int l, int r, int al, int ar)
{
if(l >= al && r <= ar)
{
return treeans[v];
}
else if(l <= ar && r >= al)
{
ll sum = ans(v * 2, l, (r + l) / 2, al, ar) + ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar);
vector <pair <int, int> > vec;
for(int i = 0; i < treeright[v * 2].size(); i++)
{
vec.push_back({treeright[v * 2][i].first, max(al, treeright[v * 2][i].second)});
}
sort(vec.begin(), vec.end(), cmp);
int minl = 0;
for(int i = 0; i < vec.size(); i++)
{
int iter = lower_bound(treeleft[v * 2 + 1].begin(), treeleft[v * 2 + 1].end(), make_pair(vec[i].first, 0)) - treeleft[v * 2 + 1].begin();
if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == vec[i].first)
{
minl = max(minl, treeleft[v * 2 + 1][iter].second - (r + l) / 2);
}
minl = min(minl, ar - (r + l) / 2);
if(i != vec.size() - 1)
{
sum += 1LL * (vec[i + 1].second - vec[i].second) * minl;
}
else
{
sum += 1LL * ((r + l) / 2 + 1 - vec[i].second) * minl;
}
}
return sum;
}
else
{
return 0;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, q;
cin >> n >> q;
treeleft.resize(4 * n);
treeright.resize(4 * n);
treeans.resize(4 * n);
vector <int> a(n);
for(int i = 0; i < n; i++)
{
cin >> a[i];
update(1, 0, n - 1, i, a[i]);
}
while(q--)
{
int type;
cin >> type;
if(type == 1)
{
int x, v;
cin >> x >> v;
x--;
update(1, 0, n - 1, x, v);
}
else
{
int l, r;
cin >> l >> r;
l--;
r--;
cout << ans(1, 0, n - 1, l, r) << "\n";
}
}
return 0;
}
Compilation message
garaza.cpp: In function 'void update(int, int, int, int, int)':
garaza.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:58:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind == treeright[v * 2].size() || treeright[v * 2][ind].first != treeright[v * 2 + 1][i].first)
~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:77:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ind == treeleft[v * 2+ 1].size() || treeleft[v * 2 + 1][ind].first != treeleft[v * 2][i].first)
~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == treeright[v * 2][i].first)
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:101:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != treeright[v * 2].size() - 1)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp: In function 'long long int ans(int, int, int, int, int)':
garaza.cpp:122:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:128:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); i++)
~~^~~~~~~~~~~~
garaza.cpp:131:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(iter != treeleft[v * 2 + 1].size() && treeleft[v * 2+ 1][iter].first == vec[i].first)
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:136:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i != vec.size() - 1)
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4065 ms |
11260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2580 ms |
20796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4050 ms |
40628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
