维护一个 W*W 的矩阵，每次操作可以增加某格子的权值，或询问某子矩阵的总权值。 修改操作数 M<=160000，询问数 Q<=10000，W<=2000000。 。。。 cdq 分治 + 扫描线。 。强行离线。将二维树状数组降成一维。。。 http://www.lydsy.com/JudgeOnline/problem.php?id=1176 https://gist.github.com/lychees/d677c384dbe09fea8e02

//}/* .................................................................................................................................. */

const int N = int(2e5) + 9;
int n;

namespace BIT{
    const int N = 2000009;
    typedef LL intt;
    intt C[N], n;
    void Add(int x, int d){
        for (;x<=n;x+=low_bit(x)) C[x] += d;
    }
    intt Sum(int x){
        intt res = 0; for (;x;x^=low_bit(x)) res += C[x];
        return res;
    }
    intt Sum(int l, int r){
        return Sum(r) - Sum(l-1);
    }
} //using namespace BIT;

struct Op{
    int x1, y1, x2, y2, ty; LL d;
    void in(int _ty){
        ty = _ty;

        if (ty == 1){
            RD(x1, y1, d);
        }
        else if (ty == 2){
            RD(x1, y1, x2, y2);
            d = 0;
        }
    }
}; vector<Op> op;

void cdq(int l, int r){
    if (l + 1 == r){

    }
    else{
        int m = l + r >> 1;

        static PII Q[N]; int qn = 0;

        FOR(i, l, m) if (op[i].ty == 1) Q[qn++] = MP(op[i].x1, i);
        FOR(i, m, r) if (op[i].ty == 2){
            Q[qn++] = MP(op[i].x1-1, i);
            Q[qn++] = MP(op[i].x2, i);
        }

        sort(Q, Q+qn);

        REP(i, qn){

            int id = Q[i].se;

            if (op[id].ty == 2){ // Query
                if (Q[i].fi + 1 == op[id].x1){ // Left
                    op[id].d -= BIT::Sum(op[id].y1, op[id].y2);
                }
                else{ // Right
                    op[id].d += BIT::Sum(op[id].y1, op[id].y2);
                }
            }
            else{
                BIT::Add(op[id].y1, op[id].d);
            }
        }

        REP(i, qn){
            int id = Q[i].se;

            if (op[id].ty == 2){ // Query

            }
            else{
                BIT::Add(op[id].y1, -op[id].d);
            }
        }

        cdq(l, m); cdq(m, r);
    }
}


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int init_value; RD(init_value, BIT::n);
    assert(init_value == 0);

    do{
        int ty; RD(ty); if (ty == 3) break;
        Op t; t.in(ty); op.PB(t);
    } while (1);

    cdq(0, SZ(op));
    ECH(it, op) if (it->ty == 2){
        OT(it->d);
    }
}

Posted by xiaodao
Category: 日常
Tags: cdq 分治