Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Всем прив, запихал в узел до 2D префсуммы ниче не работает, че делать?

Манипулятор Батинков Ученик (115), на голосовании 4 месяца назад
 #include  

using namespace std;

int w = 1, a;
vector>> t;

void build() {
for (int i = w / 2 - 1; i > 0; i--) {
t[i] = min(prefixSum2D(t[i * 2]), prefixSum2D(t[i * 2 + 1]));
}
}

long long ok(int l, int r) {
l += w / 2;
r += w / 2;
long long ans = 1e9;
for (; l <= r; r /= 2, l /= 2) {
if (l % 2 != 0) {
ans = min(t[l++], ans);
}
if (r % 2 == 0) {
ans = min(ans, t[r--]);
}
}
return ans;
}

void upd(int ind, long long x) {
ind += w / 2;
t[ind] = x;
ind /= 2;
while (ind) {
t[ind] = min(prefixSum2D(t[i * 2]), prefixSum2D(t[i * 2 + 1]));
ind /= 2;
}
}

int prefixSum2D(int a[][C])
{
int psa[R][C];
psa[0][0] = a[0][0];
for (int i = 1; i < C; i++)
psa[0][i] = psa[0][i - 1] + a[0][i];
for (int i = 1; i < R; i++)
psa[i][0] = psa[i - 1][0] + a[i][0];
for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++)
psa[i][j] = psa[i - 1][j] + psa[i][j - 1]
- psa[i - 1][j - 1] + a[i][j];
}
return psa
}

int main() {
int n, q;
cin >> n >> q;
while (w < n) {
w *= 2;
}
w *= 2;
t.resize(w, 0);
for (int i = w / 2; i < w / 2 + n; i++) {
cin >> t[i];
}
for (int i = w / 2 + n; i < w; i++) {
t[i] = t[w / 2 + n - 1];
}
build();
while (q--) {
int com;
cin >> com;
if (com == 1) {
int x;
long long y;
cin >> x >> y;
upd(x, y);
}
else {
int l, r;
cin >> l >> r;
cout << ok(l, r - 1) << endl;
}
}
}
Голосование за лучший ответ
Татьяна Просветленный (36384) 5 месяцев назад
Твой код содержит несколько ошибок и недочетов, которые мешают его корректной работе. Давай разберем их и попробуем исправить.

Функция prefixSum2D написана неправильно и не возвращает значение:
Функция prefixSum2D должна возвращать 2D префиксную сумму. Однако, в твоем коде она не возвращает значение.

Инициализация вектора t:
Инициализация вектора t в основном коде неверна. Необходимо инициализировать вектор векторов.

Функции build, upd и ok используют неверные методы:
Необходимо правильно использовать методы 2D префиксных сумм.
 #include  

using namespace std;

int w = 1, a;
vector>> t;

vector> prefixSum2D(const vector>& a) {
int R = a.size();
int C = a[0].size();
vector> psa(R, vector(C, 0));

psa[0][0] = a[0][0];

for (int i = 1; i < C; i++)
psa[0][i] = psa[0][i - 1] + a[0][i];

for (int i = 1; i < R; i++)
psa[i][0] = psa[i - 1][0] + a[i][0];

for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++)
psa[i][j] = psa[i - 1][j] + psa[i][j - 1] - psa[i - 1][j - 1] + a[i][j];
}

return psa;
}

void build() {
for (int i = w / 2 - 1; i > 0; i--) {
t[i] = prefixSum2D(t[i * 2]);
t[i] = prefixSum2D(t[i * 2 + 1]);
}
}

long long ok(int l, int r) {
l += w / 2;
r += w / 2;
long long ans = LLONG_MAX;
while (l <= r) {
if (l % 2 == 1) {
ans = min(ans, t[l][0][0]); // Предполагается, что минимальное значение в 2D префиксных суммах
l++;
}
if (r % 2 == 0) {
ans = min(ans, t[r][0][0]); // Предполагается, что минимальное значение в 2D префиксных суммах
r--;
}
l /= 2;
r /= 2;
}
return ans;
}

void upd(int ind, const vector>& x) {
ind += w / 2;
t[ind] = x;
ind /= 2;
while (ind) {
t[ind] = prefixSum2D(t[ind * 2]);
t[ind] = prefixSum2D(t[ind * 2 + 1]);
ind /= 2;
}
}

int main() {
int n, q;
cin >> n >> q;
while (w < n) {
w *= 2;
}
w *= 2;
t.resize(w);

for (int i = w / 2; i < w / 2 + n; i++) {
int m;
cin >> m;
t[i].resize(m, vector(m));
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
cin >> t[i][j][k];
}
}
}
for (int i = w / 2 + n; i < w; i++) {
t[i] = t[w / 2 + n - 1];
}
build();
while (q--) {
int com;
cin >> com;
if (com == 1) {
int x, m;
cin >> x >> m;
vector> y(m, vector(m));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
cin >> y[i][j];
}
}
upd(x, y);
} else {
int l, r;
cin >> l >> r;
cout << ok(l, r - 1) << endl;
}
}
return 0;
}
Похожие вопросы