[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));
        }
    }
}