# Public NOIP Round #4（Div. 1） 题解()-其他

## Public NOIP Round #4（Div. 1） 题解()

T1：

vector

Code：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
typedef long long ll;
const int N = 1000005;
int n, m;
int a[N];
int lsh[N], tot;
ll Ans[N], ans;
int sum1[N], sum2[N];
struct node {
int l, r, id;

node (){}
node (int _l, int _r, int _id) {
l = _l, r = _r, id = _id;
}
};
vector <node> vec[N];

int find(int x) {
return lb(lsh + 1, lsh + tot + 1, x) - lsh;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
for (int i = 1, l, r, k, x; i <= n; ++i) {
scanf("%d%d%d", &l, &r, &k);
while (k--) scanf("%d", &x), vec[x].pb(node(l, r, i));
}
for (int i = 1; i <= m; ++i) {
tot = 0;
for (auto j : vec[i]) lsh[++tot] = j.l, lsh[++tot] = j.r + 1;
sort(lsh + 1, lsh + tot + 1), tot = unique(lsh + 1, lsh + tot + 1) - (lsh + 1);
for (auto &j : vec[i]) j.l = find(j.l), j.r = find(j.r + 1), ++sum1[j.l], --sum1[j.r];
for (int j = 1; j < tot; ++j) {
sum1[j] += sum1[j - 1], sum2[j] = sum2[j - 1];
if (sum1[j]) ans += 1ll * (lsh[j + 1] - lsh[j]) * a[i];
if (sum1[j] == 1) sum2[j] += lsh[j + 1] - lsh[j];
}
for (auto j : vec[i]) Ans[j.id] += 1ll * (sum2[j.r - 1] - sum2[j.l - 1]) * a[i];
for (int j = 1; j <= tot; ++j) sum1[j] = 0;
}
for (int i = 1; i <= n; ++i) printf("%lld ", ans - Ans[i]);
return 0;
}


T2：

$$f,g$$ 都可以在 $$\mathcal O(2^nn)$$ 的复杂度内简单地用 DP 求出。

for (int S = m - 1; S; --S) {
int u = __builtin_ctz(S);
ans[u] += a[S], a[S ^ (1 << u)] += a[S];
}


Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
int T;
int n, m;
int a[N], b[N];
ll ans[N];
ll f[1 << N], g[1 << N], c[1 << N];

void solve() {
scanf("%d%d", &n, &m);
memset(a, 0, sizeof (int) * n), memset(b, 0, sizeof (int) * n);
while (m--) {
int x, y; scanf("%d%d", &x, &y), --x, --y;
a[x] |= 1 << y, b[y] |= 1 << x;
}
m = 1 << n;
memset(f, 0, sizeof (ll) * m), memset(g, 0, sizeof (ll) * m);
f[0] = g[0] = 1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) if ((i >> j & 1) == 0) {
if ((i | b[j]) == i) f[i | (1 << j)] += f[i];
if ((i | a[j]) == i) g[i | (1 << j)] += g[i];
}
for (int v = 0; v < n; ++v) {
memset(c, 0, sizeof (ll) * m);
memset(ans, 0, sizeof (ll) * n);
for (int S = 0; S < m; ++S)
if ((S | b[v]) == S && (S >> v & 1) == 0) {
int _S = (m - 1) ^ S ^ (1 << v);
c[S] = f[S] * g[_S];
}
for (int S = m - 1; S; --S) {
int u = __builtin_ctz(S);
ans[u] += c[S], c[S ^ (1 << u)] += c[S];
}
for (int u = 0; u < n; ++u) printf("%lld ", ans[u]);
printf("\n");
}
}

int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}


T3：

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m;
int a[N];
int son[N][2], stk[N], top;
int mx[N], len[N];
int ans;

void dfs(int x) {
mx[x] = a[x], len[x] = 1;
for (int i = 0, y; i < 2; ++i) {
y = son[x][i];
if (!y) continue;
dfs(y);
mx[x] = max(mx[x], mx[y]), len[x] += len[y];
}
ans = max(ans, min(len[x], a[x] + mx[x] - 1));
}

void build() {
for (int i = 0; i <= n; ++i) son[i][0] = son[i][1] = 0;
top = ans = 0;
for (int i = 1; i <= n; ++i) {
while (top && a[stk[top]] > a[i]) --top;
son[i][0] = son[stk[top]][1], son[stk[top]][1] = i;
stk[++top] = i;
}
dfs(stk[1]);
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
build();
printf("%d\n", ans);
while (m--) {
int _, x, y; scanf("%d", &_);
while (_--) scanf("%d%d", &x, &y), swap(a[x], a[y]);
build();
printf("%d\n", ans);
}
return 0;
}

————————

T1：

vector

Code：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
typedef long long ll;
const int N = 1000005;
int n, m;
int a[N];
int lsh[N], tot;
ll Ans[N], ans;
int sum1[N], sum2[N];
struct node {
int l, r, id;

node (){}
node (int _l, int _r, int _id) {
l = _l, r = _r, id = _id;
}
};
vector <node> vec[N];

int find(int x) {
return lb(lsh + 1, lsh + tot + 1, x) - lsh;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
for (int i = 1, l, r, k, x; i <= n; ++i) {
scanf("%d%d%d", &l, &r, &k);
while (k--) scanf("%d", &x), vec[x].pb(node(l, r, i));
}
for (int i = 1; i <= m; ++i) {
tot = 0;
for (auto j : vec[i]) lsh[++tot] = j.l, lsh[++tot] = j.r + 1;
sort(lsh + 1, lsh + tot + 1), tot = unique(lsh + 1, lsh + tot + 1) - (lsh + 1);
for (auto &j : vec[i]) j.l = find(j.l), j.r = find(j.r + 1), ++sum1[j.l], --sum1[j.r];
for (int j = 1; j < tot; ++j) {
sum1[j] += sum1[j - 1], sum2[j] = sum2[j - 1];
if (sum1[j]) ans += 1ll * (lsh[j + 1] - lsh[j]) * a[i];
if (sum1[j] == 1) sum2[j] += lsh[j + 1] - lsh[j];
}
for (auto j : vec[i]) Ans[j.id] += 1ll * (sum2[j.r - 1] - sum2[j.l - 1]) * a[i];
for (int j = 1; j <= tot; ++j) sum1[j] = 0;
}
for (int i = 1; i <= n; ++i) printf("%lld ", ans - Ans[i]);
return 0;
}


T2：

$$f,g$$ 都可以在 $$\mathcal O(2^nn)$$ 的复杂度内简单地用 DP 求出。

for (int S = m - 1; S; --S) {
int u = __builtin_ctz(S);
ans[u] += a[S], a[S ^ (1 << u)] += a[S];
}


Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 20;
int T;
int n, m;
int a[N], b[N];
ll ans[N];
ll f[1 << N], g[1 << N], c[1 << N];

void solve() {
scanf("%d%d", &n, &m);
memset(a, 0, sizeof (int) * n), memset(b, 0, sizeof (int) * n);
while (m--) {
int x, y; scanf("%d%d", &x, &y), --x, --y;
a[x] |= 1 << y, b[y] |= 1 << x;
}
m = 1 << n;
memset(f, 0, sizeof (ll) * m), memset(g, 0, sizeof (ll) * m);
f[0] = g[0] = 1;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) if ((i >> j & 1) == 0) {
if ((i | b[j]) == i) f[i | (1 << j)] += f[i];
if ((i | a[j]) == i) g[i | (1 << j)] += g[i];
}
for (int v = 0; v < n; ++v) {
memset(c, 0, sizeof (ll) * m);
memset(ans, 0, sizeof (ll) * n);
for (int S = 0; S < m; ++S)
if ((S | b[v]) == S && (S >> v & 1) == 0) {
int _S = (m - 1) ^ S ^ (1 << v);
c[S] = f[S] * g[_S];
}
for (int S = m - 1; S; --S) {
int u = __builtin_ctz(S);
ans[u] += c[S], c[S ^ (1 << u)] += c[S];
}
for (int u = 0; u < n; ++u) printf("%lld ", ans[u]);
printf("\n");
}
}

int main() {
scanf("%d", &T);
while (T--) solve();
return 0;
}


T3：

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int n, m;
int a[N];
int son[N][2], stk[N], top;
int mx[N], len[N];
int ans;

void dfs(int x) {
mx[x] = a[x], len[x] = 1;
for (int i = 0, y; i < 2; ++i) {
y = son[x][i];
if (!y) continue;
dfs(y);
mx[x] = max(mx[x], mx[y]), len[x] += len[y];
}
ans = max(ans, min(len[x], a[x] + mx[x] - 1));
}

void build() {
for (int i = 0; i <= n; ++i) son[i][0] = son[i][1] = 0;
top = ans = 0;
for (int i = 1; i <= n; ++i) {
while (top && a[stk[top]] > a[i]) --top;
son[i][0] = son[stk[top]][1], son[stk[top]][1] = i;
stk[++top] = i;
}
dfs(stk[1]);
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
build();
printf("%d\n", ans);
while (m--) {
int _, x, y; scanf("%d", &_);
while (_--) scanf("%d%d", &x, &y), swap(a[x], a[y]);
build();
printf("%d\n", ans);
}
return 0;
}