Męczę się z takim zadaniem z OI-a: https://szkopul.edu.pl/problemset/problem/3sQlWSD2omwi4M_wdqCbycIW/site/?key=statement
Wymyśliłem rozwiązanie w O(n*m*q) - przechodzi na 60pkt. Mianowicie:
Jesli mamy sprawdzić jakąś tablicę binarną (w ile ruchów da się doprowadzić do zer), to zauważyłem, że musimy iść od największych m(j), i dla każdego j iść w kolejności od n do 1. W sensie:
for (int j = m; j >= 1; --j)
{
for (int i = n; i >= 1; --i)
{
}
}
I teraz, jeśli plansza[i][j] jest jedynką, to obracamy na prostokącie 1,1 do i,j. I zeby nie mieć O(n^2*m^2*g) btw. to wchodzi na 39pkt, to naliczam sobie dp. dp[i][j] / sumy prefiksowe -> ile liczb obrucimy w prostokącie i,j do n,m. Tylko jest problem, bo dla każdego zapytania naliczam to dp, i nie wiem jak podejśc do tego sprytniej, żeby nie musieć naliczać cały czas.
Ma ktoś jakiś pomysł?
Kod:
#include <iostream>
#include <vector>
using namespace std;
int n = 0, m = 0, q = 0, y_1 = 0, x_1 = 0, y_2 = 0, x_2 = 0, wyn = 0;
vector<vector<bool>> plansza;
vector<vector<int>> dp;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> q;
for (int i = 0; i <= n; ++i)
{
plansza.push_back({});
dp.push_back({});
for (int j = 0; j <= m; ++j)
{
plansza[i].push_back(false);
dp[i].push_back(0);
}
}
while(q--)
{
cin >> y_1 >> x_1 >> y_2 >> x_2;
y_1--;
x_1--;
y_2--;
x_2--;
wyn = 0;
for (int i = y_1; i <= y_2; ++i)
for (int j = x_1; j <= x_2; ++j)
plansza[i][j] = !plansza[i][j];
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (plansza[i][j] == true)
dp[i][j] = 1;
else
dp[i][j] = 0;
}
}
for (int j = m-1; j >= 0; --j)
{
for (int i = n-1; i >= 0; --i)
{
dp[i][j] += dp[i+1][j] + dp[i][j+1] - dp[i+1][j+1];
if (dp[i][j] % 2 == 1)
{
dp[i][j] = dp[i+1][j] + dp[i][j+1] - dp[i+1][j+1] + 1;
if (dp[i][j] % 1 == 0)
wyn++;
}
else
dp[i][j] = dp[i+1][j] + dp[i][j+1] - dp[i+1][j+1];
}
}
printf("%d\n",wyn);
}
return 0;
}