글 읽기 - 구간합구하기 3 뭐가 문제 일까요!

orange4glace 6년 전 0

저의 팬윅트리에 도대체 무슨 문제가 있는걸까요

ㅠㅠ

#include <cstring>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <map>
#include <cstdio>
#include <fstream>
#include <string>
#include <algorithm>
#include <set>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <time.h>
using namespace std;

#define FAST_IO ios::sync_with_stdio(false)
#define sci(d) scanf("%d", &d)
#define scs(s) scanf("%s", &s)
#define SINF 20000000
#define INF 2000000000
#define LLINF 5000000000000000LL
#define X first
#define Y second
#define MAX 1001
#define endl "\n"

typedef long long ll;
typedef pair<int, int> pi;

int Q, N, M, K, L;

struct FenwickTree2D {
	vector<vector <ll> > bit;
	int n, m;

	void init(int _n, int _m) {
		n = _n + 1;
		m = _m + 1;
		bit.assign(n, vector<ll>(m));
	}

	ll query(int y, int x) {
		ll ret = 0;
		while (y > 0) {
			int _x = x;
			while (_x > 0) {
				ret += bit[y][_x];
				_x -= (_x & -_x);
			}
			y -= (y & -y);
		}
		return ret;
	}
	
	ll query(int y1, int x1, int y2, int x2) {
		int qx1 = min(x1, x2);
		int qy1 = min(y1, y2);
		int qx2 = max(x1, x2);
		int qy2 = max(y1, y2);
		return query(qy2, qx2) - query(qy1 - 1, qx2) - query(qy2, qx1 - 1) + query(qy1 - 1, qx1 - 1);
	}
	
	void update(int y, int x, ll dif) {
		while (y < n) {
			int _x = x;
			while (_x < m) {
				bit[y][_x] += dif;
				_x += (_x & -_x);
			}
			y += (y & -y);
		}
	}
};

int main() {
	sci(N); sci(M);
	FenwickTree2D bit;
	bit.init(N, N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ll a;
			scanf("%lld", &a);
			bit.update(i + 1, j + 1, a);
		}
	}
	for (int i = 0; i < M; i++) {
		int a, b, c, d, e; ll f;
		sci(a);
		if (a) {
			scanf("%d %d %d %d", &b, &c, &d, &e);
			printf("%lld\n", bit.query(c, b, e, d));
		}
		else {
			scanf("%d %d %lld", &b, &c, &f);
			ll v = bit.query(c, b, c, b);
			bit.update(c, b, f - v);
		}
	}
	cin >> N;
}

etaehyun4 6년 전 1

입력받으실 때 bit.update (j +1, i + 1, a) 가 되어야 할 것 같아요.

orange4glace 6년 전 0

헐 감사합니다!! ㅠㅠ 문제를 제대로 읽지 않았네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

구간합구하기 3 뭐가 문제 일까요!

orange4glace 6년 전 0

etaehyun4 6년 전 1

orange4glace 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말