C 给定1000*1000的矩阵，每次将一个子矩阵内全部值赋值为1，问四联通块数量 Q 3e4
首先考虑复杂度，3e4次操作的合并暴力肯定不行，并且要考虑已经为1的块不应该再次考虑
1.考虑合并操作，对于一个0点，当他变为1对答案的影响只有几种情况
周边都是0，总联通联通块数量加1
周边有（1 - 4）个不同联通块，ans -= 不同联通块个数+1
对于相同的联通块通过当前0点合并没有意义，不用计算。
所以对于每个0点的合并可以快速计算并用并查集合并（映射下标）
2.然后考虑第二个问题，如何让每个0点只被操作一次
可以用并查集维护每行当前点的下一个0点，这样在区间上跳动速度飞快并且每次跳的都是0点
或者用set维护当前行内还有0的下标并操作erase（比并查集常数大)
/*
Zeolim - An AC a day keeps the bug away
*/
//#pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
#define pb(x) push_back(x)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 386910137;
const ull P = 13331;
const int MAXN = 3e6 + 100;
int n, m;
int fa[MAXN] = {0};
int mov[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool arr[1010][1010] = {0};
struct uni
{
int fa[1010] = {0};
uni() { for(int i = 0; i < 1010; ++i) fa[i] = i; }
int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x] ); }
}u[1010];
int findfa(int x) { return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
int ans = 0;
int getp(int x, int y) { return x * m + y; }
struct node { int x, y, fa; };
void uni(int x, int y)
{
++ans;
int tox, toy, p, q;
p = findfa(getp(x, y));
for(int i = 0; i < 4; ++i) //统计不同联通块的数量并计算贡献
{
tox = x + mov[i][0], toy = y + mov[i][1];
if(arr[tox][toy])
{
q = findfa(getp(tox, toy));
if(p != q) { fa[q] = p; --ans; } //不同联通块才有贡献
}
}
}
void init()
{
for(int i = 0; i < 1010; ++i)
for(int j = 0; j < 1010; ++j)
fa[getp(i, j)] = getp(i, j);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j) //维护第i行第j列后面的第一个0
{
if(!arr[i][j]) u[i].fa[j] = j;
else u[i].fa[j] = j + 1;
}
}
for(int i = 1; i <= n; ++i) //初始化合并矩阵信息
{
for(int j = 1; j <= m; ++j)
{
if(!arr[i][j]) continue;
uni(i, j);
}
}
}
void put()
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cout << arr[i][j];
}
cout << '
';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("d:out.txt","w",stdout);
//freopen("d:in.txt","r",stdin);
cin >> n >> m;
char x;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> x;
arr[i][j] = (x == '1');
}
}
init();
//cout << ans << '
';
int q;
cin >> q;
while(q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for(int i = x1; i <= x2; ++i) //操作区间内1
{
for(int j = u[i].findfa(y1); j <= y2; j = u[i].findfa(j))
{
arr[i][j] = 1;
u[i].fa[j] = j + 1;
uni(i, j);
}
}
//put();
cout << ans << '
';
}
return 0;
}B 贪吃蛇，wsad上下左右移动，吃住x头变长，不吃整体移动，问最终形态
用双端队列可以很容易的维护当前状态见代码
/*
Zeolim - An AC a day keeps the bug away
*/
//#pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
#define pb(x) push_back(x)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 386910137;
const ull P = 13331;
const int MAXN = 3e6 + 100;
int mov[4][2] = {{0, 1},{1, 0},{-1,0},{0,-1}};
struct pit { int x, y; };
char arr[410][410] = {0};
int n, m;
bool inmap(int x, int y) { return (x >= 1 && x <= n && y >= 1 && y <= m); }
int main()
{
cin >> n >> m;
deque <pit> Q;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> arr[i][j];
if(arr[i][j] == '@')
{
Q.push_back(pit{i, j});
arr[i][j] = '.';
}
}
}
map <char, int> MP;
MP['W'] = 2, MP['A'] = 3, MP['S'] = 1, MP['D'] = 0;
string opt;
cin >> opt;
int p, tox, toy, rtox, rtoy;
for(auto x : opt)
{
p = MP[x], tox = Q.front().x, toy = Q.front().y;
tox += mov[p][0], toy += mov[p][1];
if(!inmap(tox, toy)) { cout << "GG
"; return 0; }
if(arr[tox][toy] == 'o')
{
arr[tox][toy] = '.';
Q.push_front(pit{tox, toy});
}
else
{
rtox = Q.back().x, rtoy = Q.back().y;
Q.pop_back();
Q.push_front(pit{tox, toy});
rtox = Q[1].x, rtoy = Q[1].y;
}
}
while(Q.size() > 1)
{
arr[Q.back().x][Q.back().y] = 'X';
Q.pop_back();
}
arr[Q.back().x][Q.back().y] = '@';
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cout << arr[i][j];
}
cout << '
';
}
return 0;
}