Description
n<=1e5
Solution
- 考虑颜色覆盖的操作与LCT中的Access操作类似，所以可以（证明）得到连续段颜色的个数之和为nlogn级别的。
- 直接用LCT，每一个splay树都代表同一种颜色，刚开始有n棵，即每一条边都是虚边，然后Access一下，与LCT完全一样，再用个树状数组求逆序对个数。
- 当然离线下来用树链剖分，每条链用一个set维护不同的颜色也可以（难打得一批）
时间复杂度的证明
P.S.以下证明中的等于并不严格，只是为了计算大概的时间而进行的等价或近似的转换
LCT的Access
- LCT的Access操作的时间复杂度总共为nlogn（未考虑splay）（参考QTREE解法的一些研究_百度文库)
- 对整颗树进行树链剖分之后有轻边和重边，Access后有虚边和实边。
- Access操作就是将到根路径上的所有虚边变成实边。
- 时间为：将轻边变成实边+将重边变成实边
- 轻边的条数根据树剖为logn的。
- 下面考虑的都是所有操作的总时间
- 将为虚边的重边变实边=将为实边的重边变虚边（即变成虚边后才能变重边）+n（最后所有都是虚边）
- 将重边变虚边=将与它同一个出发点的的轻边变成实边
- 将轻边变为实边的总数又是nlogn的。
- 得出结论，总时间是nlogn的，均摊下来就是logn的。
该题每次操作的不同颜色总数=LCT复杂度
- 注意到刚开始并没有轻重链，每一个点都是独立的，而LCT是在有轻重链的基础上进行的。
- 所以假设我们钦定出重链，即暴力让每个点都加入实链中，并且钦定每条实链上的所有点颜色都相同，而这正同于将到根路径Access的意义（加入同一实链）。
- 而在钦定的过程中其实省略了n的不同颜色个数。
- 所以时间=n+O(Access)=O(Access)
- 时间就和LCT类似了。
辣鸡set
要考虑不少边界，着实没有LCT来的痛快
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
#define maxn 100005
using namespace std;
struct arr{
int x,i;
} a[maxn];
int cmp(arr a,arr b){return a.x<b.x;}
int n,i,j,k,c[maxn],x,y,cnt,ans,L[maxn][2];
int em,e[maxn],nx[maxn],ls[maxn];
int tot,dep[maxn],sz[maxn],g[maxn],top[maxn],fa[maxn],fr[maxn];
struct node{
int d,x;
node(int _d,int _x){d=_d,x=_x;}
};
int operator<(node a,node b){return a.d<b.d||a.d==b.d&&a.x<b.x;}
set<node> s[maxn];
set<node>::iterator it,it0;
struct Treearray{
int s[maxn];
void clear(int x){for(;x<=cnt;x+=x&-x)s[x]=0;}
void add(int x,int delta){for(;x<=cnt;x+=x&-x)s[x]+=delta;}
int sum(int x,int S=0){for(;x;x-=x&-x)S+=s[x];return S;}
} t;
void insert(int x,int y){
em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;
}
void DFS(int x){
sz[x]=1,g[x]=0;
for(int i=ls[x];i;i=nx[i]) {
dep[e[i]]=dep[x]+1,DFS(e[i]),sz[x]+=sz[e[i]];
if (!g[x]||sz[e[i]]>sz[g[x]]) g[x]=e[i];
}
}
void DFS2(int x,int p){
if (!p) fr[x]=++tot,top[x]=x,s[tot].insert(node(dep[x]-1,0));
else fr[x]=fr[p],top[x]=top[p];
s[fr[x]].insert(node(dep[x],c[x]));
if (g[x]) DFS2(g[x],x);
for(int i=ls[x];i;i=nx[i]) if (e[i]!=g[x])
DFS2(e[i],0);
}
int d[maxn];
void ADD(int cnt,int x){
ans+=cnt*t.sum(x-1);
t.add(x,cnt);
d[++d[0]]=x;
}
int main(){
freopen("road3.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&c[i]),a[i].x=c[i],a[i].i=i;
sort(a+1,a+1+n,cmp);
for(cnt=0,i=1;i<=n;i++){
if (i==1||a[i].x!=a[i-1].x) cnt++;
c[a[i].i]=cnt;
}
for(i=1;i<n;i++) {
scanf("%d%d",&L[i][0],&L[i][1]);
insert(L[i][0],L[i][1]);
fa[L[i][1]]=L[i][0];
}
dep[1]=1,DFS(1);
DFS2(1,0);
for(i=1;i<n;i++) {
while (d[0]) t.clear(d[d[0]--]);
ans=0;
int now=L[i][0],D=dep[L[i][0]];
while (now){
it=s[fr[now]].lower_bound(node(D,0));
node tmp=*it;
it0=it,it0--; node tmp0=*it0;
if (tmp.d==D) s[fr[now]].erase(it);
ADD(D-tmp0.d,tmp.x);
it=it0,tmp=tmp0;
while (tmp.x){
it0=it,it0--; tmp0=*it0;
ADD(tmp.d-tmp0.d,tmp.x);
s[fr[now]].erase(it);
it=it0,tmp=tmp0;
}
s[fr[now]].insert(node(D,c[L[i][1]]));
now=fa[top[now]],D=dep[now];
}
printf("%d
",ans);
}
}
阉割版LCT
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 100005
using namespace std;
struct arr{
int x,i;
} a[maxn];
int cmp(arr a,arr b){return a.x<b.x;}
struct node{
int s[2],f,sz,c;
} t[maxn];
int n,c[maxn],x,y,cnt,i,j,k,ans;
void read(int &x){
x=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}
struct Treearray{
int s[maxn];
void clear(int x){for(;x<=cnt;x+=x&-x)s[x]=0;}
void add(int x,int delta){for(;x<=cnt;x+=x&-x)s[x]+=delta;}
int sum(int x,int S=0){for(;x;x-=x&-x)S+=s[x];return S;}
} T;
int d[maxn];
void ADD(int x,int cnt){
ans+=cnt*T.sum(x-1);
T.add(x,cnt);
d[++d[0]]=x;
}
void update(int x){
t[x].sz=t[t[x].s[0]].sz+t[t[x].s[1]].sz+1;
}
int get(int x){return t[t[x].f].s[1]==x;}
int nroot(int x){return t[t[x].f].s[0]==x||t[t[x].f].s[1]==x;}
void rotate(int x){
int y=t[x].f,c=get(x); t[x].c=t[y].c;
t[y].s[c]=t[x].s[c^1]; t[x].s[c^1]=y;
if (t[y].s[c]) t[t[y].s[c]].f=y;
if (nroot(y)) t[t[y].f].s[get(y)]=x;
t[x].f=t[y].f; t[y].f=x;
update(y); update(x);
}
void splay(int x){
int y;
while (nroot(x)) {
y=t[x].f;
if (nroot(y)) {
if (get(x)==get(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
}
void access(int x,int first){
int y=0;
while (x){
splay(x);
if (x!=first) ADD(t[x].c,t[t[x].s[0]].sz+1);
if (t[x].s[1]) t[t[x].s[1]].c=t[x].c;
t[x].s[1]=y;
update(y=x),x=t[x].f;
}
}
int main(){
freopen("road3.in","r",stdin);
freopen("road.out","w",stdout);
read(n);
for(i=1;i<=n;i++) read(c[i]),a[i].x=c[i],a[i].i=i;
sort(a+1,a+1+n,cmp);
for(cnt=0,i=1;i<=n;i++){
if (i==1||a[i].x!=a[i-1].x) cnt++;
c[a[i].i]=cnt;
}
for(i=1;i<=n;i++) t[i].c=c[i],t[i].f=0,t[i].sz=1;
for(i=1;i<n;i++) {
read(x),read(y);
ans=0;
t[y].f=x;
access(y,y);
splay(y);
t[y].c=c[y];
while (d[0]) T.clear(d[d[0]--]);
printf("%d
",ans);
}
}