$\Huge\href{https://www.acwing.com/blog/content/30372/}{『题解主页』}$

6349

lofty

Egbert-Lannister.

_mayiwei
ssy_
xueseng

rswcc
wxy.
YuanYn.
WA自由人
hbin_frooog
むぎわらボイス

QWQ-J

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 160;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int n, m;
char a[N][N];
queue<PII> q;
int res;
int dist[N][N];

int bfs(int sx, int sy)
{
memset(dist, -1, sizeof dist);
dist[sx][sy] = 0;
q.push({sx, sy});

while (q.size())
{
PII t = q.front();
q.pop();

for (int i = 0; i < 8; i ++ )
{
int x = t.x + dx[i], y = t.y + dy[i];
if (x <= 0 || x > n || y <= 0 || y > m) continue;
if (a[x][y] == '*') continue;
if (dist[x][y] != -1) continue;
if (a[x][y] == 'H') return dist[t.x][t.y] + 1;

dist[x][y] = dist[t.x][t.y] + 1;
q.push({x, y});
}
}

return -1;
}

int main()
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++ )
scanf("%s", a[i] + 1);

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (a[i][j] == 'K') printf("%d\n", bfs(i, j));

return 0;
}


$$x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 500010;

LL n, res;
LL a[N], tmp[N];

void merge_sort(LL q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ], res += (LL)mid - i + 1;

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

int main()
{
while (cin >> n && n)
{
res = 0;
for (int i = 0; i < n; i ++ )
scanf("%lld", &a[i]);

merge_sort(a, 0, n - 1);

printf("%lld\n", res);
}

return 0;
}


### 平衡树做法 · $O(n \log n)$

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int p, n, id;

int main()
{
int x;
scanf("%d", &p);

while (p -- )
{
multiset<int> S;
multiset<int>::iterator it;
vector<int> ans;

scanf("%d%d", &id, &n);

for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
S.insert(x);

if (i == 1) it = S.begin();
else
{
if (i & 1)
{
if (x < *it) it -- ;
}
else
{
if (x >= *it) it ++ ;
}
}
if (i & 1) ans.push_back(*it);
}

printf("%d %d\n", id, (n + 1) / 2);

bool f = 1;
for (int i = 0, sz = ans.size(); i < sz; i ++ )
{
if (i && i % 10 == 0) puts(""), f = 1;
if (f) printf("%d ", ans[i]);
else printf(" %d", ans[i]);
}
puts("");
}

return 0;
}


### 对顶堆做法 · $O(n \log n)$




#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m, k;
int row[N], col[N];
int s[N], c[N];

LL f(int n, int a[])
{
for (int i = 1; i <= n; i ++ )
s[i] = s[i - 1] + a[i];

if (s[n] % n) return -1;
int avg = s[n] / n;

c[1] = 0;
for (int i = 1; i <= n; i ++ )
c[i] = s[i - 1] - (i - 1) * avg;

sort(c + 1, c + n + 1);

LL res = 0;
for (int i = 1; i <= n; i ++ )
res += abs(c[i] - c[(n + 1) / 2]);

return res;
}

int main()
{
int x, y;
scanf("%d%d%d", &n, &m, &k);

while (k -- )
{
scanf("%d%d", &x, &y);
row[x] ++ , col[y] ++ ;
}

LL r = f(n, row), c = f(m, col);
if (r != -1 && c != -1) printf("both %lld\n", r + c);
else if (r != -1) printf("row %lld\n", r);
else if (c != -1) printf("column %lld\n", c);
else puts("impossible");

return 0;
}


#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int n;
int g[N][N];
queue<PII> q;
PII pre[N][N];

void bfs(int x, int y)
{
q.push({x, y});
memset(pre, -1, sizeof pre);
pre[x][y] = {0, 0};

while (q.size())
{
auto t = q.front();
q.pop();

for (int i = 0; i < 4; i ++ )
{
int xx = t.x + dx[i], yy = t.y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
if (g[xx][yy]) continue;
if (pre[xx][yy].x != -1) continue;

q.push({xx, yy});
pre[xx][yy] = t;
}
}
}

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &g[i][j]);

bfs(n - 1, n - 1);

PII end(0, 0);
while (1)
{
printf("%d %d\n", end.x, end.y);
if (end.x == n - 1 && end.y == n - 1) break;
end = pre[end.x][end.y];
}

return 0;
}


#include <iostream>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n;
int h[N][N];
queue<PII> q;
bool st[N][N];

void bfs(int x, int y, bool& f1, bool& f2)
{
q.push({x, y});
st[x][y] = 1;

while (q.size())
{
auto t = q.front();
q.pop();

for (int i = 0; i < 8; i ++ )
{
int xx = t.x + dx[i], yy = t.y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
if (h[xx][yy] != h[t.x][t.y])
{
if (h[xx][yy] > h[t.x][t.y]) f1 = 1;
else f2 = 1;
}
else if (!st[xx][yy])
{
st[xx][yy] = 1;
q.push({xx, yy});
}
}
}
}

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &h[i][j]);

int r1 = 0, r2 = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (!st[i][j])
{
bool f1 = 0, f2 = 0;
bfs(i, j, f1, f2);
if (!f1) r1 ++ ;
if (!f2) r2 ++ ;
}

printf("%d %d\n", r1, r2);

return 0;
}


#include <iostream>

using namespace std;

const int N = 200010;

int n, k, a, b, q;
int d[N];
int t1[N], t2[N];

int lowbit(int x)
{
return x & -x;
}

void add(int tr[], int x, int c)
{
for (int i = x; i <= n; i += lowbit(i))
tr[i] += c;
}

int sum(int tr[], int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += tr[i];
return res;
}

int main()
{
scanf("%d%d%d%d%d", &n, &k, &a, &b, &q);

int op, x, y, p;
while (q -- )
{
scanf("%d", &op);
if (op == 1)
{
scanf("%d%d", &x, &y);
add(t1, x, min(d[x] + y, b) - min(d[x], b));
add(t2, x, min(d[x] + y, a) - min(d[x], a));
d[x] += y;
}
else
{
scanf("%d", &p);
printf("%d\n", sum(t1, p - 1) + sum(t2, n) - sum(t2, p + k - 1));
}
}

return 0;
}