Day6 - L - Mokia HYSBZ

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output3
5Hint

保证答案不会超过int范围

思路：三元偏序问题，CDQ分治，(time,x,y)，将每一次查询拆成四个点即可，初始值预处理一下就行

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

const int maxm = 2e6+;

int C[maxm], S, W, ans[maxm];

void add(int x, int val) {

    for(; x <= maxm; x += lowbit(x))

        C[x] += val;

}

int getsum(int x) {

    int ret = ;

    for(; x; x -= lowbit(x))

        ret += C[x];

    return ret;

}

void clearr(int x) {

    for(; x <= maxm; x += lowbit(x)) {

        if(C[x] == ) break;

        C[x] = ;

    }

}

struct Node {

    int type, tim, x, y, w, id;

} buf[maxm], res[maxm];

bool cmp_S(Node a, Node b) {

    if(a.tim == b.tim && a.x == b.x) return a.y < b.y;

    if(a.tim == b.tim) return a.x < b.x;

    return a.tim < b.tim;

}

void CDQ(int L, int R) {

    if(L >= R) return;

    int mid = L+R >> ;

    CDQ(L, mid), CDQ(mid+, R);

    int i = L, j = mid+, k = L;

    //左修改右查询

    while(i <= mid && j <= R) {

        if(res[i].x <= res[j].x) {

            if(res[i].type == )

                add(res[i].y, res[i].w);

            buf[k++] = res[i++];

        } else {

            if(res[j].type == )

                ans[res[j].id] += getsum(res[j].y) * res[j].w;

            buf[k++] = res[j++];

        }

    }

    while(i <= mid)

        buf[k++] = res[i++];

    while(j <= R) {

        ans[res[j].id] += getsum(res[j].y) * res[j].w;

        buf[k++] = res[j++];

    }

    for(int t = L; t <= R; ++t) {

        clearr(buf[t].y); // 清空树状数组

        res[t] = buf[t];

    }

}

int main() {

    scanf("%d%d", &S, &W);

    int type, sz = , x1, x2, y1, y2, tim = , query = ;

    while(scanf("%d", &type) && type != ) {

        if(type == ) {

            scanf("%d%d%d", &res[sz].x, &res[sz].y, &res[sz].w);

            res[sz].tim = tim++;

            res[sz++].type = type;

        } else if(type == ) {

            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

            ans[++query] = (y2 - y1 + ) * (x2 - x1 + ) * S;

            res[sz++] = {type, tim++, x1-, y1-, , query};

            res[sz++] = {type, tim++, x2, y1-, -, query};

            res[sz++] = {type, tim++, x1-, y2, -, query};

            res[sz++] = {type, tim++, x2, y2, , query};

        }

    }

    sort(res, res+sz, cmp_S);

    CDQ(, sz-);

    for(int i = ; i <= query; ++i)

        printf("%d\n", ans[i]);

    return ;

}

巴特西

Day6 - L - Mokia HYSBZ - 1176

最新文章

热门文章