#include "bits/stdc++.h"
using namespace std;
inline long long gcd(long long a , long long b){
while(b){
long long temp = a - b * (a / b);
a = b;
b = temp;
}
return a;
}
int n , m , q , type , x , y , X , Y;
long long value;
struct node{
long long val;
node *left , *beech , *right;
node(){
val = 0LL;
left = beech = right = NULL;
}
long long query(int l , int r , int ql , int qr){
if(r < l || l > qr || r < ql)
return 0LL;
if(l >= ql && r <= qr)
return val;
int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
return gcd((beech == NULL ) ? 0 : beech -> query(mid1 + 1 , mid2 , ql , qr) , gcd((left == NULL) ? 0 : left -> query(l , mid1 , ql , qr) ,(right == NULL) ? 0 : right -> query(mid2 + 1 , r , ql , qr)));
}
node* update(int l , int r , int idx , bool leaf , node *ll , node *bb , node*rr){
if(l == r)
if(leaf)
val = value;
else
val = gcd((ll == NULL) ? 0 : ll -> val , gcd((bb == NULL) ? 0 : bb -> val , (rr == NULL) ? 0 : rr -> val));
else{
int mid1 = l + (r - l + 1) / 3 , mid2 = r - (r - l + 1) / 3;
if(idx <= mid1){
if(left == NULL)
left = new node();
left = left -> update(l , mid1 , idx , leaf , (ll == NULL) ? NULL : ll -> left , (bb == NULL) ? NULL : bb -> left , (rr == NULL) ? NULL : rr -> left);
}
else if(idx <= mid2){
if(beech == NULL)
beech = new node();
beech = beech -> update(mid1 + 1 , mid2 , idx , leaf , (ll == NULL) ? NULL : ll -> beech , (bb == NULL) ? NULL : bb -> beech , (rr == NULL) ? NULL : rr -> beech);
}
else{
if(right == NULL)
right = new node();
right = right -> update(mid2 + 1 , r , idx , leaf , (ll == NULL) ? NULL : ll -> right , (bb == NULL) ? NULL : bb -> right , (rr == NULL) ? NULL : rr -> right);
}
val = gcd((beech == NULL) ? 0LL : beech -> val , gcd((left == NULL) ? 0LL : left -> val , (right == NULL) ? 0LL : right -> val));
}
return this;
}
};
struct nodex{
long long val;
node *ychild;
nodex *left , *beech , *right;
nodex(){
val = 0LL;
ychild = NULL;
left = right = beech = NULL;
}
long long queryx(int l , int r , int x1 , int y1 , int x2 , int y2){
if(r < l || l > x2 || r < x1 || ychild == NULL)
return 0LL;
if(l >= x1 && r <= x2)
return ychild -> query(0 , m - 1 , y1 , y2);
int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
return gcd((beech == NULL) ? 0 : beech -> queryx(mid1 + 1 , mid2 , x1 , y1 , x2 , y2) , gcd((left == NULL) ? 0 : left -> queryx(l , mid1 , x1 , y1 , x2 , y2) ,(right == NULL) ? 0 : right -> queryx(mid2 + 1 , r , x1 , y1 , x2 , y2)));
}
nodex* update(int l , int r , int idx , int idy){
if(ychild == NULL)
ychild = new node();
if(l == r)
ychild = ychild -> update(0 , m - 1 , idy , 1 , NULL , NULL , NULL);
else{
int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
if(idx <= mid1){
if(left == NULL)
left = new nodex();
left = left -> update(l , mid1, idx , idy);
}
else if(idx <= mid2){
if(beech == NULL)
beech = new nodex();
beech = beech -> update(mid1 + 1 , mid2 , idx , idy);
}
else{
if(right == NULL)
right = new nodex();
right = right -> update(mid2 + 1 , r , idx , idy);
}
ychild = ychild -> update(0 , m - 1 , idy , 0 , (left == NULL) ? NULL : left -> ychild ,(beech == NULL) ? NULL : beech -> ychild ,(right == NULL) ? NULL : right -> ychild);
}
return this;
}
};
nodex * root = new nodex();
/*int main(){
scanf("%d %d %d" , &n , &m , &q);
while(~scanf("%d" , &type)){
if(type & 1){
scanf("%d %d %lld" , &x , &y , &value);
root = root -> update(0 , n - 1 , x , y);
}
else{
scanf("%d %d %d %d" , &x , &y , &X , &Y);
printf("%lld\n" , root -> queryx(0 , n - 1 , x , y , X , Y));
}
}
}*/
void init(int R, int C) {
n = R, m = C;
}
void update(int P, int Q, long long K) {
//cout << "upd\n";
value = k;
root = root -> update(0 , n - 1 , P, Q);
}
long long calculate(int P, int Q, int U, int V) {
//cout << "calc\n";
return root -> queryx(0 , n - 1 , P , Q , U , V)
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^
game.cpp: In function 'void update(int, int, long long int)':
game.cpp:121:10: error: 'k' was not declared in this scope
value = k;
^
game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:128:1: error: expected ';' before '}' token
}
^
