#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);
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;
}
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 = treeleft[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);
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;
}
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]);
}
}
if(treeleft[v].size() > 30 || treeright[v].size() > 30)
{
cout << "A";
exit(0);
}
treeans[v] = treeans[v * 2] + treeans[v * 2 + 1];
int j = -1;
for(int i = 0; i < treeright[v * 2].size(); 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 == treeright[v * 2].size() - 1)
{
treeans[v]+= ((r + l) / 2 + 1 - treeright[v * 2][i].first) * (treeleft[v * 2 + 1][j].first - (r + l) / 2);
}
else
{
treeans[v] += (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);
int j = -1;
if(treeright[v * 2].size() > 30 || treeleft[v * 2 + 1].size() > 30)
{
cout << "A";
exit(0);
}
for(int i = 0; i < treeright[v * 2].size(); 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 == treeright[v * 2].size() - 1)
{
sum += ((r + l) / 2 + 1 - max(al, treeright[v * 2][i].first)) * (min(ar, treeleft[v * 2 + 1][j].first) - (r + l) / 2);
}
else
{
sum += (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:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2].size(); i++){
~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i< treeleft[v * 2 + 1].size(); i++)
~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:72:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeleft[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:81: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:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:124: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:130:10: 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:156:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < treeright[v * 2].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~~
garaza.cpp:158: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:164:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == treeright[v * 2].size() - 1)
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
11520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
22656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
