[HOJ 247][IOI 2008] Islands

作法：

首先當然是把所有連通塊分開看，這題簡單來說就是要找水母圖上的最長路（無向的），我們先找出這張水母圖的圈在哪裡，找法從隨便一個點開始沿著他唯一連出去的邊一直走，走到重複的點為止，就找到一個圈了。水母圖上的最長路分兩種，一種是沒有經過圈上的邊的，一種則是有的。對於前者，我們可以枚舉水母圈上的點，考慮這個點連往非水母圈的邊的那些點們，會形成一棵子樹，對這個子樹求最長路徑就可以了。至於經過水母圈上的邊的路徑，因為顯然如果我們已經決定好路徑和水母圈的交集的兩端點的話，剩下就取這個端點往他的子樹方向走過去的最長路就可以了，因此在回傳子樹內部的最長路時要順便回傳子樹根往下走的最長路。於是我們現在有圈上每個點往樹方向走下去的最長路了（以下稱為$val$值），還有圈上每條邊的長度，要求的是「兩點之間的距離$+$兩點的$val$值」的最大值。考慮把圈壓成序列，也就是如果原本圈上的點為$A_1,...,A_k$，考慮序列$A_1,...,A_k,A_{k+1},...,A_{2k-1}$，其中$A_{i+k}=A_i$，並且相鄰點的距離就和原本圈上連接這兩點的距離相等，記$dis[i]$代表$A_1$往右走到$A_i$的距離，和$val[i]$代表$A_i$的 val 值（最長路長），那麼我們要求的東西就是：$(i,j)$滿足$dis[i]-dis[j]+val[i]+val[j]$最大，其中$i-j<k$。因此當固定$i$的時候，我們需要的東西就會是$max\{ val[j]-dis[j] \}$，其中$j=i-k+1,...,i-1$。於是這就可以用 deque 優化在線性的時間內求出來了。

最後我傳上去 MLE 了，載測資來看發現那兩筆是DFS會到$10^6$層左右的，後來我把DFS改成自己用 stack 作才過的，感覺 IOI 沒必要這樣卡記憶體阿OAO......

code :

[HOJ 251][IOI 2008] Pyramid Base

作法：

首先考慮二分搜答案，因為如果能夠在預算內放入邊長$x$的正方形，那顯然可以放入邊長$x-1$的正方形。當確定一個邊長時，我們想要知道他可不可行，而只要注意到：我們只要決定好正方形的左上角就可以了，並且對於平面上的某個障礙物來說，考慮那些「用來當正方形左上角的話會和這個障礙物有交集的格子」，不難發現這些格子形成一個長方形（其座標不難求），因此就可以想成：如果左上角放在這個長方形裡，就要多花（這個長方形的 cost ）元。並且我們想知道這個平面上花費最少的格子是否在預算之中。因此就轉換為經典問題了：給定平面上的一些長方形，每個長方形都把內部的格子同加某個值，求整個平面的最小值是多少。這就顯然可以用掃描線+線段樹做了。

但這樣傳上去TLE了，畢竟$O(nlog^2n)$對$n\leq 400000$來說太大了。但注意到剩下只有$B=0$的情形，因此可以思考另外一種算法。考慮對於每個左界$i$，都找出最大的右界$j$，使得存在一個空的正方形，他的左右界分別為$i$和$j$。注意到如果我們把$i$到$j$這幾排全部壓成一排，並且「有和$i$到$j$交集的障礙物」都被壓成一排中的區間，那麼就變成詢問這一排中有最多連續幾個格子沒有障礙物了。因此我們可以把有交集到的障礙物的兩個$y$座標看成「把這兩數之間的所有數的位置的值都$+1$」，並且詢問的是這個數列裡有最多多少個連續的$0$，因此可以用線段樹做。這樣我們得到了$O(n^2logn)$的算法，也就是對於每個左界$i$直接一個一個往右擴展，當多遇到一個障礙物的左界，就在該區間$+1$的地方$+1$，直到查詢出來的值無法在兩邊界之間形成正方形為止。但只要注意到：如果存在一個正方形的左右邊界是$i,j$，那麼也存在左右邊界是$i+1,j$的。因此就可以改成用雙指標掃過去一次就可以了。複雜度降為$O(nlogn)$

最後提一下，這裡的線段樹必須支援：區間加$1$，區間減$1$和查詢最大連續的$0$數量，作法和「求$n$個矩形在平面上的覆蓋面積」時掃描線所用的線段樹類似，可以參考這篇。

code :

[TIOJ 1837][IOI 2013] ArtClass

作法：

總之就是亂做一通 + 經過別人的提示才過的。我一開始還在想判白色區塊和黑色區塊的格子數，後來發現不行，改成判白色區塊和黑色區塊的最大矩形，後來發現也會爛掉。最後是改成看每個點和他的四個相鄰點，去計算有幾組相鄰點的顏色差到了某個程度以上，這樣可以成功把第二種圖和第三種圖分出來，因為第三種圖是最多的，第二種圖大概也有 1/4 ，剩下第一種和第四種要再分。

後來聽別人分第一種和第四種的方法是，去看有多少組相鄰點的顏色相差很多，第四種圖的組數會比第一種圖的少，但他們之間的分界我亂試了很久才過，還有判斷顏色相差很多的函式和判斷顏色是否一樣的函式我也是亂做的，後來得到的準確率好像是 90.3% ，總之就是亂寫過了。

另外，何達睿的作法是看每一個橫排的亂七八糟度(?)，code 附在下面，比我的簡潔好多QQ。還有周逸的作法是在多考慮綠色的多少，好像是看平方和之類的，如果特別多那就是第二種圖，沒有詳細聽他講，結果他就把我的CBD大頭貼判成第二種圖( 印象派風景畫 )了XDD

code :

#include<bits/stdc++.h>
#define DB double
#define MAX(x,y,z) max(x,max(y,z))
#define ADD(x,y,z) (x+y+z)
using namespace std;
const int maxn=1000 ;
 
int ABS(int x)
{
    return x>0 ? x : -x ;
}
 
int a[maxn][maxn][3] ;
bool same(int x1,int y1,int x2,int y2)
{
    int x=0 ;
    for(int i=0;i<3;i++)
    {
        x+=ABS(a[x1][y1][i]-a[x2][y2][i]) ;
        if(ABS(a[x1][y1][i]-a[x2][y2][i])>10) return 0 ;
    }
    return 1 ;
}
 
int dif(int x1,int y1,int x2,int y2)
{
    return ADD(ABS(a[x1][y1][0]-a[x2][y2][0]),
               ABS(a[x1][y1][1]-a[x2][y2][1]),
               ABS(a[x1][y1][2]-a[x2][y2][2])) ;
}
 
int n,m ;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1} ;
 
int solve()
{
    int cnt=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        for(int k=0;k<4;k++)
    {
        int nx=i+dx[k] , ny=j+dy[k] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(!same(i,j,nx,ny)) cnt++ ;
    }
 
    DB ans=cnt*100.0/4.0/n/m ;
    if(ans>=64.0) return 3 ;
    if(ans>=21.0) return 2 ;
 
    cnt=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        for(int k=0;k<4;k++)
    {
        int nx=i+dx[k] , ny=j+dy[k] ;
        if(nx<0||nx>=n||ny<0||ny>=m) continue ;
        if(dif(i,j,nx,ny)>180) cnt++ ;
    }
    if(cnt>7000) return 1 ;
    return 4 ;
}
 
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++) for(int j=0;j<m;j++)
            scanf("%d%d%d",&a[i][j][0],&a[i][j][1],&a[i][j][2]) ;
        printf("%d\n",solve()) ;
    }
}

看橫排的亂七八糟度的 code :

http://imgur.com/YCz2qBF

[HOJ 289][IOI 2013] Wombats

作法：

這題我也是查解才會做的。因為我們需要從第 0 排到第 R-1 排的 C*C 個答案的陣列，而這個答案陣列可以從 [ 0 , mid ] 的答案和 [ mid , R-1 ] 的答案算出來，所以就用一個線段樹，如果一個節點代表的區間是 [ l , r ] ，那麼這個節點就是紀錄第 l 到第 r 排的所有 C*C 個答案。那麼當我要用 [ l , mid ] 和 [ mid , r ] 的答案合併成 [ l , r ] 的答案時，最原始的方法就是對每個第 l 排的位置和第 r 排的位置都枚舉最佳路徑經過第 mid 排的哪個位置，這樣合併的時間是 O(C^3) ，並且當在修改的時候需要合併 log R 的線段樹上的區間，會TLE掉。但其實只要注意到他的最佳位置其實是有某種遞增性的，就是如果第 l 排的第 i 個到第 r 排的第 j 個中間經過的點的最佳位置是 X ，第 i+1 個到第 j+1 個中間經過的點的最佳位置是 Y ，那麼第 i 個到第 j+1 個中間的最佳位置就會在 X 和 Y 之間。大概可以感受到最佳解不會跑到外面，不然直接把兩條路徑交換會讓 i 到 j 的最佳路徑 ( 或 i+1 到 j+1 的最佳路徑 ) 不再是最佳路徑，就矛盾了。所以我們只要先 O(C^2) 算出第 i 個到第 i 個的最佳解和最佳位置，剩下的所有答案就可以用上面的方法在O(C^2)的時間內算出來，所以線段樹的兩個子節點的合併可以做到O(C^2)。這好像叫四邊形優化，但我沒有仔細讀過他在講甚麼QQ。

所以我們只要能算出葉節點的答案就好了( 葉節點的寬度都只有 1 )。所以現在等於是有 2 * C 個點，排成矩形的形狀，並且之間有連一些邊，要求上面C個的任意一點到下面C個的任意一點中間經過的最少數量，而這可以用DP做，考慮對每個上面的點都做一次到下面C個點的類似最短路的算法，並且因為他是特殊圖，可以做到O(C) ( 掃過來再掃過去XD )，所以計算葉節點的複雜度也是O(C^2)。

但這樣會發現線段樹必須開 10000*100*100 的陣列，會MLE掉，所以線段樹不能建得太深，就是先定好一個 K 值，到了線段樹的節點的區間長度 <= K 的時候就直接做這個區間的答案，不要到最底層才做，這樣可以節省記憶體，但會讓速度變慢。所以在葉節點的時候的計算答案的複雜度其實會變成 O(C^2 * len ) ，其中 len 是區間的長度。看網路上的題解是取 K = 15 ，所以就取跟他一樣的了。

（附上丁安立的精妙（？）解說： http://alt.twbbs.org/?p=3687 ）

code :

#include<bits/stdc++.h>
#define INF 1500000000
using namespace std;
const int maxn=5000+10 , maxc=100+2 , KK=15 ;
 
int n,m,ST[2000][maxc][maxc] ;
 
int dis[maxc] ;
void sweep_hor(int a[maxc],int h[maxc])
{
    dis[0]=0 ;
    for(int i=1;i<m;i++) dis[i]=dis[i-1]+h[i-1] ;
    int mi=INF ;
    for(int i=1;i<m;i++)
    {
        mi=min(mi, a[i-1]-dis[i-1]) ;
        a[i]=min(a[i],mi+dis[i]) ;
    }
    mi=INF ;
    for(int i=m-2;i>=0;i--)
    {
        mi=min(mi,a[i+1]+dis[i+1]) ;
        a[i]=min(a[i],mi-dis[i]) ;
    }
}
 
int H[maxn][maxc] , V[maxn][maxc] ;
 
void cal(int l,int r,int a[maxc][maxc])
{
    for(int i=0;i<m;i++) for(int j=l;j<=r;j++)
    {
        for(int k=0;k<m;k++)
            a[i][k]= j==l ? (i==k?0:INF) : (a[i][k]+V[j-1][k]) ;
        sweep_hor(a[i],H[j]) ;
    }
}
 
int K[maxc][maxc] ;
void merge(int a[maxc][maxc],int b[maxc][maxc],int c[maxc][maxc])
{
    for(int i=0;i<m;i++) for(int j=0;j<m;j++)
        c[i][j]=INF ;
    for(int i=0;i<m;i++) for(int j=0;j<m;j++)
        if(a[i][j]+b[j][i]<c[i][i])
            c[i][i]=a[i][j]+b[j][i] , K[i][i]=j ;
    for(int i=m-2;i>=0;i--) for(int j=i+1;j<m;j++)
        for(int k=K[i][j-1];k<=K[i+1][j];k++)
        if(a[i][k]+b[k][j]<c[i][j])
            c[i][j]=a[i][k]+b[k][j] , K[i][j]=k ;
    for(int i=1;i<m;i++) for(int j=i-1;j>=0;j--)
        for(int k=K[i-1][j];k<=K[i][j+1];k++)
        if(a[i][k]+b[k][j]<c[i][j])
            c[i][j]=a[i][k]+b[k][j] , K[i][j]=k ;
}
 
void build(int l,int r,int id)
{
    if(r-l<KK)
    {
        cal(l,r,ST[id]) ;
        return ;
    }
    int mid=(l+r)/2 ;
    build(l,mid,2*id) ;
    build(mid,r,2*id+1) ;
    merge(ST[2*id],ST[2*id+1],ST[id]) ;
}
 
void modify(int L,int R,int id,int pos)
{
    if(R-L<KK)
    {
        cal(L,R,ST[id]) ;
        return ;
    }
    int mid=(L+R)/2 ;
    if(pos<=mid) modify(L,mid,2*id,pos) ;
    else modify(mid,R,2*id+1,pos) ;
    merge(ST[2*id],ST[2*id+1],ST[id]) ;
}
 
void modify_hor(int x,int y,int val)
{
    H[x][y]=val ;
    modify(0,n-1,1,x) ;
    if(x<n-1) modify(0,n-1,1,x+1) ;
}
 
void modify_ver(int x,int y,int val)
{
    V[x][y]=val ;
    modify(0,n-1,1,x+1) ;
}
 
main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++) for(int j=0;j<m-1;j++) scanf("%d",&H[i][j]) ;
    for(int i=0;i<n-1;i++) for(int j=0;j<m;j++) scanf("%d",&V[i][j]) ;
    build(0,n-1,1) ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int op ; scanf("%d",&op) ;
        if(op==1)
        {
            int x,y,val ; scanf("%d%d%d",&x,&y,&val) ;
            modify_hor(x,y,val) ;
        }
        else if(op==2)
        {
            int x,y,val ; scanf("%d%d%d",&x,&y,&val) ;
            modify_ver(x,y,val) ;
        }
        else
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            printf("%d\n",ST[1][x][y]) ;
        }
    }
}
 

[HOJ 292][IOI 2013] Game

作法：

用線段樹套線段樹，考慮一棵線段樹，他的根的區間是 [ 0 , R-1 ] ，並且線段樹上的每個節點 ( 假設他代表的區間是 [ L , R ]  )，都代表一棵線段樹 st ，其中 st 的根的區間是 [ 0 , C-1 ] ， st 上的每個節點 ( 假設他代表的區間是 [ L2 , R2 ] ) 存的值就是第一個座標落在 [ L , R ] 裡且第二個座標落在 [ L2 , R2 ] 裡的所有數們的 gcd ( 就一個矩形區域 )。

我的實作上是對每個外層線段樹的節點再多放一個內層線段樹的 node 的指標，指向這個節點代表的線段樹。又因為如果直接先開好滿的線段樹顯然會MLE，所以要用動態開點的方法，當走到一個點時，如果這個節點是空的再 new 出來。而也是第一次走到這個節點的時候再開就好。

在區間查詢的時候比較好寫，很類似一維線段樹，但在修改的時候就比較麻煩。這時我們把每個節點都當成一坨資料結構會比較好理解，總之內層的線段樹就是一坨可以做「單點改值，區間查詢 gcd」的一維資料結構，所以就想像外層線段樹的每個節點都是一坨資料結構，然後我們要在修改值的時候維護好這好幾陀資料結構。

考慮現在要修改 ( x , y ) 這個點，那麼會先經過第一層線段樹的 logR 個節點 ( 他們代表的線段都包住 x )，這每個節點的資料結構都即將被修改到。考慮葉節點的資料結構，那麼單純地對他把位置 y 的值修改掉就完成了。接下來要做外層線段樹的 pull 操作 ( 就是用這個節點的兩個子節點的資料結構來更新自己的資料結構 )，因為這個資料結構只有座標為 y 的地方值有改掉，所以可以只對這個資料結構修改 y 座標的值，至於要把他修改成甚麼值，會發現這個值的算法就是先查詢左子節點的資料結構裡 y 位置的值，再查詢右子節點的資料結構裡 y 位置的值，然後把這兩個值取 gcd 就可以了。所以每次修改都會改到 logR 個資料結構，每次修改一個資料結構的時間是 logC ，所以單次修改的時間為 O( logC logR )。

很悲劇的是，這樣寫在 HOJ 可以獲得 60幾分 ( 或好像把甚麼東西寫好，然後把函式前面都加個 inline 可以衝到 80 之類的 )，剩下會MLE掉。所以這邊加了一個東西優化記憶體，大家把它叫作周逸 tag (?) 。就是當我們在實作內層的資料結構的時候，如果有一個區間裡只有一個數有值，那就沒有必要一直往下建新的節點到底了，所以可以另外加一個 tag 值代表這個區間裡是否只有一個數有值，如果否的話就設成某個負數，是的話就設成這個數的位置，並且和一般的 tag 一樣對一個區間的點修改的時候要先 push ，這樣最好狀況下可以省下 O( logC ) 的記憶體，但最差情況下還是沒有省到，因為如果一直修改兩個 y 座標很近的點的值記憶體還是會爛掉，所以其實是一個假解作法XD 。而且這樣當在做查詢操作的時候也可以省時間，因為如果目前的節點區間裡只有一個數有值，那就只要判斷詢問的區間是否包含他的位置就知道答案要回傳多少了，這樣就能成功 AC 了！

另外陳博彰寫的做法應該是這題的正解，就是讓內層的資料結構做的蠻像平衡樹的(但他還是線段樹)。例如根的區間是 [ 0 , 10 ] ，現在只有在 3 的區間改一個值，那麼現在線段樹就會變成有 [ 0 , 5 ] , [ 3 , 5 ] , [ 3 , 4 ] , [ 3 , 3 ] 這些節點，但是其實只有一個孩子的節點沒有必要，可以把它改成 [ 0 , 10 ] 的左孩子直接接上 [ 3 , 3 ] 這個節點，這樣做可以把記憶體壓到更小，而插入的時候就會變成要找最低的能夠蓋住新區間的區間之類的，實作的細節我還沒有很懂，總之還是先在下面附上 code (?) 。


code :

#include<bits/stdc++.h>
#define LL long long
#define VAL(u) ((u)?((u)->val):0LL)
using namespace std;
 
struct node2
{
    node2 *l,*r ;
    LL val ;
    int tag ;
    node2()
    {
        l=r=NULL ;
        val=0LL ;
        tag=-1 ;
    }
    node2(int _tag,LL _val)
    {
        l=r=NULL ;
        val=_val ;
        tag=_tag ;
    }
};
 
struct node
{
    node *l,*r ;
    node2 *st ;
    LL val ;
    node()
    {
        l=r=NULL ;
        st=NULL ;
        val=0LL ;
    }
};
 
int N,M ;
 
void push(int L,int R,node2 *u)
{
    if(!u || u->tag<0) return ;
    int mid=(L+R)/2 ;
    if(u->tag <= mid) u->l=new node2(u->tag,u->val) ;
    else u->r=new node2(u->tag,u->val) ;
    u->tag=-2 ;
}
 
void modify2(int L,int R,node2 *u,int pos,LL val)
{
    if(u->tag==-1 || L==R) { u->tag=pos ; u->val=val ; return ; }
    if(u->tag>=0 && pos==u->tag) { u->val=val ; return ; }
 
    push(L,R,u) ;
    int mid=(L+R)/2 ;
    if(pos<=mid)
    {
        if(!u->l) u->l=new node2 ;
        modify2(L,mid,u->l,pos,val) ;
    }
    else
    {
        if(!u->r) u->r=new node2 ;
        modify2(mid+1,R,u->r,pos,val) ;
    }
    u->val = __gcd(VAL(u->l),VAL(u->r)) ;
}
 
LL query2(int l,int r,int L,int R,node2 *u)
{
    if(!u) return 0LL ;
    if(l==L && r==R) return u->val ;
    if(u->tag >= 0)
    {
        if(l<=u->tag && r>=u->tag) return u->val ;
        else return 0LL ;
    }
    int mid=(L+R)/2 ;
    if(r<=mid) return query2(l,r,L,mid,u->l) ;
    else if(l>mid) return query2(l,r,mid+1,R,u->r) ;
    else return __gcd(query2(l,mid,L,mid,u->l),query2(mid+1,r,mid+1,R,u->r)) ;
}
 
void modify1(int posx,int posy,int L,int R,node *u,LL val)
{
    if(!u->st) u->st=new node2 ;
    if(L==R) { modify2(0,M-1,u->st,posy,val) ; return ; }
    int mid=(L+R)/2 ;
    if(posx<=mid)
    {
        if(!u->l) u->l=new node ;
        modify1(posx,posy,L,mid,u->l,val) ;
    }
    else
    {
        if(!u->r) u->r=new node ;
        modify1(posx,posy,mid+1,R,u->r,val) ;
    }
 
    if(u->l && u->r) modify2(0,M-1,u->st,posy,
            __gcd( query2(posy,posy,0,M-1,u->l->st) ,
                    query2(posy,posy,0,M-1,u->r->st) ) ) ;
    else if(u->l)
        modify2(0,M-1,u->st,posy,query2(posy,posy,0,M-1,u->l->st)) ;
    else if(u->r)
        modify2(0,M-1,u->st,posy,query2(posy,posy,0,M-1,u->r->st)) ;
}
 
LL query1(int x1,int x2,int y1,int y2,int L,int R,node *u)
{
    if(!u) return 0LL ;
    if(x1==L && x2==R) return query2(y1,y2,0,M-1,u->st) ;
    int mid=(L+R)/2 ;
    if(x2<=mid) return query1(x1,x2,y1,y2,L,mid,u->l) ;
    else if(x1>mid) return query1(x1,x2,y1,y2,mid+1,R,u->r) ;
    else return __gcd(query1(x1,mid,y1,y2,L,mid,u->l),
                    query1(mid+1,x2,y1,y2,mid+1,R,u->r)) ;
}
 
main()
{
    int Q ; scanf("%d%d%d",&N,&M,&Q) ;
    node *root=new node ;
    while(Q--)
    {
        int type ; scanf("%d",&type) ;
        if(type==1)
        {
            int x,y ; LL val ; scanf("%d%d%I64d",&x,&y,&val) ;
            modify1(x,y,0,N-1,root,val) ;
        }
        else
        {
            int x1,y1,x2,y2 ; scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ;
            printf("%I64d\n",query1(x1,x2,y1,y2,0,N-1,root)) ;
        }
    }
}
 

正解 code :

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory>
 
using namespace std;
 
using ull = unsigned long long;
 
ull gcd(ull a, ull b){ return b ? gcd(b, a % b) : a; }
 
struct Tree2 {
    int c1, c2;
    Tree2 *lc, *rc;
    ull gcd;
    Tree2(int cc1, int cc2) : c1(cc1), c2(cc2), lc(nullptr), rc(nullptr), gcd(0) {}
 
    static void ensure(Tree2*& t, int x, int c1, int c2) {
        if(!t) {
            t = new Tree2(x, x + 1);
        } else if(x < t->c1 || t->c2 <= x) {
            while((x < (c1 + c2) / 2) == (t->c1 < (c1 + c2) / 2))
                ((x < (c1 + c2) / 2) ? c2 : c1) = (c1 + c2) / 2;
            Tree2 * t2 = new Tree2(c1, c2);
            ((t->c1 < (c1 + c2) / 2) ? t2->lc : t2->rc) = t;
            t2->gcd = t->gcd;
            t = t2;
        }
    }
 
    void update(int q, ull k) {
        if(c1 + 1 == c2) {
            gcd = k;
        } else {
            if(q < (c1 + c2) / 2) {
                ensure(lc, q, c1, (c1 + c2) / 2);
                lc->update(q, k);
            } else {
                ensure(rc, q, (c1 + c2) / 2, c2);
                rc->update(q, k);
            }
            gcd = 0;
            if(lc) gcd = ::gcd(gcd, lc->gcd);
            if(rc) gcd = ::gcd(gcd, rc->gcd);
        }
    }
 
    ull query(int q, int v) {
        if(q <= c1 && c2 <= v) {
            return gcd;
        } else if(!(v <= c1 || c2 <= q)){
            ull ans = 0;
            if(lc) ans = ::gcd(ans, lc->query(q, v));
            if(rc) ans = ::gcd(ans, rc->query(q, v));
            return ans;
        } else {
            return 0;
        }
    }
 
    Tree2* copy() {
        Tree2 * that = new Tree2(c1, c2);
        if(lc) that->lc = lc->copy();
        if(rc) that->rc = rc->copy();
        that->gcd = gcd;
        return that;
    }
};
 
struct Tree {
    int r1, c1, r2, c2;
    Tree *lc, *rc;
    Tree2 t2;
    Tree(int rr1, int cc1, int rr2, int cc2) : r1(rr1), c1(cc1), r2(rr2), c2(cc2), lc(nullptr), rc(nullptr), t2(c1, c2) {}
 
    static void ensure(Tree*& t, int x, int r1, int c1, int r2, int c2) {
        if(!t) {
            t = new Tree(x, c1, x + 1, c2);
        } else if(x < t->r1 || t->r2 <= x) {
            while((x < (r1 + r2) / 2) == (t->r1 < (r1 + r2) / 2))
                ((x < (r1 + r2) / 2) ? r2 : r1) = (r1 + r2) / 2;
            Tree * t2 = new Tree(r1, c1, r2, c2);
            ((t->r1 < (r1 + r2) / 2) ? t2->lc : t2->rc) = t;
            t2->t2 = *unique_ptr<Tree2>(t->t2.copy());
            t = t2;
        }
    }
 
    void update(int p, int q, ull k) {
        if(r1 + 1 == r2) {
            t2.update(q, k);
        } else {
            if(p < (r1 + r2) / 2) {
                ensure(lc, p, r1, c1, (r1 + r2) / 2, c2);
                lc->update(p, q, k);
            } else {
                ensure(rc, p, (r1 + r2) / 2, c1, r2, c2);
                rc->update(p, q, k);
            }
            ull gcd = 0;
            if(lc) gcd = ::gcd(gcd, lc->t2.query(q, q + 1));
            if(rc) gcd = ::gcd(gcd, rc->t2.query(q, q + 1));
            t2.update(q, gcd);
        }
    }
 
    ull query(int p, int q, int u, int v) {
        if(p <= r1 && r2 <= u) {
            return t2.query(q, v);
        } else if(!(u <= r1 || r2 <= p)){
            ull ans = 0;
            if(lc) ans = ::gcd(ans, lc->query(p, q, u, v));
            if(rc) ans = ::gcd(ans, rc->query(p, q, u, v));
            return ans;
        } else {
            return 0;
        }
    }
};
 
int main(){
    int r, c, n;
    scanf("%d %d %d", &r, &c, &n);
 
    Tree tree(0, 0, r, c);
 
    while(n--){
        int cmd;
        scanf("%d", &cmd);
        if(cmd == 1) {
            int p, q; ull k;
            scanf("%d %d %llu", &p, &q, &k);
            tree.update(p, q, k);
        } else if(cmd == 2) {
            int p, q, u, v;
            scanf("%d %d %d %d", &p, &q, &u, &v);
            u++, v++;
            printf("%llu\n", tree.query(p, q, u, v));
        }
    }
}