[Ynoi2016]这是我自己的发明

|

第一道Ynoi,blog总要有个Ynoi题解来装x。

传送门

一句话题意:求区间相同颜色的数对数,上树做,要求支持换根。

在做这题之前我见过[Snoi2017]一个简单的询问,所以如果这是一个序列上的问题的话:

$f(l1,r1,l2,r2)$表示询问l1,r1,l2,r2的答案,显然四个关键字不能莫队,但是我们可以容斥。
$$
f(l1,r1,l2,r2)=f(1,r1,1,r2)-f(1,l1-1,l2,r2)-f(l1,r1,l2-1,r2)+f(1,l1-1,1,l2-1)
$$
很多问你两个区间满足什么条件的数对数都可以容斥成这样,比如[HAOI2011 Problem b]

这样一个询问就只有两个关键字了。

在树上的做法:

因为有换根的操作,所以可能会是一个区间对多个区间甚至多个区间对多个区间。

例如:三个区间[l1,r1],[l2,r2],[l3,r3]和三个个区间[l1‘,r1’],[l2’,r2’],[l3’,r3’]中的答案数。

把两边区间每一对都对应即可,就是3*3=9个询问。

换根的话分类讨论,如果新根不在x的子树内相安无事,否则x子树的区间就是除了x向新根那个方向的儿子的子树,以外的所有点,dfs序搞一搞就好了。

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
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
static char c;static int y;
for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
x*=y;
}
#else
void read(int&x){scanf("%d",&x);}
#endif
struct node{
int next,to;
}w[400001];
struct ques{
int h,l,r,f;
}q[8000011];
struct ls{
int h,z;
}a[100001];
int rt,now,num,hs[100001],head[100001],idx[100001],size[100001];
int r,lx[201],n,b[100001],dfn[100001],fa[100001],bl[100001],cnt;
int m,l,ly[201],o[100001][2],que,fx[201],fy[201],blo,top[100001];
ll ans[500001],sum;
inline bool cmp2(ls c,ls d){return c.z<d.z;}
inline bool cmp(ques c,ques d){
if (bl[c.l]!=bl[d.l]) return c.l<d.l;
if (bl[c.l]&1) return c.r<d.r;
else return c.r>d.r;
// return (c.r<d.r)^(bl[c.l]&1)^1;
}
inline void add_edge(int x,int y){
w[++cnt].next=head[x];
w[cnt].to=y; head[x]=cnt;
}
void dfs1(int x,int da){
dfn[++num]=b[x]; idx[x]=num; size[x]=1;
for (int i=head[x]; i; i=w[i].next){
if (w[i].to!=da){
fa[w[i].to]=x;
dfs1(w[i].to,x);
size[x]+=size[w[i].to];
if (size[w[i].to]>size[hs[x]]) hs[x]=w[i].to;
}
}
}
void dfs2(int x,int tp){
top[x]=tp;
if (hs[x]) dfs2(hs[x],tp);
// top[x]=x;
for (int i=head[x]; i; i=w[i].next)
if (w[i].to!=hs[x]&&w[i].to!=fa[x])
dfs2(w[i].to,w[i].to);
}
inline int find(int y,int x){
int u;
while (top[x]!=top[y]) u=top[x],x=fa[u];
if (x==y) return u; return hs[y];
}
inline void build(int x,int y){
int nx=0,ny=0;
int l1=idx[x],r1=idx[x]+size[x]-1;
int l2=idx[y],r2=idx[y]+size[y]-1;
if (x==rt) lx[++nx]=n,fx[nx]=1;
else
if (idx[x]<=idx[rt]&&idx[rt]<=idx[x]+size[x]-1){
int z=find(x,rt);
lx[++nx]=idx[z]-1; fx[nx]=1;
lx[++nx]=idx[z]+size[z]-1; fx[nx]=-1;
lx[++nx]=n; fx[nx]=1;
}
else{
lx[++nx]=r1; fx[nx]=1;
lx[++nx]=l1-1; fx[nx]=-1;
}
if (y==rt) ly[++ny]=n,fy[ny]=1;
else
if (idx[y]<=idx[rt]&&idx[rt]<=idx[y]+size[y]-1){
int z=find(y,rt);
ly[++ny]=idx[z]-1; fy[ny]=1;
ly[++ny]=idx[z]+size[z]-1; fy[ny]=-1;
ly[++ny]=n; fy[ny]=1;
}
else{
ly[++ny]=r2; fy[ny]=1;
ly[++ny]=l2-1; fy[ny]=-1;
}
for (int i=1; i<=nx; i++)
for (int j=1; j<=ny; j++)
if (lx[i]&&ly[j])
q[++que].h=now,q[que].l=lx[i],q[que].r=ly[j],q[que].f=fx[i]*fy[j];
}
inline void add(int x,int y){o[dfn[x]][y]++; sum+=o[dfn[x]][y^1];}
inline void del(int x,int y){o[dfn[x]][y]--; sum-=o[dfn[x]][y^1];}
int main(){
int x,y,opt;
read(n),read(m);
for (int i=1; i<=n; i++) read(a[i].z),a[i].h=i;
sort(a+1,a+n+1,cmp2);
for (int i=1; i<=n; i++){
b[a[i].h]=b[a[i-1].h]; if (a[i].z!=a[i-1].z) b[a[i].h]++;
}

// puts("dllxl");
for (int i=1; i<n; i++){
read(x),read(y);
add_edge(x,y); add_edge(y,x);
}
dfs1(1,0); dfs2(1,1); rt=1;
for (int i=1; i<=m; i++){
read(opt);
if (opt==1) read(rt);
else{
read(x),read(y);
now++; build(x,y);
}
}
blo=sqrt(n);
for (int i=1; i<=n; i++) bl[i]=(i-1)/blo+1;
sort(q+1,q+que+1,cmp);// return 0;
for (int i=1; i<=que; i++){
while (l<q[i].l) l++,add(l,0);
while (l>q[i].l) del(l,0),l--;
while (r<q[i].r) r++,add(r,1);
while (r>q[i].r) del(r,1),r--;
ans[q[i].h]+=sum*q[i].f;
}
for (int i=1; i<=now; i++) printf("%lld\n",ans[i]);
return 0;
}
文章目录
,
载入天数...载入时分秒... 字数统计:75.7k