为什么题目名称又是 \(A, B, C\) 啊！
T1 嘉然
首先对整个序列做一些处理，容易发现连续的颜色相同的一段，我们只能取其中的一个值，贪心的讲，显然需要取这一段的最大值，那么我们将颜色相同的段缩起来，设最终得到的序列长度为 \(m\) ，不难发现我们最多选择 \(\lfloor\tfrac{m-1}{2}\rfloor\) 个数，由于首尾的数一定不能选，因此最优方案是选择其他数中最大的 \(\lfloor\tfrac{m-1}{2}\rfloor\) 个，可以归纳证明这个上界一定可以取到。（可以吗？可以吗？可以吗？）
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e6;
int n, m;
long long ans;
char s[max1 + 5];
int A[max1 + 5];
int main ()
{
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d%s", &n, s + 1);
for ( int i = 1, w; i <= n; i ++ )
{
scanf("%d", &w);
if ( i == 1 || s[i - 1] != s[i] )
A[++m] = w;
else
A[m] = max(A[m], w);
}
if ( m > 2 )
{
nth_element(A + 2, A + ( m + 1 >> 1 ), A + m);
reverse(A + 2, A + m);
for ( int i = 2; i <= ( m + 1 >> 1 ); i ++ )
ans += A[i];
}
printf("%lld\n", ans);
return 0;
}
T2 今天
简单谈一下考场中的一个想法。（显然这题不是考场上能写出来的）
考虑对 \(A\) 序列分块，对于散块显然暴力，考虑整块进行移动，设当前处理的块为 \([st,ed]\)， 将这个块内的点取出后建立虚树，考虑一个整块对于一次询问的影响，具体而言是下面所述过程：
首先询问的点 \(u\) 会跳到虚树包含的一条链上，这个过程不管对虚树上哪个点进行操作，所造成的的影响均为跳 father ，显然我们很容易计算询问点进入虚树的时刻，当询问点进入虚树后，由于询问点位于虚树的一条边所代表的链上，因此经过若干操作后，询问点一定会经过这条边的两个端点（如果不经过，那么询问点最终仍然位于进入虚树时的边上），如果我们可以预处理 \(f_{i,j}\) 表示 \(i\) 节点经过操作 \([j,ed]\) 后到达的节点，那么便可以快速查询。
预处理 \(f_{i,j}\) 就是找到 \(i\) 经过第 \(j\) 次操作后到达的节点，发现这个节点仍然位于虚树所包含的一条链上，因此可以套用上述查询过程进行计算。
只需要考虑如何查询，此时需要计算询问点到达虚树上边所连接两个端点中任意一个的最早时刻，考虑询问点在边上的移动，不难发现如果操作位于边所连接的下面的节点的子树中，那么询问点下移，否则，询问点上移，可以计算 \(sum_{i,j}\) 表示经过 \([st,i]\) 的操作后， \(j\) 的父边上的询问点下移的次数，建立 vector \(bin_{i,k}\) 并将 \(i\) push_back 到 \(bin_{j,sum_{i,j}}\) 中，我们可以通过 vector 内二分做到 \(O(\log n)\) 查询。
总复杂度 \(O(n\sqrt{n}\log n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
const int max1 = 1e5, max2 = 316, base = 1264;
int n, m, q, A[max1 + 5];
int head[max1 + 5], edge[max1 + 5];
int siz[max1 + 5], deep[max1 + 5], father[max1 + 5], son[max1 + 5];
int top[max1 + 5], dfn[max1 + 5], rk[max1 + 5], dfs_clock;
void Find_Heavy_Edge ( int now, int fa, int depth )
{
siz[now] = 1, deep[now] = depth, father[now] = fa, son[now] = 0;
int max_siz = 0;
for ( int v = head[now]; v; v = edge[v] )
{
if ( v == fa )
continue;
Find_Heavy_Edge(v, now, depth + 1);
if ( max_siz < siz[v] )
max_siz = siz[v], son[now] = v;
siz[now] += siz[v];
}
return;
}
void Connect_Heavy_Edge ( int now, int ancestor )
{
top[now] = ancestor; dfn[now] = ++dfs_clock; rk[dfs_clock] = now;
if ( son[now] )
Connect_Heavy_Edge(son[now], ancestor);
for ( int v = head[now]; v; v = edge[v] )
{
if ( v == father[now] || v == son[now] )
continue;
Connect_Heavy_Edge(v, v);
}
return;
}
int Kth_Ancestor ( int u, int k )
{
while ( deep[u] - deep[top[u]] < k )
k -= deep[u] - deep[top[u]] + 1, u = father[top[u]];
return rk[dfn[u] - k];
}
int Get_Lca ( int u, int v )
{
while ( top[u] != top[v] )
{
if ( deep[top[u]] < deep[top[v]] )
swap(u, v);
u = father[top[u]];
}
if ( deep[u] > deep[v] )
swap(u, v);
return u;
}
int Move ( int u, int v )
{
if ( u == v )
return u;
else if ( dfn[v] >= dfn[u] && dfn[v] <= dfn[u] + siz[u] - 1 )
return Kth_Ancestor(v, deep[v] - deep[u] - 1);
return father[u];
}
int len, block, st[max2 * 8 + 5], ed[max2 * 8 + 5], belong[max1 + 5];
struct Question
{
int id, L, R, x;
Question () {}
Question ( int __id, int __L, int __R, int __x )
{ id = __id, L = __L, R = __R, x = __x; }
}qus[max1 + 5];
int cnt;
int ans[max1 + 5];
int tmp[max2 * 10 + 5], num;
int s[max2 * 10 + 5], stop, anc[max2 * 10 + 5];
bool vis[max1 + 5];
int dis[max1 + 5], point[max1 + 5], Map[max1 + 5];
int sum[max2 * 10 + 5][max2 * 10 + 5];
vector <int> bin[max2 * 10 + 5][max2 * 10 + 5];
int f[max2 * 10 + 5][max2 * 10 + 5];
int Find ( int u )
{
return Map[u];
}
void Dfs ( int now, int fa, int depth, int root )
{
dis[now] = depth; point[now] = root;
for ( int v = head[now]; v; v = edge[v] )
{
if ( v == fa || vis[v] )
continue;
Dfs(v, now, depth + 1, root);
}
return;
}
int Query ( int u, int tim, int lim )
{
if ( tim == lim + 1 )
return u;
int pos = Map[u];
if ( tmp[pos] == u )
return f[pos][tim];
int pos1 = lim + 1, pos2 = lim + 1;
if ( sum[tim - 1][pos] + ( deep[tmp[pos]] - deep[u] ) <= lim )
{
vector <int> &down = bin[pos][sum[tim - 1][pos] + ( deep[tmp[pos]] - deep[u] ) + base];
if ( !down.empty() && down.back() >= tim )
pos1 = ( *lower_bound(down.begin(), down.end(), tim - 1) ) + 1;
}
if ( sum[tim - 1][pos] - ( deep[u] - deep[tmp[anc[pos]]] ) >= -lim )
{
vector <int> &up = bin[pos][sum[tim - 1][pos] - ( deep[u] - deep[tmp[anc[pos]]] ) + base];
if ( !up.empty() && up.back() >= tim )
pos2 = ( *lower_bound(up.begin(), up.end(), tim - 1) ) + 1;
}
if ( pos1 == lim + 1 && pos2 == lim + 1 )
{
int k = sum[lim][pos] - sum[tim - 1][pos];
k = deep[tmp[pos]] - deep[u] - k;
return Kth_Ancestor(tmp[pos], k);
}
if ( pos1 < pos2 )
return f[pos][pos1];
return f[anc[pos]][pos2];
}
void Solve ( int id )
{
num = 0;
for ( int i = st[id]; i <= ed[id]; i ++ )
tmp[++num] = A[i];
sort(tmp + 1, tmp + 1 + num, [&] ( const int &x, const int &y ) { return dfn[x] < dfn[y]; });
num = unique(tmp + 1, tmp + 1 + num) - ( tmp + 1 );
for ( int i = num - 1; i >= 1; i -- )
tmp[++num] = Get_Lca(tmp[i], tmp[i + 1]);
tmp[++num] = 1;
sort(tmp + 1, tmp + 1 + num, [&] ( const int &x, const int &y ) { return dfn[x] < dfn[y]; });
num = unique(tmp + 1, tmp + 1 + num) - ( tmp + 1 );
stop = 0;
for ( int i = 1; i <= num; i ++ )
{
while ( stop > 1 && Get_Lca(tmp[i], tmp[s[stop]]) != tmp[s[stop]] )
--stop;
if ( stop )
anc[i] = s[stop];
s[++stop] = i;
}
memset(vis + 1, 0, sizeof(bool) * n);
for ( int i = 1; i <= num; i ++ )
{
int u = tmp[i];
while ( u && !vis[u] )
{
vis[u] = true;
u = father[u];
}
}
for ( int i = 1; i <= n; i ++ )
if ( vis[i] )
Dfs(i, 0, 0, i);
Map[1] = 1;
for ( int i = 2; i <= num; i ++ )
for ( int k = dfn[tmp[i - 1]] + 1; k <= dfn[tmp[i]]; k ++ )
Map[rk[k]] = i;
int lim = ed[id] - st[id] + 1;
for ( int i = 0; i <= lim; i ++ )
memset(sum[i] + 1, 0, sizeof(int) * num);
for ( int i = 0; i <= num; i ++ )
for ( int j = base - lim; j <= base + lim; j ++ )
bin[i][j].clear();
for ( int i = 1; i <= lim; i ++ )
{
int u = Map[A[st[id] + i - 1]];
for ( int k = 1; k <= num; k ++ )
{
if ( dfn[tmp[u]] >= dfn[tmp[k]] && dfn[tmp[u]] <= dfn[tmp[k]] + siz[tmp[k]] - 1 )
++sum[i][k];
else
--sum[i][k];
}
}
for ( int i = 1; i <= lim; i ++ )
for ( int j = 1; j <= num; j ++ )
sum[i][j] += sum[i - 1][j];
for ( int i = 1; i <= lim; i ++ )
for ( int j = 1; j <= num; j ++ )
bin[j][sum[i][j] + base].push_back(i);
for ( int i = lim; i >= 1; i -- )
{
for ( int j = 1; j <= num; j ++ )
{
f[j][i] = Query(Move(tmp[j], A[st[id] + i - 1]), i + 1, lim);
}
}
for ( int i = 1; i <= cnt; i ++ )
{
if ( belong[qus[i].L] < id && belong[qus[i].R] > id )
{
if ( dis[qus[i].x] >= lim )
qus[i].x = Kth_Ancestor(qus[i].x, lim);
else
qus[i].x = Query(Kth_Ancestor(qus[i].x, dis[qus[i].x]), dis[qus[i].x] + 1, lim);
}
}
return;
}
int main ()
{
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d%d", &n, &m, &q);
for ( int i = 2, u; i <= n; i ++ )
{
scanf("%d", &u);
edge[i] = head[u];
head[u] = i;
}
for ( int i = 1; i <= m; i ++ )
scanf("%d", &A[i]);
Find_Heavy_Edge(1, 0, 0);
Connect_Heavy_Edge(1, 1);
len = max(1.0, sqrt(m) * 0.4), block = m / len; st[0] = ed[0] = 0;
for ( int i = 1; i <= block; i ++ )
{
st[i] = ed[i - 1] + 1;
ed[i] = i * len;
}
ed[block] = m;
for ( int i = 1; i <= block; i ++ )
for ( int k = st[i]; k <= ed[i]; k ++ )
belong[k] = i;
for ( int i = 1, L, R, x; i <= q; i ++ )
{
scanf("%d%d%d", &L, &R, &x);
if ( belong[L] == belong[R] )
{
for ( int k = L; k <= R; k ++ )
x = Move(x, A[k]);
ans[i] = x;
}
else
{
for ( int k = L; k <= ed[belong[L]]; k ++ )
x = Move(x, A[k]);
qus[++cnt] = Question(i, L, R, x);
}
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl << endl;
cerr << "ok!" << endl;
for ( int i = 1; i <= block; i ++ )
{
Solve(i);
cerr << i << endl;
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl << endl;
for ( int i = 1; i <= cnt; i ++ )
{
for ( int k = st[belong[qus[i].R]]; k <= qus[i].R; k ++ )
qus[i].x = Move(qus[i].x, A[k]);
ans[qus[i].id] = qus[i].x;
}
for ( int i = 1; i <= q; i ++ )
printf("%d\n", ans[i]);
return 0;
}
T3 吃什么
考虑维护连续的极长的合法的 \(A\) 序列区间，对于一次询问 \([ql,qr]\) ， \(ql\) 和 \(qr\) 所在的区间可以通过特判贡献答案，对于其他区间，考虑到这些区间一定对应 \(B\) 序列上置换环上连续的一段，因此考虑求解置换环的 \(dfn\) 序，对于一个连续的合法区间 \([L,R]\) ，我们将 \([L,R]\) 插入到其包含的所有 dfn 序所对应的平衡树上，由于平衡树内所有区间互不相交，因此查询就是 dfn 序上的单点查询，平衡树上区间查询，可以使用树套树做到 \(O(n\log^2 n)\) 。
code
#include <cstdio>
#include <algorithm>
#include <set>
#include <cstring>
using namespace std;
const int max1 = 1e6;
const int inf = 0x3f3f3f3f;
int n, m, A[max1 + 5], B[max1 + 5];
int dfn[max1 + 5], dfs_clock, belong[max1 + 5], cnt, circleL[max1 + 5], circleR[max1 + 5];
struct Segment
{
int L, R;
Segment () {}
Segment ( int __L, int __R )
{ L = __L, R = __R; }
bool operator < ( const Segment &A ) const
{ return L < A.L; }
};
set <Segment> Set;
struct FHQ_Treap
{
#define lson(now) tree[now].son[0]
#define rson(now) tree[now].son[1]
struct Data
{
int son[2], rd, L, R, maxval;
}tree[max1 * 80 + 5];
int total;
void Clear ()
{
lson(0) = rson(0) = tree[0].L = tree[0].R = tree[0].maxval = total = 0;
return;
}
void Push_Up ( int now )
{
tree[now].maxval = max(tree[lson(now)].maxval, tree[rson(now)].maxval);
tree[now].maxval = max(tree[now].maxval, tree[now].R - tree[now].L + 1);
return;
}
void SplitL ( int now, int k, int &x, int &y )
{
if ( !now )
{ x = y = 0; return; }
if ( tree[now].L >= k )
y = now, SplitL(lson(now), k, x, lson(y));
else
x = now, SplitL(rson(now), k, rson(x), y);
Push_Up(now);
return;
}
void SplitR ( int now, int k, int &x, int &y )
{
if ( !now )
{ x = y = 0; return; }
if ( tree[now].R <= k )
x = now, SplitR(rson(now), k, rson(x), y);
else
y = now, SplitR(lson(now), k, x, lson(y));
Push_Up(now);
return;
}
int Merge ( int x, int y )
{
if ( !x || !y )
return x | y;
if ( tree[x].rd > tree[y].rd )
{
rson(x) = Merge(rson(x), y);
Push_Up(x);
return x;
}
lson(y) = Merge(x, lson(y));
Push_Up(y);
return y;
}
void Insert ( int &now, int L, int R )
{
int x, y, New;
SplitL(now, L, x, y);
New = ++total;
lson(New) = rson(New) = 0, tree[New].rd = rand();
tree[New].L = L, tree[New].R = R;
tree[New].maxval = R - L + 1;
now = Merge(Merge(x, New), y);
return;
}
void Delete ( int &now, int L, int R )
{
int x, y, z;
SplitL(now, L, x, y);
SplitR(y, R, y, z);
now = Merge(x, z);
return;
}
int Query ( int &now, int L, int R )
{
int x, y, z, res;
SplitL(now, L, x, y);
SplitR(y, R, y, z);
res = tree[y].maxval;
now = Merge(Merge(x, y), z);
return res;
}
#undef lson
#undef rson
}Tree;
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
int root[max1 * 4 + 5];
void Build ( int now, int L, int R )
{
root[now] = 0;
if ( L == R )
return;
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
return;
}
void Insert ( int now, int L, int R, int ql, int qr, int x, int y, int op )
{
if ( L >= ql && R <= qr )
{
if ( !op )
Tree.Insert(root[now], x, y);
else
Tree.Delete(root[now], x, y);
return;
}
int mid = L + R >> 1;
if ( ql <= mid )
Insert(lson(now), L, mid, ql, qr, x, y, op);
if ( qr > mid )
Insert(rson(now), mid + 1, R, ql, qr, x, y, op);
return;
}
int Query ( int now, int L, int R, int pos, int x, int y )
{
int res = Tree.Query(root[now], x, y);
if ( L == R )
return res;
int mid = L + R >> 1;
if ( pos <= mid )
res = max(res, Query(lson(now), L, mid, pos, x, y));
else
res = max(res, Query(rson(now), mid + 1, R, pos, x, y));
return res;
}
}Solve;
void Insert ( int L, int R, int op )
{
int x = dfn[A[L]], y = dfn[A[R]], w = belong[A[L]];
if ( R - L >= circleR[w] - circleL[w] )
Solve.Insert(1, 1, n, circleL[w], circleR[w], L, R, op);
else if ( x <= y )
Solve.Insert(1, 1, n, x, y, L, R, op);
else
{
Solve.Insert(1, 1, n, x, circleR[w], L, R, op);
Solve.Insert(1, 1, n, circleL[w], y, L, R, op);
}
return;
}
int main ()
{
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &A[i]);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &B[i]);
for ( int i = 1; i <= n; i ++ )
{
if ( !dfn[i] )
{
int x = i;
++cnt;
while ( !dfn[x] )
{
dfn[x] = ++dfs_clock;
belong[x] = cnt;
x = B[x];
}
circleL[cnt] = dfn[x], circleR[cnt] = dfs_clock;
}
}
Set.insert(Segment(0, 0)), Set.insert(Segment(n + 1, n + 1));
Tree.Clear();
Solve.Build(1, 1, n);
for ( int L = 1, R; L <= n; L = R + 1 )
{
R = L;
while ( R + 1 <= n && B[A[R]] == A[R + 1] )
++R;
Set.insert(Segment(L, R));
Insert(L, R, 0);
}
int op, L, R, x, y;
for ( int i = 1; i <= m; i ++ )
{
scanf("%d", &op);
if ( op == 1 )
{
scanf("%d%d", &x, &y);
set <Segment> :: iterator it = prev(Set.upper_bound(Segment(x, 0)));
L = it -> L, R = it -> R;
if ( x != 1 && L == x )
{
it = prev(Set.find(Segment(L, R)));
Insert(it -> L, it -> R, -1);
Set.erase(it);
}
if ( x != n && R == x )
{
it = next(Set.find(Segment(L, R)));
Insert(it -> L, it -> R, -1);
Set.erase(it);
}
Set.erase(Set.find(Segment(L, R)));
Insert(L, R, -1);
A[x] = y;
if ( x != 1 && B[A[x - 1]] != A[x] )
{
it = prev(Set.lower_bound(Segment(x, 0)));
Insert(( it -> R ) + 1, x - 1, 0);
Set.insert(Segment(( it -> R ) + 1, x - 1));
}
if ( x != n && B[A[x]] != A[x + 1] )
{
it = Set.lower_bound(Segment(x, 0));
Insert(x + 1, ( it -> L ) - 1, 0);
Set.insert(Segment(x + 1, ( it -> L ) - 1));
}
it = Set.lower_bound(Segment(x, 0));
L = ( prev(it) -> R ) + 1, R = ( it -> L ) - 1;
Set.insert(Segment(L, R));
Insert(L, R, 0);
}
else
{
scanf("%d%d%d", &L, &R, &x);
int ans = 0;
set <Segment> :: iterator p = prev(Set.upper_bound(Segment(L, 0))), q = prev(Set.upper_bound(Segment(R, 0)));
int down = circleL[belong[x]], up = circleR[belong[x]];
if ( belong[A[L]] == belong[x] )
{
int lim = min(R, p -> R);
bool flag = lim - L >= up - down;
flag |= dfn[A[L]] <= dfn[A[lim]] && ( dfn[x] >= dfn[A[L]] && dfn[x] <= dfn[A[lim]] );
flag |= dfn[A[L]] > dfn[A[lim]] && ( dfn[x] >= dfn[A[L]] || dfn[x] <= dfn[A[lim]] );
if ( flag )
ans = max(ans, lim - L + 1);
}
if ( belong[A[R]] == belong[x] )
{
int lim = max(L, q -> L);
bool flag = R - lim >= up - down;
flag |= dfn[A[lim]] <= dfn[A[R]] && ( dfn[x] >= dfn[A[lim]] && dfn[x] <= dfn[A[R]] );
flag |= dfn[A[lim]] > dfn[A[R]] && ( dfn[x] >= dfn[A[lim]] || dfn[x] <= dfn[A[R]] );
if ( flag )
ans = max(ans, R - lim + 1);
}
p = next(p), q = prev(q);
if ( ( p -> L ) <= ( q -> L ) )
ans = max(ans, Solve.Query(1, 1, n, dfn[x], L, R));
printf("%d\n", ans);
}
}
return 0;
}