练习情况

P2787 语文1（chin1）- 理理思维

开 \(26\) 棵线段树，区间覆盖，区间查询。

注意大小写不敏感。

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL int
#define Ld long double
#define l(p,id) tree[id][p].l
#define r(p,id) tree[id][p].r
#define sum(p,id) tree[id][p].sum
#define add(p,id) tree[id][p].add
const int N = 60005,M=20005;

LL n,m,x,y,op,a[N],k;
struct Segment_tree{
    LL l,r,sum,add;
}tree[30][N*4];

inline LL readc(){
    char ch=getchar();
    while(!((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))) ch=getchar();
    if((ch>='a'&&ch<='z')) return ch-'a'+1;else return ch-'A'+1;
}

void pushdown(LL p,LL id){
    if(add(p,id)==-1) return ;
    sum(p<<1,id)=(r(p<<1,id)-l(p<<1,id)+1)*add(p,id);
    sum(p<<1|1,id)=(r(p<<1|1,id)-l(p<<1|1,id)+1)*add(p,id);
    add(p<<1,id)=add(p<<1|1,id)=add(p,id);
    add(p,id)=-1;
    return  ;
}

void build(LL p,LL l,LL r,LL id){
    l(p,id)=l,r(p,id)=r;
    add(p,id)=-1;
    sum(p,id)=0;
    if(l==r){
        if(id==a[l]) sum(p,id)=1;
        return ;
    }
    LL mid=(l(p,id)+r(p,id))>>1;
    build(p<<1,l,mid,id);
    build(p<<1|1,mid+1,r,id);
    sum(p,id)=sum(p<<1,id)+sum(p<<1|1,id);
    return ;
}

void change(LL p,LL l,LL r,LL id,LL k){
    if(add(p,id)==k) return ;
    if(l<=l(p,id)&&r(p,id)<=r){
        sum(p,id)=(r(p,id)-l(p,id)+1)*k;
        add(p,id)=k;
        return ;
    }
    pushdown(p,id);
    LL mid=(l(p,id)+r(p,id))>>1;
    if(l<=mid) change(p<<1,l,r,id,k);
    if(r>mid) change(p<<1|1,l,r,id,k);
    sum(p,id)=sum(p<<1,id)+sum(p<<1|1,id);
    return ;
}

LL query(LL p,LL l,LL r,LL id){
    if(sum(p,id)==0) return 0;
    if(l<=l(p,id)&&r(p,id)<=r)
        return sum(p,id);
    pushdown(p,id);
    LL mid=(l(p,id)+r(p,id))>>1,val=0;
    if(l<=mid) val+=query(p<<1,l,r,id);
    if(r>mid) val+=query(p<<1|1,l,r,id);
    return val;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        a[i]=readc();
    for(int i=1;i<=26;i++) build(1,1,n,i);
    for(int i=1;i<=m;i++){
        cin>>op>>x>>y;
        if(op==1){
            k=readc();
            cout<<query(1,x,y,k)<<endl;
        }else
        if(op==2){
            k=readc();
            for(int j=1;j<=26;j++)
            change(1,x,y,j,0);
            change(1,x,y,k,1);
        }else
        if(op==3){
            LL len=x;
            for(int j=1;j<=26;j++){
                LL t=query(1,x,y,j);
                change(1,x,y,j,0);
                if(t) change(1,len,len+t-1,j,1);
                len+=t;
            }
        }
    }
	return 0;
}

P5536 【XR-3】核心城市

树的直径模板

找到直径中点，以中点为根，遍历统计每个点能走多远。

前 \(k\) 远的为核心城市，第 \(k+1\) 远距离加 \(1\) 为答案。

Code:

树的直径

P2491 [SDOI2011] 消防

P1099 [NOIP2007 提高组] 树网的核

找出树的直径，从一个端点开始尺取，统计直径上两端到路径的最小值。

从直径上每个点搜与该点相连的树边，统计距离。

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N = 300005,M=20005;

LL n,d[N],id,st,s,sq,id1,last[N];
LL head[N],val[N*2],net[N*2],len[N*2],idx=1;
bool vis[N];

void add(LL x,LL y,LL w){
    val[++idx]=y,len[idx]=w;
    net[idx]=head[x];
    head[x]=idx;
    return ;
}

void dfs(LL x,LL fa){
    if(d[x]>st) id=x,st=d[x];
    for(int i=head[x];i;i=net[i]){
        LL v=val[i];
        if(vis[v]||v==fa) continue;
        last[v]=x,d[v]=d[x]+len[i];
        dfs(v,x);
    }
    return ;
}

int main(){
    cin>>n>>sq;
    for(int i=1;i<n;i++){
        LL u,v,w;
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    dfs(1,1);
    d[id]=0,last[id]=0,st=0,id1=id;
    dfs(id,id);
    LL ans=0x3f3f3f3f3f;
    LL a=id;
    for(int i=id;i;i=last[i]){
        while(last[a]&&d[i]-d[last[a]]<=sq) a=last[a];//尺取两端点
        ans=min(ans,max(d[a],d[id]-d[i]));//d[a]为到id1的距离，d[id]-d[i]为到id的距离
        vis[i]=1;
    }
    for(int i=id;i;i=last[i]){
        d[i]=0;
        dfs(i,i);//树上点到直径的距离
    }
    for(int i=1;i<=n;i++) ans=max(ans,d[i]);
    printf("%lld\n",ans);
	return 0;
}

P4408 [NOI2003] 逃学的小孩

树的直径两端必为 \(A\)、$ B$，从直径上的点开始枚举 \(C\) 即可

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N = 300005,M=20005;

LL n,d[N],id,st,s,sq,id1,last[N],m,dis[N],d1[N];
LL head[N],val[N*2],net[N*2],len[N*2],idx=1;
bool vis[N];

struct node{
    LL fa,len;
}t[N];

void add(LL x,LL y,LL w){
    val[++idx]=y,len[idx]=w;
    net[idx]=head[x];
    head[x]=idx;
    return ;
}

void dfs(LL x,LL fa){
    if(d[x]>st) id=x,st=d[x];
    for(int i=head[x];i;i=net[i]){
        LL v=val[i];
        if(vis[v]|v==fa) continue;
        t[v].fa=x,t[v].len=len[i];
        d[v]=d[x]+len[i];
        dfs(v,x);
    }
    return ;
}

void dfs1(LL x,LL fa,LL k1,LL k2){
    for(int i=head[x];i;i=net[i]){
        LL v=val[i];
        if(vis[v]|v==fa) continue;
        d1[v]=d1[x]+len[i];
        dis[v]=k1>k2?d1[v]+k2:d1[v]+k1;
        dfs1(v,x,k1,k2);
    }
    return ;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        LL u,v,w;
        cin>>u>>v>>w;
        add(u,v,w),add(v,u,w);
    }
    dfs(1,1);
    d[id]=0,t[id].fa=0,t[id].len=0,st=0,id1=id;
    dfs(id,id);
    LL ans=0;
    for(int i=id;i;i=t[i].fa){
        ans=max(ans,min(d[i],d[id]-d[i]));
        vis[i]=1;
    }
    for(int i=id;i;i=t[i].fa)
    dfs1(i,i,d[i],d[id]-d[i]);
    for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
    cout<<ans+d[id]<<endl;
	return 0;
}

P4281 [AHOI2008]紧急集合 / 聚会

两两求 \(LCA\)

若三个相同则为集合点,若有两个相同则另一个为集合点

别开 \(long\ long\)

\(ans=dep[u]+dep[v]+dep[c]-dep[lca_1]-dep[lca_2]-dep[lca_3]\)

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N = 500005,M=20005;

LL n,m,ans;
int head[N],net[N*2],val[N*2],idx=1;
int fa[N][35],dep[N];

void add(LL x,LL y){
    val[++idx]=y;
    net[idx]=head[x];
    head[x]=idx;
    return ;
}

void dfs(LL x,LL y){
    fa[x][0]=y;
    for(int i=1;i<=25;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=net[i]){
        LL v=val[i];
        if(v==y) continue;
        dep[v]=dep[x]+1;
        dfs(v,x);
    }
    return ;
}

LL LCA(LL x,LL y){
    if(dep[x]<dep[y])
    swap(x,y);
    for(int i=25;i>=0;i--)
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    if(x==y){
        ans-=dep[x];
        return x;
    }
    for(int i=25;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    ans-=dep[fa[x][0]];
    return fa[x][0];
}

int main(){
    cin>>n>>m;
    for(LL i=1,u,v;i<n;i++){
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    dep[1]=1;
    dfs(1,1);
    for(LL i=1,u,v,c;i<=m;i++){
        ans=0;
        cin>>u>>v>>c;
        ans=dep[u]+dep[v]+dep[c];
        LL lca1=LCA(u,v),lca2=LCA(v,c),lca3=LCA(u,c);
        if(lca1==lca2)
        printf("%lld ",lca3);
        else
        if(lca2==lca3)
        printf("%lld ",lca1);
        else
        printf("%lld ",lca2);
        printf("%lld\n",ans);
    }
	return 0;
}