[NOI Online 2022 提高组] 丹钓战
容易发现，无论从哪个点的开始，弹出一个点的点总是固定的，令 \(nxt_i\) 表示弹出点 \(i\) 的点的位置。\(l\) 肯定为答案，弹出 \(l\) 的点 \(nxt_l\) 为答案，弹出 \(nxt_l\) 的点 \(nxt_{nxt_l}\) 也是答案，可以使用倍增维护答案数量。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10,Lg=20;
int n,q,a[N],b[N],nxt[N][Lg+5],stk[N],top;
void solve(){
read(n),read(q);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<=n;i++){
read(b[i]);
}
for(int i=1;i<=n;i++){
while(top&&(a[stk[top]]==a[i]||b[stk[top]]<=b[i])){
nxt[stk[top]][0]=i;
top--;
}
stk[++top]=i;
}
for(int i=1;i<=Lg;i++){
for(int j=1;j<=n+1;j++){
nxt[j][i]=nxt[nxt[j][i-1]][i-1];
}
}
while(q--){
int l,r,ans=1;
read(l),read(r);
for(int i=Lg;i>=0;i--){
if(nxt[l][i]&&nxt[l][i]<=r){
ans+=(1<<i);
l=nxt[l][i];
}
}
write_endl(ans);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[ABC111D] Robot Arms
这种题容易想到二进制拆分，打表发现可以到达的点是一个菱形，且到达的点 \(x+y\) 均为奇数。将 \(x\) 或 \(y\) 平移一个单位，就可以使得到达的点 \(x+y\) 均为偶数。剩下的可以自行构造。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1010;
int x[N],y[N],n,pos[N],cnt;
void solve(){
read(n);
int tmp=-1;
for(int i=1;i<=n;i++){
read(x[i]),read(y[i]);
if(tmp==-1){
tmp=abs(x[i]+y[i])%2;
}
if(tmp!=abs(x[i]+y[i])%2){
puts("-1");
return;
}
}
if(tmp==1){
cnt=31;
write_endl(31);
pos[1]=1;
for(int i=1;i<=30;i++){
pos[i+1]=(1<<i);
}
for(int i=1;i<=31;i++){
write_space(pos[i]);
}
putchar('\n');
}
else{
cnt=32;
write_endl(32);
pos[1]=1;
for(int i=0;i<=30;i++){
pos[i+2]=(1<<i);
}
for(int i=1;i<=32;i++){
write_space(pos[i]);
}
putchar('\n');
}
for(int i=1;i<=n;i++){
int nowx=0,nowy=0;
string s="";
for(int j=cnt;j;j--){
int dx=x[i]-nowx,dy=y[i]-nowy;
if(abs(dx)>abs(dy)){
if(dx>0){
nowx+=pos[j];
s+='R';
}
else{
nowx-=pos[j];
s+='L';
}
}
else{
if(dy>0){
nowy+=pos[j];
s+='U';
}
else{
nowy-=pos[j];
s+='D';
}
}
}
reverse(s.begin(),s.end());
cout<<s<<'\n';
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
[eJOI2019] 异或橙子
一个数对于异或和的贡献为 \(a_i\times [2\not\mid(i-l+1)\times (r-i+1)]\)，当区间长度的为偶数时，\(i-l+1\) 和 \(r-i+1\) 必然一奇一偶，答案为 \(0\)。当区间长度为奇数时，只有下标奇偶性与 \(l,r\) 相同的点会产生贡献，用线段树维护即可。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,q,a[N];
struct Seg_Tree{
int ans[N<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
void push_up(int p){
ans[p]=ans[ls(p)]^ans[rs(p)];
}
void update(int p,int l,int r,int pos,int val){
if(l==r){
ans[p]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),l,mid,pos,val);
}
else{
update(rs(p),mid+1,r,pos,val);
}
push_up(p);
}
int query(int p,int l,int r,int q_l,int q_r){
// cerr<<p<<' '<<l<<' '<<r<<' '<<q_l<<' '<<q_r<<endl;
if(q_l<=l&&r<=q_r){
return ans[p];
}
int mid=(l+r)>>1,res=0;
if(q_l<=mid){
res=res^query(ls(p),l,mid,q_l,q_r);
}
if(q_r>mid){
res=res^query(rs(p),mid+1,r,q_l,q_r);
}
return res;
}
#undef ls(p)
#undef rs(p)
}tr[2];
signed main(){
read(n),read(q);
for(int i=1;i<=n;i++){
read(a[i]);
tr[i%2].update(1,1,n,i,a[i]);
}
while(q--){
// cerr<<q<<endl;
int opt,x,y;
read(opt),read(x),read(y);
if(opt==1){
tr[x%2].update(1,1,n,x,y);
}
else{
if((y-x+1)%2){
write_endl(tr[x%2].query(1,1,n,x,y));
}
else{write_endl(0);}
}
}
// cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
Yet Another LCP Problem
给出两种做法。
做法1
对于三个串 \(A,B,C\)，令 \(A\) 的字典序小于 \(B\)，\(B\) 的字典序小于 \(C\)。必然满足 \(\operatorname{lcp}(A,C)=\min(\operatorname{lcp}(A,B),\operatorname{lcp}(B,C))\)。
证明：\(A,B\) 前 \(\operatorname{lcp}(A,B)\) 个字符相同，\(B,C\) 前 \(\operatorname{lcp}(B,C)\) 个字符相同，所以 \(A,C\) 至少有前 \(\min(\operatorname{lcp}(A,B),\operatorname{lcp}(B,C))\) 个字母相同，即 \(\operatorname{lcp}(A,C)\ge\min(\operatorname{lcp}(A,B),\operatorname{lcp}(B,C))\)。若 \(\operatorname{lcp}(A,C)>\operatorname{lcp}(A,B)\)，则 \(B\) 在 \(A,C\) 比出前就已经不同与 \(A,C\)，必然存在 \(A>B\) 或 \(B>C\)，不符合条件，\(\operatorname{lcp}(A,C)\le\operatorname{lcp}(A,B)\)；同理 \(\operatorname{lcp}(A,C)\le operatorname{lcp}(B,C)\)。得 \(\operatorname{lcp}(A,C)\le \min(\operatorname{lcp}(A,C),\operatorname{lcp}(B,C))\)。
综上 \(\operatorname{lcp}(A,C)= \min(\operatorname{lcp}(A,C),\operatorname{lcp}(B,C)\)。
借助上述结论，我们可以将两个集合合并为一个集合，用一个点表示集合中的一个后缀，相邻两个位置的后缀的 \(\operatorname{lcp}\) 为边权，两个后缀的 \(\operatorname{lcp}\) 表示为两个点之间的最小瓶颈路。特殊处理一下 \(a_i=b_j\) 的 \(i,j\) 即可。
这里给出哈希求 \(\operatorname{lcp}\) 的代码（本人常数略大，未能通过此题），SA 也可以求。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10,base=1145141,mod=1e9+7;
int n,q,m,a[N],b[N],c[N];
int siz[N][2],fa[N];
ull Hash[N],mul[N];
ull ans;
char s[N];
int get_hash(int l,int r){
return (Hash[r]-Hash[l-1]*mul[r-l+1]%mod+mod)%mod;
}
int lcp(int x,int y){
int len=0,l=1,r=min(n-x+1,n-y+1);
while(l<=r){
int mid=(l+r)>>1;
if(get_hash(x,x+mid-1)==get_hash(y,y+mid-1)){
len=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
return len;
}
bool cmp1(int x,int y){
int len=lcp(x,y);
return s[x+len]<s[y+len];
}
int u[N],v[N],w[N],id[N];
bool cmp2(int x,int y){
return w[x]>w[y];
}
int getfa(int x){
if(fa[x]!=x){
fa[x]=getfa(fa[x]);
}
return fa[x];
}
void solve(){
cin>>n>>q;
cin>>(s+1);
mul[0]=1;
for(int i=1;i<=n;i++){
Hash[i]=(Hash[i-1]*base%mod+s[i])%mod;
mul[i]=mul[i-1]*base%mod;
// cerr<<mul[i]<<' ';
}
while(q--){
int lena,lenb;
cin>>lena>>lenb;
for(int i=1;i<=lena;i++){
cin>>a[i];
}
for(int i=1;i<=lenb;i++){
cin>>b[i];
}
merge(a+1,a+lena+1,b+1,b+lenb+1,c+1);
ans=0;
for(int i=2;i<=lena+lenb;i++){
if(c[i]==c[i-1]){
ans+=(n-c[i]+1);
}
}
m=unique(c+1,c+lena+lenb+1)-c-1;
stable_sort(c+1,c+m+1,cmp1);
for(int i=1;i<=m;i++){
siz[c[i]][0]=siz[c[i]][1]=0;
fa[c[i]]=c[i];
}
for(int i=1;i<m;i++){
u[i]=c[i];
v[i]=c[i+1];
w[i]=lcp(c[i],c[i+1]);
id[i]=i;
}
for(int i=1;i<=lena;i++){
siz[a[i]][0]++;
}
for(int i=1;i<=lenb;i++){
siz[b[i]][1]++;
}
sort(id+1,id+m,cmp2);
for(int i=1;i<m;i++){
// cerr<<e[i].u<<' '<<e[i].v<<' '<<e[i].w<<endl;
int x=getfa(u[id[i]]),y=getfa(v[id[i]]);
ans+=1ll*w[id[i]]*siz[x][0]*siz[y][1];
ans+=1ll*w[id[i]]*siz[y][0]*siz[x][1];
fa[x]=y;
siz[y][0]+=siz[x][0];
siz[y][1]+=siz[x][1];
}
cout<<ans<<'\n';
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
做法2
将 \(a_i\) 和 \(b_i\) 分别按照 \(rk\) 排序，用 \(rk\) 代替 \(a_i,b_i\)，可以得到求 \(\operatorname{lcp}\) 的式子。
\(\operatorname{lcp}(i,j)=\begin{cases}n+1-sa_i，(i=j)\\ \min\limits_{k=i+1}^j ht_k，(i<j)\\ \min\limits_{k=j+1}^i ht_k，(i>j)\end{cases}\)。
由于第二、三种情况是一致的，所以我们只要会做一个，另一个反过来做一遍即可。
使用 ST 表，可以实现 \(O(\log n)-O(1)\) 的。
枚举 \(a_i\)，较 \(a_{i-1}\) 新增的 \(b_j\in (a_{i-1},a_i]\)，\(\operatorname{lcp}(a_i,b_j)\)，可以暴力计算。对于 \(b_j\le a_{i-1}\) 这个部分已经计算过 \(\operatorname{lcp}(a_{i-1},b_j)\)，将所有的 \(\operatorname{lcp}\) 对 \(\operatorname{lcp}(a_{i-1},a_i)\) 取 \(\min\) 可以算出 \(\operatorname{lcp}(a_i,b_j)\)。单点加，区间取 \(\min\)，所有数的和，可以使用权值线段树维护。
记得减去重复计算的 \(a_i=b_j\) 的情况。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,Lg=20;
int n,q,siza,sizb,a[N],b[N];
char s[N];
namespace SA{
int sa[N],rk[N],buc[N],ork[N<<1],id[N],pid[N],ht[N];
bool cmp(int x,int y,int w){
return ork[x]==ork[y]&&ork[x+w]==ork[y+w];
}
void build(){
int m=(1<<7),p=0;
for(int i=1;i<=n;i++){
rk[i]=s[i];
buc[rk[i]]++;
}
for(int i=1;i<=m;i++){
buc[i]=buc[i-1]+buc[i];
}
for(int i=n;i;i--){
sa[buc[rk[i]]--]=i;
}
for(int w=1;;w<<=1,m=p,p=0){
for(int i=n;i>n-w;i--){
id[++p]=i;
}
for(int i=1;i<=n;i++){
if(sa[i]>w){
id[++p]=sa[i]-w;
}
}
for(int i=0;i<=m;i++){
buc[i]=0;
}
for(int i=1;i<=n;i++){
pid[i]=rk[id[i]];
buc[pid[i]]++;
}
for(int i=1;i<=m;i++){
buc[i]=buc[i-1]+buc[i];
}
for(int i=n;i;i--){
sa[buc[pid[i]]--]=id[i];
}
for(int i=0;i<=n;i++){
ork[i]=rk[i];
}
p=0;
for(int i=1;i<=n;i++){
rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
}
if(p==n){
break;
}
}
for(int i=1,k=0;i<=n;i++){
if(k){
k--;
}
while(s[i+k]==s[sa[rk[i]-1]+k]){
k++;
}
ht[rk[i]]=k;
}
}
}
namespace Seg_Tree{
ll ans[N<<2];
int cnt[N<<2],tag[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void clear(int p){
tag[p]=1;
ans[p]=cnt[p]=0;
}
void push_down(int p){
if(tag[p]){
tag[p]=0;
clear(ls(p));
clear(rs(p));
}
}
void push_up(int p){
ans[p]=ans[ls(p)]+ans[rs(p)];
cnt[p]=cnt[ls(p)]+cnt[rs(p)];
}
void update(int p,int l,int r,int pos,int val){
if(!pos){
return;
}
if(l==r){
cnt[p]+=val;
ans[p]+=1ll*val*l;
return;
}
int mid=(l+r)>>1;
push_down(p);
if(pos<=mid){
update(ls(p),l,mid,pos,val);
}
else{
update(rs(p),mid+1,r,pos,val);
}
push_up(p);
}
int query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
int res=cnt[p];
clear(p);
return res;
}
int mid=(l+r)>>1,res=0;
push_down(p);
if(q_l<=mid){
res+=query(ls(p),l,mid,q_l,q_r);
}
if(q_r>mid){
res+=query(rs(p),mid+1,r,q_l,q_r);
}
push_up(p);
return res;
}
}
int st[N][Lg+5],lg[N];
int lcp(int x,int y){
if(x==y){
return n+1-SA::sa[x];
}
else{
x++;
}
int l=lg[y-x+1];
return min(st[x][l],st[y-(1<<l)+1][l]);
}
void solve(){
read(n),read(q);
cin>>(s+1);
SA::build();
lg[0]=-1;
for(int i=1;i<=n;i++){
st[i][0]=SA::ht[i];
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<=Lg;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
ll ans;
while(q--){
ans=0;
read(siza),read(sizb);
for(int i=1;i<=siza;i++){
read(a[i]);
a[i]=SA::rk[a[i]];
}
sort(a+1,a+siza+1);
for(int i=1;i<=sizb;i++){
read(b[i]);
b[i]=SA::rk[b[i]];
}
// for(int i=1;i<=sizb;i++){
// cerr<<b[i]<<' ';
// }
// cerr<<endl;
sort(b+1,b+sizb+1);
for(int i=1,j=1;i<=siza;i++){
if(i==1){
Seg_Tree::clear(1);
}
else{
int LCP=lcp(a[i-1],a[i]),tmp=Seg_Tree::query(1,1,n,LCP+1,n);
if(LCP){
Seg_Tree::update(1,1,n,LCP,tmp);
}
}
while(j<=sizb&&b[j]<=a[i]){
Seg_Tree::update(1,1,n,lcp(b[j],a[i]),1);
j++;
}
ans+=Seg_Tree::ans[1];
}
for(int i=1,j=1;i<=sizb;i++){
if(i==1){
Seg_Tree::clear(1);
}
else{
int LCP=lcp(b[i-1],b[i]),tmp=Seg_Tree::query(1,1,n,LCP+1,n);
if(LCP){
Seg_Tree::update(1,1,n,LCP,tmp);
}
}
while(j<=siza&&a[j]<=b[i]){
if(a[j]==b[i]){
ans-=lcp(a[j],b[i]);
}
Seg_Tree::update(1,1,n,lcp(a[j],b[i]),1);
j++;
}
ans+=Seg_Tree::ans[1];
}
write_endl(ans);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Serval and Rooted Tree
容易想到的是二分权值，令 \(a_i=1\) 表示大于等于二分的权值，\(a_i=0\) 表示小于二分的权值，判断是否有可行方案使得 \(a_1=1\)。容易发现这个等价于令 \(d_x\) 表示 \(x\) 权值最大可以为以 \(x\) 为根的子树中叶子节点的数值中排名第 \(d_x\) 大的数值。答案为 \(k+1-d_1\)。
对于 \(\min\)，\(d_x=\sum\limits_{y\in son_x}d_y\)；
对于 \(\max\)，\(d_y=\min\limits_{y\in son_x}d_y\)。
两个都非常容易理解，若为 \(\min\)，必须小于等于所有儿子的权值，大于它的叶子的集合就为大于各儿子的叶子的集合的并，排名就为儿子排名之和；若为 \(\max\)，必须大于等于所有儿子的权值，大于它的叶子的集合就为所有大于儿子的集合中最小的一个。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
int n,opt[N],fa[N],k,f[N];
vector<int>e[N];
void dfs(int u){
if(e[u].size()==0){
k++;
f[u]=1;
return;
}
if(opt[u]==1){
f[u]=inf;
}
for(auto v:e[u]){
dfs(v);
if(opt[u]==1){
f[u]=min(f[u],f[v]);
}
else{
f[u]+=f[v];
}
}
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(opt[i]);
}
for(int i=2;i<=n;i++){
read(fa[i]);
e[fa[i]].pb(i);
}
dfs(1);
write_endl(k-f[1]+1);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
Xenia and Tree
这种树上动态询问点和点集路径的问题，一般是考虑点分树的，但是因为数据范围这里有更好的做法。
对于所有的操作进行分块，对于一个询问操作，红点会有两种情况，一种是在当前块内，块内最多有 \(B\) 个点，可以暴力找 \(lca\)，求距离。另一种是在块外，每次离开一个块时，对块内所有的点进行一次 bfs，更新所有点到红点距离的最小值，bfs 最多进行 \(\frac{n}{B}\) 次，一次最多更新 \(n\) 个点。以 \(\sqrt n\) 为块长，可以使复杂度达到 \(n\sqrt n\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pdi pair<double,int>
#define pb push_back
#define eps 1e-9
#define mp make_pair
using namespace std;
const int inf=1e9;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10,Lg=20;
int n,q,dfn[N],st[N][Lg+5],idx,lg[N],dis[N],dep[N],pos[N],B,head[N],tot;
struct edge{
int v,w,nxt;
}e[N<<1];
void add(int u,int v){
e[++tot].v=v;
e[tot].nxt=head[u];
head[u]=tot;
}
void dfs(int u,int fa){
dfn[u]=++idx;
dep[u]=dep[fa]+1;
st[dfn[u]][0]=fa;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa){
continue;
}
dfs(v,u);
}
}
int get(int x,int y){
return dfn[x]<dfn[y]?x:y;
}
int lca(int u,int v){
if(u==v){
return u;
}
u=dfn[u],v=dfn[v];
if(u>v){
swap(u,v);
}
// cerr<<v<<' '<<u<<' '<<v-u++<<' '<<v<<" "<<u<<endl;
int d=lg[v-u];
return get(st[u+1][d],st[v-(1<<d)+1][d]);
}
int Dis(int u,int v){
return dep[u]+dep[v]-dep[lca(u,v)]*2;
}
void bfs(int l,int r){
queue<int>q;
for(int i=l;i<=r;i++){
if(!pos[i]){
continue;
}
q.push(pos[i]);
dis[pos[i]]=0;
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(dis[v]>dis[u]+1){
dis[v]=dis[u]+1;
q.push(v);
}
}
}
}
void solve(){
memset(dis,0x3f,sizeof(dis));
read(n),read(q);
B=sqrt(q);
for(int i=1;i<n;i++){
int u,v;
read(u),read(v);
add(u,v);
add(v,u);
}
dfs(1,0);
lg[0]=-1;
for(int i=1;i<=n;i++){
lg[i]=lg[i>>1]+1;
}
for(int i=1;i<=Lg;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
pos[0]=1;
for(int i=1;i<=q;i++){
if(i%B==0){
bfs((i-1)/B*B,i-1);
}
int opt,x;
read(opt),read(x);
if(opt==1){
pos[i]=x;
}
else{
int ans=dis[x];
for(int j=i/B*B;j<=i;j++){
if(!pos[j]){
continue;
}
// cerr<<pos[j]<<' '<<i<<' '<<j<<endl;
ans=min(ans,Dis(x,pos[j]));
}
write_endl(ans);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}