感觉这一场的后面两题稍微比18DEC的要难一点点

T2的一些小细节想了很久,问了jambow;T3最后一点边界情况没想清楚,经dis提示后才会

YALIOJ Link

Redistricting

Description

给出一个长度为nn的01序列,现在你要把这个序列分成若干个长度不超过KK的连续段

求最少有多少段1的数量不少于0的数量

Constraints

n3105n\le 3*10^5

Solution

考虑dp,设dp[i]dp[i]表示考虑到ii的答案

dp[i]=minj=max(0,iK)i1(dp[j]+[sum1(j+1,i)ji2]) dp[i] = \min_{j=\max(0, i - K)}^{i-1} (dp[j] + [sum1(j + 1, i) \ge \frac{j-i}{2}])

其中sum1(i,j)sum1(i,j)表示区间iijj中1的个数

显然这个式子拆一下就能变成j2sum[j]i2sum[i]j - 2 * sum[j] \ge i - 2 * sum[i],其中sum[i]sum[i]11的前缀和

对于j2sum[j]j-2*sum[j]这个下标维护一个最小值的线段树,每次算出需要+1+1的部分的下标区间和不 的下标区间,直接转移

因为有jmax(0,iK)j\ge max(0, i-K)这个限制,所以在线段树维护的时候还要支持删除,那么在最底层开一个可删除堆维护即可

时间复杂度O(nlogn)O(n\log n),最多只会在线段树底层进行O(n)O(n)次删除,所以不是O(nlog2n)O(n \log ^2 n)

Exercise Route

Description

给出一棵nn个节点的树,另外还有mn+1m-n+1条非树边(即边数总和为mm

求恰好包含两条非树边的简单环的个数

Constraints

n,m2105n, m\le 2*10^5

Solution

通过观察发现,两条非树边(x1,y1),(x2,y2)(x_1, y_1),(x_2, y_2)要能形成简单环,当且仅当路径(x1,y1)(x_1, y_1)(x2,y2)(x_2, y_2)有公共边

于是可以把路径 拆成 两段统计贡献,直接树上差分

然后需要多处理一下两条路径的包含情况,也就是它们位于 所在子树相同。这种情况会多算,需要减掉

Train Tracking 2

Description

有一个长度为nn,值域[1,109][1, 10^9]的数组aia_i

给出kk, 告诉你ci=minj=ii+1ajc_i = \min_{j=i}^{i+-1}a_j,求满足条件的数组aa有多少个,答案对109+710^9+7取模

Constraints

n105n\le 10^5

Solution

不难发现,若ci>ci+1c_i > c_{i + 1},则能确定ai+ka_{i+k}的值;若ci<ci+1c_i < c_{i+1},则能确定aia_{i}的值

考虑连续一段cic_i相同的答案:求一段长度为lenlencic_i全都为valval的方案数

x=109valx = 10^9 - valdp[i]dp[i]表示考虑到第ii个数的方案数,那么有

dp[i]=(x+1)dp[i1]xkdp[ik1] dp[i] = (x + 1)dp[i-1] - x^{k}dp[i - k - 1]

假设第ii个数随便填[val,109][val, 10^9]中的数,则有可能区间[ik+1,i][i - k+ 1, i]全都没有填valval这个数

这种情况就是[ik+1,i][i-k+1, i]每个都能填[val+1,109][val + 1, 10^9]的数,且第iki-k位填了valval(因为要保证valval在区间[ik,i1][i-k, i-1]至少出现一次),剩下前面合法的方案数,即为xkdp[ik1]x^kdp[i-k-1]

那么可以把原序列分成cic_i相同的若干段,每段分别计算

最后特殊处理一下段与段之间相交的情况:若上一段的值ci1c_{i-1}大于当前的值cic_i,那么ai+k1a_{i+k-1}的值能被确定,且[i,i+k2][i, i+k-2]内的数会在上一段被考虑到,也就是说当前需要考虑的位置要减少kk个。下一段的情况同理

Codes

T1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 3e5 + 100, inf = 0x3f3f3f3f;

int N, K, Dp[Maxn];
char S[Maxn];

struct Heap
{
priority_queue <int, vector <int>, greater <int> > Q1, Q2;

inline void process () { while (!Q2.empty() && Q1.top() == Q2.top()) Q1.pop(), Q2.pop(); }

inline void push (int x) { Q1.push(x); }

inline void erase (int x) { Q2.push(x); }

inline int top () { process(); return (!Q1.empty()) ? Q1.top() : inf; }
};

namespace SEG
{
#define mid (l + r >> 1)
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r

struct info
{
int min;
Heap h;
} node[Maxn << 2];

inline void push_up (int root) { node[root].min = min(node[root << 1].min, node[root << 1 | 1].min); }

inline void init (int root, int l, int r)
{
node[root].min = inf;
if (l == r) return ;
init (lson), init (rson);
}

inline void update (int root, int l, int r, int x, int val, int op)
{
if (l == r)
{
if (op) node[root].h.push (val);
else node[root].h.erase (val);
node[root].min = node[root].h.top();
}
else
{
if (x <= mid) update (lson, x, val, op);
else update (rson, x, val, op);
push_up (root);
}
}

inline int query (int root, int l, int r, int x, int y)
{
if (x > y) return inf;
if (x <= l && r <= y) return node[root].min;

int ans = inf;
if (x <= mid) ans = min(ans, query (lson, x, y));
if (y > mid) ans = min(ans, query (rson, x, y));
return ans;
}

#undef mid
#undef lson
#undef rson
}

int Sum[Maxn], Val[Maxn];

inline void Solve ()
{
int cnt = 0;
for (int i = 0; i <= N; ++i)
{
Sum[i] = Sum[i - 1] + (S[i] == 'G');
Val[++cnt] = i - 2 * Sum[i];
}

sort(Val + 1, Val + cnt + 1);
cnt = unique (Val + 1, Val + cnt + 1) - Val - 1;
Sum[0] = lower_bound (Val + 1, Val + cnt + 1, Sum[0]) - Val;

SEG :: init (1, 1, cnt);
SEG :: update (1, 1, cnt, Sum[0], 0, 1);

for (int i = 1; i <= N; ++i)
{
Sum[i] = lower_bound (Val + 1, Val + cnt + 1, i - 2 * Sum[i]) - Val;
if (i >= K + 1)
{
int x = i - K - 1;
SEG :: update (1, 1, cnt, Sum[x], Dp[x], 0);
}
int x1 = SEG :: query (1, 1, cnt, Sum[i], cnt) + 1;
int x2 = SEG :: query (1, 1, cnt, 1, Sum[i] - 1);
Dp[i] = min (x1, x2);
//cout << Dp[i] << endl;
SEG :: update (1, 1, cnt, Sum[i], Dp[i], 1);
}

cout << Dp[N] << endl;
}

inline void Input ()
{
N = read<int>(), K = read<int>();
scanf("%s", S + 1);
}

int main()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();
// proc_status();

return 0;
}

T2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;

int N, M;
vector <int> G[Maxn];
pii E[Maxn];

int Sum[Maxn];
map <pii, int> Map;

namespace HLD
{
int dfn[Maxn], dfs_clock, top[Maxn], son[Maxn], size[Maxn], dep[Maxn], fa[Maxn];

inline void dfs_pre (int x)
{
dep[x] = dep[fa[x]] + 1, size[x] = 1;

for (int i = 0; i < G[x].size(); ++i)
{
int y = G[x][i];
if (y == fa[x]) continue;
fa[y] = x;
dfs_pre (y);
if (size[y] > size[son[x]]) son[x] = y;
size[x] += size[y];
}
}

inline void get_top (int x, int now)
{
dfn[x] = ++dfs_clock, top[x] = now;
if (son[x]) get_top (son[x], now);

for (int i = 0; i < G[x].size(); ++i)
{
int y = G[x][i];
if (y == fa[x] || y == son[x]) continue;
get_top (y, y);
}
}

inline int get_lca (int x, int y)
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
if (dep[x] < dep[y]) swap(x, y);
return y;
}
}

using namespace HLD;

inline int cmp (int x, int y) { return dfn[x] < dfn[y]; }

inline void dfs_sum (int x)
{
for (int i = 0; i < G[x].size(); ++i)
{
int y = G[x][i];
if (y == fa[x]) continue;
Sum[y] += Sum[x];
dfs_sum (y);
}
}

LL ans = 0;

inline void Update (int x, int y)
{
int lca = get_lca (x, y);
int fx = *(--upper_bound (G[lca].begin(), G[lca].end(), x, cmp));
int fy = *(--upper_bound (G[lca].begin(), G[lca].end(), y, cmp));
// cout << x << ' ' << y << ' ' << lca << endl;
// cout << fx << ' ' << fy << endl;

if (lca != x) ans -= Sum[fx] + Sum[fy], ++Sum[fx], ++Sum[fy];
else ans -= Sum[fy], ++Sum[fy];
}

inline void Query (int x, int y)
{
int lca = get_lca (x, y);
int fx = *(--upper_bound (G[lca].begin(), G[lca].end(), x, cmp));
int fy = *(--upper_bound (G[lca].begin(), G[lca].end(), y, cmp));

if (lca != x) ans -= Map[mp(fx, fy)], ++Map[mp(fx, fy)];

ans += max(0, Sum[x] - Sum[lca] - 1);
ans += max(0, Sum[y] - Sum[lca] - 1);
}

inline void Solve ()
{
dfs_pre (1), get_top (1, 1);
for (int i = 1; i <= N; ++i) sort(G[i].begin(), G[i].end(), cmp);

for (int i = 1; i <= M; ++i)
{
if (dfn[E[i].x] > dfn[E[i].y]) swap(E[i].x, E[i].y);
Update (E[i].x, E[i].y);
}

dfs_sum (1);

for (int i = 1; i <= M; ++i) Query (E[i].x, E[i].y);

cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = read<int>() - (N - 1);

for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
G[x].pb (y), G[y].pb (x);
}

for (int i = 1; i <= M; ++i) E[i].x = read<int>(), E[i].y = read<int>();
}

int main()
{

#ifdef hk_cnyali
freopen("B.in", "r", stdin);
freopen("B.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

T3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Mod = 1e9 + 7;

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL)a * a % Mod) if (i & 1) ans = (LL)ans * a % Mod;
return ans;
}

int N, K, A[Maxn];
int Dp[Maxn];

inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

inline int Calc (int val, int n)
{
int rest = 1e9 - val, rest_pow = Pow(rest, K);
Dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
Dp[i] = (LL)(rest + 1) * Dp[i - 1] % Mod;
if (i >= K) Add (Dp[i], Mod - (LL)rest_pow * Dp[max(0, i - K - 1)] % Mod);
}
return Dp[n];
}

inline void Solve ()
{
int i = 1, ans = 1;
while (i <= N - K + 1)
{
int j = i, len = K;
while (A[j] == A[j + 1]) ++j, ++len;

if (A[i - 1] > A[i]) len -= K;
if (A[j + 1] > A[j]) len -= K;

if (len >= 0) ans = (LL)ans * Calc (A[i], len) % Mod;
i = j + 1;
}

cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), K = read<int>();
for (int i = 1; i <= N - K + 1; ++i) A[i] = read<int>();
}

int main()
{

#ifdef hk_cnyali
freopen("C.in", "r", stdin);
freopen("C.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}