J. 大秦酒店欢迎您
题解
我们考虑莫队
首先我们预处理出处于位置\(x\)的颜色下一次出现的位置\(nxt[x]\)以及上一次出现的位置\(pre[x]\)
莫队上维护一下信息：
\(Ans\)：\([l,r]\)的所有子区间的颜色数之和
\(num\)：\([l,r]\)的颜色数
\(Lans\)：\([l,l],[l,l + 1],[l,l + 2]...[l,r]\)这些区间的颜色数之和
\(Rans\)：\([r,r],[r - 1, r],[r - 2, r]...[l,r]\)这些区间的颜色数之和
\(cnt[x]\)：颜色\(x\)的出现次数
- 我们以左端点\(l\)向左扩张为例， 表示左端点向左扩张对维护的信息的影响
\(l:=l-1\)
\(cnt[col[l]]:=cnt[col[l]] + 1\)，颜色出现次数更新的同时更新\(num\)
\(Rans:=Rans + num\)
\(Lans := Lans + min(r, nxt[l]-1) - l + 1\)
\(Ans := Ans + Lans\)
- 那么对于其他操作的影响也是类似的
const int mod = (1ll << 32);
const int N = 5e5 + 10, M = 4e5 + 10;
const int B = sqrt(N) + 1;
int n, q, a[N];
int id[N], Ans, Lans, Rans, num, cnt[N], nxt[N], pre[N], ans[N], pos[N];
struct QUERY
{
int l, r, idx;
bool operator<(const QUERY &t) const
{
if (id[l] == id[t.l])
{
if (id[l] & 1)
return r < t.r;
else
return r > t.r;
}
else
return l < t.l;
}
} qry[N];
void del(int l, int r, int op)
{
if (op == 1) // Left
{
Ans -= Lans;
Lans -= min(r, nxt[l] - 1) - l + 1;
Rans -= num;
cnt[a[l]]--;
if (cnt[a[l]] == 0)
num--;
}
else // Right
{
Ans -= Rans;
Rans -= r - max(l, pre[r] + 1) + 1;
Lans -= num;
cnt[a[r]]--;
if (cnt[a[r]] == 0)
num--;
}
}
void add(int l, int r, int op)
{
if (op == 1) // Left
{
cnt[a[l]]++;
if (cnt[a[l]] == 1)
num++;
Rans += num;
Lans += min(r, nxt[l] - 1) - l + 1;
Ans += Lans;
}
else // Right
{
cnt[a[r]]++;
if (cnt[a[r]] == 1)
num++;
Lans += num;
Rans += r - max(l, pre[r] + 1) + 1;
Ans += Rans;
}
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
pre[i] = 0;
if (pos[a[i]])
{
pre[i] = pos[a[i]];
nxt[pos[a[i]]] = i;
}
pos[a[i]] = i;
nxt[i] = n + 1;
}
for (int i = 1; i <= q; ++i)
{
cin >> qry[i].l >> qry[i].r;
qry[i].idx = i;
}
for (int i = 1; i <= n; ++i) // 分块
id[i] = (i - 1) / B + 1;
sort(qry + 1, qry + q + 1); // 对查询进行排序
for (int i = 1, l = 1, r = 0; i <= q; ++i)
{
while (l > qry[i].l)
add(--l, r, 1);
while (r < qry[i].r)
add(l, ++r, 2);
while (l < qry[i].l)
del(l++, r, 1);
while (r > qry[i].r)
del(l, r--, 2);
ans[qry[i].idx] = Ans;
}
for (int i = 1; i <= q; ++i)
cout << ans[i] % mod << endl;
}
M. 斑马子树
\(1 \leq n \leq 10^5\)
题解
- 我们考虑如果一颗子树是斑马子树，那么这颗子树能够产生贡献的时间区间段是多少
- 我们考虑\(dp\)出子树\(u\)中最早变成斑马子树的时间戳\(l\)，最晚变成非斑马子树的时间戳\(r\)
- 那么\([l,r]\)的时间段上\(u\)的贡献一直为\(1\)，我们考虑差分，最后前缀和统计答案即可
// M. 斑马子树
const int N = 2e5 + 10, M = 4e5 + 10;
int n, t[N], mi[N], mx[N], ans[N];
vector<int> g[N];
void dfs(int u, int par)
{
mi[u] = mx[u] = t[u];
for (auto v : g[u])
{
if (v == par)
continue;
dfs(v, u);
mi[u] = min(mi[u], mi[v]);
mx[u] = max(mx[u], mx[v]);
}
ans[mi[u]]++;
ans[mx[u]]--;
}
void solve()
{
cin >> n;
for (int i = 2; i <= n; ++i)
{
int u;
cin >> u;
g[u].push_back(i);
g[i].push_back(u);
}
for (int i = 1; i <= n; ++i)
{
int u;
cin >> u;
t[u] = i;
}
dfs(1, 0);
for (int i = 1; i <= n; ++i)
{
ans[i] = ans[i - 1] + ans[i];
cout << ans[i] << "\n "[i < n];
}
}