树状数组动态维护前缀和
题意:在一个n*m的矩阵中有一些图标,每次询问增加/删除一个图标,问最少移动多少个图标能从上往下,从左往右依次将每列填满
思路:考虑将二维矩阵按列展开成一维矩阵并从上往下编号。
即对于一个3*3的矩阵,每一格的编号为
1,4,7
2,5,8
3,6,9
假设当前有k个图标,每次移动图标时,原本就在编号k前面的图标我们不用动它,只需要移动在k后面的图标去填满k个格子即可~
因此,我们记录图标*
的总数为sum,每次的答案即为询问时*
的总数量sum - 从1到sum*
的数量
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q, tr[N * N], s[N * N];
int sum, cnt;
char g[N][N];
//y总的板子
int lowbit(int x)
{
return x & -x;
}
void modify(int x, int v)
{
for(int i = x; i <= cnt; i += lowbit(i))
tr[i] += v;
}
int ask(int x)
{
int res = 0;
for(int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}
int main()
{
cin >> n >> m >> q;
for(int i = 1; i <= n; i++)
scanf("%s", g[i] + 1);
cnt = 0;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
if(g[j][i] == '*') s[++cnt] = 1, sum++; //记录*的个数
else s[++cnt] = 0;
}
for(int i = 1; i <= cnt; i++) modify(i, s[i]); //初始化
while(q--)
{
int a, b;
scanf("%d%d", &a, &b);
int t = a + (b - 1) * n; //在一维中的相对位置
if(g[a][b] == '*') g[a][b] = '.', modify(t, -1), sum--; //*变.数量减一
else g[a][b] = '*', modify(t, 1), sum++; //.变*数量加一
cout << sum - ask(sum) << endl;
}
return 0;
}