[20220318联考] 数颜色
前言
典中典套路,但是典中典中典是连典中典都不知道。
题目
没有链接
给 \(n\) 个点的树,\(m\) 条路径,\(q\) 个询问,每次询问把 \([l_i,r_i]\) 的路径点亮,问点亮的连通块个数。
\(1\le n,m,q\le 10^5.\)
讲解
典中典套路是树上连通块个数=点-边。
接下来的问题就是怎么求路径(点和边)并。
这里还有个典中典做法是先重剖,把路径拆成很多 \(dfs\) 序连续的区间,然后用 \(set\) 动态维护(珂朵莉树)每条边(点)最后一次被覆盖的时间。
询问就是查一段时间内边(点)的个数,显然可以在维护时用树状数组之类的东西顺便也维护一下。
时间复杂度 \(O(n\log_2^2n)\)。
代码
//12252024832524
#pragma GCC optimize("Ofast")
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 100005;
int n,m,q;
int ans[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot;
struct edge{
int v,nxt;
}e[MAXN<<1];
void Add_Edge(int u,int v){
e[++tot] = edge{v,head[u]};
head[u] = tot;
}
void Add_Double_Edge(int u,int v){
Add_Edge(u,v);
Add_Edge(v,u);
}
int f[MAXN],d[MAXN],siz[MAXN],son[MAXN];
void dfs1(int x,int fa){
d[x] = d[fa] + 1; f[x] = fa; siz[x] = 1;
for(int i = head[x],v; i ;i = e[i].nxt)
if((v = e[i].v) ^ fa){
dfs1(v,x); siz[x] += siz[v];
if(siz[v] > siz[son[x]]) son[x] = v;
}
}
int tp[MAXN],dfn[MAXN],dfntot;
void dfs2(int x,int t){
tp[x] = t; dfn[x] = ++dfntot;
if(!son[x]) return;
dfs2(son[x],t);
for(int i = head[x],v; i ;i = e[i].nxt){
v = e[i].v;
if(v == f[x] || v == son[x]) continue;
dfs2(v,v);
}
}
vector > Q[MAXN],line[MAXN];
int B[MAXN];
int lowbit(int x){return x & -x;}
void Add(int x,int val){for(int i = x;i <= m;i += lowbit(i)) B[i] += val;}
int Sum(int x){int ret = 0;for(int i = x;i >= 1;i ^= lowbit(i)) ret += B[i];return ret;}
struct node{
int l,r,ID;
bool operator < (const node &px)const{
return l < px.l;
}
};
set s;
void TAdd(int l,int r,int ID){
if(!s.size()){s.insert(node{l,r,ID});Add(ID,r-l+1);return;}
auto R = s.upper_bound(node{r,0,0});
if(R != s.begin()){
--R;
if(R->r > r){
int newl = R->l,newr = r,rr = R->r,nID = R->ID;
s.erase(R);
s.insert(node{newl,newr,nID});
R = s.insert(node{newr+1,rr,nID}).first;
}
else ++R;
}
auto L = s.lower_bound(node{l,0,0});
if(L != s.begin()){
--L;
if(L->r >= l){
int newl = L->l,newr = l-1,rr = L->r,nID = L->ID;
s.erase(L);
s.insert(node{newl,newr,nID});
L = s.insert(node{newr+1,rr,nID}).first;
}
else ++L;
}
for(auto it = L;it != R;++ it) Add(it->ID,-(it->r-it->l+1));
s.erase(L,R);
s.insert(node{l,r,ID}); Add(ID,r-l+1);
}
void solve(int sg){
s.clear();
for(int i = 1;i <= m;++ i) B[i] = 0;
for(int i = 1;i <= m;++ i){
for(auto &A : line[i]) TAdd(A.first,A.second,i);
for(auto &A : Q[i]) ans[A.second] += sg * (Sum(i) - Sum(A.first-1));
}
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
n = Read(); m = Read(); q = Read();
for(int i = 1;i < n;++ i) Add_Double_Edge(Read(),Read());
dfs1(1,0); dfs2(1,1);
for(int i = 1,u,v;i <= m;++ i) {
u = Read(),v = Read();
while(tp[u] ^ tp[v]){
if(d[tp[u]] < d[tp[v]]) swap(u,v);
line[i].emplace_back(make_pair(dfn[tp[u]],dfn[u]));
u = f[tp[u]];
}
if(dfn[u] < dfn[v]) swap(u,v);
if(u ^ v) line[i].emplace_back(make_pair(dfn[v]+1,dfn[u]));
line[i].emplace_back(make_pair(dfn[v],dfn[v]));
}
for(int i = 1;i <= q;++ i){
int l = Read();
Q[Read()].emplace_back(make_pair(l,i));
}
solve(1);
for(int i = 1;i <= m;++ i) line[i].pop_back();
solve(-1);
for(int i = 1;i <= q;++ i) Put(ans[i],'\n');
return 0;
}
后记
哦,木示木干还有个 \(O(n\log_2n)\) 的线段树合并做法,但是我不太会。如果祂写了博客,我就把链接贴一下。