#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)
{
if(val == 1)
{
treeans[v] = 0;
}
else
{
treeans[v] = 1;
}
treeleft[v].clear();
treeright[v].clear();
if(val != 1)
{
treeleft[v].push_back({l, val});
treeright[v].push_back({r, val});
}
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();
int len1 = treeleft[v * 2].size();
if(treeleft[v * 2 + 1].size() > 0 && len1 > 0 && treeleft[v * 2][len1 - 1].first == (r + l) / 2 && __gcd(treeleft[v * 2][len1 - 1].second, treeleft[v * 2+ 1][0].second) == treeleft[v * 2][len1 - 1].second)
{
int a = treeleft[v * 2].back().second;
for(int i = 0; i < treeleft[v * 2].size() - 1; i++)
{
treeleft[v].push_back(treeleft[v * 2][i]);
}
for(int i = 0; i < treeleft[v * 2 + 1].size(); i++)
{
int d = __gcd(a, treeleft[v * 2 + 1][i].second);
if(d == 1){
break;
}
if(i < treeleft[v * 2 + 1].size() -1 && __gcd(treeleft[v * 2 + 1][i + 1].second, a) == d)
{
continue;
}
treeleft[v].push_back({treeleft[v * 2 + 1][i].first, d});
}
}
else if(len1 > 0 && treeleft[v * 2].size() > 0 && treeleft[v * 2].back().first == (r + l) / 2)
{
int a = treeleft[v * 2].back().second;
for(int i = 0; i < treeleft[v * 2].size(); i++){
treeleft[v].push_back(treeleft[v * 2][i]);
}
for(int i = 0; i< treeleft[v * 2 + 1].size(); i++)
{
int d = __gcd(a, treeleft[v * 2 + 1][i].second);
if(d == 1){
break;
}
if(i < treeleft[v * 2 + 1].size() - 1 && __gcd(treeleft[v * 2 + 1][i + 1].second, a) == d)
{
continue;
}
treeleft[v].push_back({treeleft[v * 2 + 1][i].first, d});
}
}
else
{
for(int i = 0; i < treeleft[v * 2].size(); i++)
{
treeleft[v].push_back(treeleft[v * 2][i]);
}
}
int len2 = treeright[v * 2 + 1].size();
if(len2 > 0 && treeright[v * 2].size() > 0 && treeright[v * 2 + 1].back().first == (r + l) / 2 + 1 && __gcd(treeright[v * 2 + 1].back().second, treeright[v * 2][0].second) == treeright[v * 2 + 1].back().second)
{
int a = treeright[v * 2 + 1].back().second;
for(int i = 0; i < treeright[v * 2 + 1].size() - 1; i ++)
{
treeright[v].push_back(treeright[v * 2 + 1][i]);
}
for(int i = 0; i < treeright[v * 2].size(); i++)
{
int d = __gcd(a, treeright[v * 2][i].second);
if(d == 1)
{
break;
}
if(i < treeright[v * 2].size() - 1 && __gcd(treeright[v * 2][i + 1].second, a) == d)
{
continue;
}
treeright[v].push_back({treeright[v * 2][i].first, d});
}
}
else if(len2 > 0 && treeright[v * 2].size() > 0 && treeright[v * 2 + 1].back().first == (r + l) / 2 + 1)
{
int a = treeright[v * 2 + 1].back().second;
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
{
treeright[v].push_back(treeright[v * 2 + 1][i]);
}
for(int i = 0; i < treeright[v * 2].size(); i++)
{
int d = __gcd(a, treeright[v * 2][i].second);
if(d == 1)
{
break;
}
if(i < treeright[v * 2].size() - 1 && __gcd(treeright[v * 2][i + 1].second, a) == d)
{
continue;
}
treeright[v].push_back({treeright[v * 2][i].first, d});
}
}
else
{
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
{
treeright[v].push_back(treeright[v * 2 + 1][i]);
}
}
treeans[v] = treeans[v * 2] + treeans[v * 2 + 1];
int j = -1;
for(int i = treeright[v * 2].size() - 1; i >= 0; i--)
{
while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
{
j++;
}
if(j != -1)
{
if(i == 0)
{
treeans[v]+= 1LL * ((r + l) / 2 + 1 - treeright[v * 2][i].first) * (treeleft[v * 2 + 1][j].first - (r + l) / 2);
}
else
{
treeans[v] += 1LL * (treeright[v * 2][i - 1].first - treeright[v * 2][i].first) * (treeleft[v * 2 + 1][j].first - (r + l ) / 2);
}
}
}
}
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);
if(al <= (r + l) / 2 && ar > (r + l) / 2)
{
int j = -1;
for(int i = treeright[v * 2].size() - 1; i >= 0; i--)
{
while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
{
j++;
}
if(j != -1)
{
if(i == 0)
{
sum += 1LL * ((r + l) / 2 + 1 - max(al, treeright[v * 2][i].first)) * (min(ar, treeleft[v * 2 + 1][j].first) - (r + l) / 2);
}
else
{
sum += 1LL * (max(al, treeright[v * 2][i - 1].first) - max(al, treeright[v * 2][i].first)) * (min(ar, treeleft[v * 2 + 1][j].first) - (r + l ) / 2);
}
}
}
}
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:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2].size() - 1; i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:55:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < treeleft[v * 2 + 1].size() -1 && __gcd(treeleft[v * 2 + 1][i + 1].second, a) == d)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2].size(); i++){
~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i< treeleft[v * 2 + 1].size(); i++)
~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:74:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < treeleft[v * 2 + 1].size() - 1 && __gcd(treeleft[v * 2 + 1][i + 1].second, a) == d)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2 + 1].size() - 1; i ++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:103:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < treeright[v * 2].size() - 1 && __gcd(treeright[v * 2][i + 1].second, a) == d)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:113:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:124:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i < treeright[v * 2].size() - 1 && __gcd(treeright[v * 2][i + 1].second, a) == d)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:133:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:142:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp: In function 'long long int ans(int, int, int, int, int)':
garaza.cpp:173:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j + 1 < treeleft[v * 2 + 1].size() && __gcd(treeleft[v * 2 + 1][j + 1].second, treeright[v * 2][i].second) != 1)
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
640 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1536 KB |
Output is correct |
| 3 |
Correct |
22 ms |
2292 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
95 ms |
7932 KB |
Output is correct |
| 2 |
Correct |
112 ms |
12152 KB |
Output is correct |
| 3 |
Correct |
163 ms |
11768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
249 ms |
19320 KB |
Output is correct |
| 2 |
Correct |
293 ms |
20700 KB |
Output is correct |
| 3 |
Correct |
359 ms |
23288 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
489 ms |
38200 KB |
Output is correct |
| 2 |
Correct |
539 ms |
40568 KB |
Output is correct |
| 3 |
Correct |
589 ms |
38392 KB |
Output is correct |
