题解 P4390 【[BOI2007]Mokia 摩基亚】

qianfujia · 2019-08-01 18:27:35 · 题解

似乎本题题解里还没有用二维线段树过的

这是一道二维线段树板子题

动态开点，运用四分的思想，将区间分为左上，左下，右上，右下四块，分别进行递归求解

时间复杂度 O(q \log W) 但是常数较大，被树状数组吊着打，动态开点后空间复杂度O(s\log W) s为修改操作个数

贴代码

#include<bits/stdc++.h>
#define N 160010
using namespace std;
int tree[N*22], lu[N*22], ld[N*22], ru[N*22], rd[N*22], cnt = 1;//一分为四
inline void pushup(int rt){
    tree[rt] = tree[lu[rt]] + tree[ld[rt]] + tree[ru[rt]] + tree[rd[rt]];
}
inline void update(int x, int y, int rt, int LU, int LD, int RU, int RD, int p){
    if(LU == LD && RU == RD){tree[rt] += p; return ;}
    int midx = (LU + LD) >> 1, midy = (RU + RD) >> 1;
    if(midx >= x){
        if(midy >= y){
            if(!lu[rt])lu[rt] = ++ cnt;
            update(x, y, lu[rt], LU, midx, RU, midy, p);
        }
        else if(midy != RD){
            if(!ld[rt])ld[rt] = ++ cnt;
            update(x, y, ld[rt], LU, midx, midy + 1, RD, p);
        }
    }
    else if(midx != LD){
        if(midy >= y){
            if(!ru[rt])ru[rt] = ++ cnt;
            update(x, y, ru[rt], midx + 1, LD, RU, midy, p);
        }
        else if(midy != RD){
            if(!rd[rt])rd[rt] = ++ cnt;
            update(x, y, rd[rt], midx + 1, LD, midy + 1, RD, p);
        }
    }
    pushup(rt);
}
inline int query(int lx, int rx, int ly, int ry, int LU, int LD, int RU, int RD, int rt){
    if(lx <= LU && LD <= rx && ly <= RU && RD <= ry)return tree[rt];
    int midx = (LU + LD) >> 1, midy = (RU + RD) >> 1, ans = 0;
    if(midx >= lx && midy >= ly && lu[rt])ans += query(lx, rx, ly, ry, LU, midx, RU, midy, lu[rt]);
    if(midx >= lx && midy < ry && ld[rt] && midy != RD)ans += query(lx, rx, ly, ry, LU, midx, midy + 1, RD, ld[rt]);
    if(midx < rx && midy >= ly && ru[rt] && midx != LD)ans += query(lx, rx, ly, ry, midx + 1, LD, RU, midy, ru[rt]);
    if(midx < rx && midy < ry && rd[rt] && midx != LD && midy != RD)ans += query(lx, rx, ly, ry, midx + 1, LD, midy + 1, RD, rd[rt]);
    return ans;
}
int main(){
    int opt, w;
    while(scanf("%d", &opt) != EOF && opt != 3){
        if(opt == 0){
            scanf("%d", &w); continue;
        }
        if(opt == 1){
            int x, y, A; scanf("%d%d%d", &x, &y, &A);
            update(x, y, 1, 1, w, 1, w, A);
        } else{
            int xl, xr, yl, yr; scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
            printf("%d\n", query(xl, xr, yl, yr, 1, w, 1, w, 1));
        }
    }
    return 0;
}