P3250 [HNOI2016]网络 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • AcFirmament
    其实用 O(1) 的 LCA 是可以做到 O(n log n) 的
  • maoxiangui
    老哥你这每次都求一下lca,复杂度好像高了一点emmmmm......总复杂度都是O(nlog^2n),但是可以存一下LCA优化一下
  • 杜岱玮
    orz %%% tql
  • teafrogsf
    1L2L两位老哥大概是没看到BIT吧23333
  • CaptainSlow
    这个trick棒啊,我没想到写了个O(nlog^3n)的树剖[汗]
作者: Salamander 更新时间: 2018-03-28 19:17  在Ta的博客查看    8  

用时间线段树或者直接暴力维护是$O(n\log^3n)$的,虽然卡卡常可以过但是有更好的做法。

考虑二分答案,如果某个询问点被所有大于当前答案的路径所经过,那么答案小于等于当前答案,否则大于等于当前答案。查询经过一个点的路径条数,把路径两端点权加一,然后lca和lca父亲的点权减一,用树状数组维护一下子树权值和即可。

但是我们还要考虑一条路径在当前时刻是否出现,以及计算出比当前答案大的路径有多少条。

所以我们考虑整体二分。整体二分中当前部分的各个操作依旧是按照时间顺序进行的,可以同时维护当前时刻路径是否存在,以及计算出比当前答案大的路径有多少条。

假设当前二分的答案是mid,要处理的操作队列为q。我们只需要扫一遍q,如果是询问那么就查询一下经过它的路径,判断它下次会被丢到左边递归还是丢到右边递归;如果是修改,那么如果这次修改对应的路径权值大于mid,就进行修改,然后丢到右边递归,否则对当前情况下其他的询问没有影响,直接丢到左边递归即可。

复杂度$O(n\log^2n)$,不需要任何优化跑得飞快。

#include<bits/stdc++.h>
using std::vector;

#define For(i,_beg,_end) for(int i=(_beg),i##end=(_end);i<=i##end;++i)
#define Rep(i,_beg,_end) for(int i=(_beg),i##end=(_end);i>=i##end;--i)

template<typename T>T Max(const T &x,const T &y){return x<y?y:x;}
template<typename T>T Min(const T &x,const T &y){return x<y?x:y;}
template<typename T>int chkmax(T &x,const T &y){return x<y?(x=y,1):0;}
template<typename T>int chkmin(T &x,const T &y){return x>y?(x=y,1):0;}
template<typename T>void read(T &x){
    T f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    x*=f;
}

const int maxn=200010;
struct edge{
    int to,nxt;
}e[maxn];
struct Query{
    int op,t,x,res;
    bool operator<(const Query &b)const{return t<b.t;}
}q[maxn],ql[maxn],qr[maxn];
int n,m,num,head[maxn],c[maxn];
int fa[maxn],top[maxn],size[maxn],son[maxn],dep[maxn];
int A[maxn],B[maxn],C[maxn],tL[maxn],tR[maxn],dfn,mx;

void add(int,int);
int qry(int);
int qry(int,int);
void addedge(int,int);
void Dfs1(int,int);
void Dfs2(int,int);
int lca(int,int);
void Solve(int,int,int,int);
void modify(int,int,int);

int main(){
    read(n);read(m);
    For(i,1,n-1){
        int u,v;read(u);read(v);
        addedge(u,v);
    }
    Dfs1(1,0);Dfs2(1,1);
    For(i,1,m){
        read(q[i].op);
        q[i].t=i;
        if(!q[i].op){
            read(A[i]);read(B[i]);
            read(C[i]);
            q[i].x=i;
            chkmax(mx,C[i]);
        }
        else read(q[i].x);
    }
    Solve(-1,mx,1,m);
    std::sort(q+1,q+m+1);
    For(i,1,m) if(q[i].op==2) printf("%d\n",q[i].res);
    return 0;
}

void Solve(int l,int r,int L,int R){
    if(l==r){
        For(i,L,R) if(q[i].op==2) q[i].res=l;
        return;
    }
    int mid=(l+r)>>1,path=0,cntl=0,cntr=0;
    For(i,L,R){
        if(q[i].op==2){
            if(qry(tL[q[i].x],tR[q[i].x])==path) ql[++cntl]=q[i];
            else qr[++cntr]=q[i];
        }
        else{
            if(C[q[i].x]<=mid) ql[++cntl]=q[i];
            else{
                int v=q[i].op?-1:1;
                path+=v;
                modify(A[q[i].x],B[q[i].x],v);
                qr[++cntr]=q[i];
            }
        }
    }
    For(i,1,cntr) if(qr[i].op!=2){
        int v=qr[i].op?1:-1;
        modify(A[qr[i].x],B[qr[i].x],v);
    }
    For(i,1,cntl) q[L+i-1]=ql[i];
    For(i,1,cntr) q[L+cntl+i-1]=qr[i];
    if(cntl) Solve(l,mid,L,L+cntl-1);
    if(cntr) Solve(mid+1,r,L+cntl,R);
}
void modify(int x,int y,int v){
    int z=lca(x,y);
    add(tL[x],v);add(tL[y],v);add(tL[z],-v);
    if(fa[z]) add(tL[fa[z]],-v);
}
void Dfs1(int x,int f){
    dep[x]=dep[fa[x]=f]+1;
    size[x]=1;tL[x]=++dfn;
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=f){
            Dfs1(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
        }
    tR[x]=dfn;
}
void Dfs2(int x,int tp){
    top[x]=tp;
    if(son[x]) Dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].nxt)
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
            Dfs2(e[i].to,e[i].to);
}
int lca(int u,int v){
    int x=top[u],y=top[v];
    while(x!=y){
        if(dep[x]>dep[y]) x=top[u=fa[x]];
        else y=top[v=fa[y]];
    }
    return dep[u]<dep[v]?u:v;
}
void addedge(int u,int v){
    e[++num].to=v;e[num].nxt=head[u];head[u]=num;
    e[++num].to=u;e[num].nxt=head[v];head[v]=num;
}
void add(int x,int v){for(;x<=n;x+=x&-x) c[x]+=v;}
int qry(int x){
    int res=0;
    for(;x;x-=x&-x) res+=c[x];
    return res;
}
int qry(int l,int r){return qry(r)-qry(l-1);}

评论

  • TPLY
    ztO(YYB)Orz
  • 斯德哥尔摩
    orz!惊现yyb julao。。。
  • dsl2002
    这代码有点问题吧,查询递归到底层岂不是$O(nmlogn)$
  • Junlier_test
    %%% yyb Orz
  • 杜岱玮
    %%% yyb Orz
作者: yybyyb 更新时间: 2017-10-04 15:49  在Ta的博客查看    7  

这题真是相当的暴力。。。

树链剖分搞出DFS序,以及用来求LCA

既然是不在这个节点上的最大值

那就把除了这个路径上的点之外的所有点全部丢到一个堆里面

具体的讲:

类似于线段树套一个堆???

具体的实现还是看代码把。。。

但是我就喜欢强行把博客插进来

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<vector>
#define MAX 110000
#define lson (now<<1)
#define rson (now<<1|1)
using namespace std;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Line
{
    int v,next;
}e[MAX*2];
struct Link
{
    int l,r;
}li[MAX];
struct Record
{
    int u,v,w;
}tt[MAX];
inline bool operator <(Link a,Link b)
{
    if(a.l!=b.l)return a.l<b.l;
    else return a.r<b.r;
}
int size[MAX],hson[MAX];
int h[MAX],cnt=1,dep[MAX],top[MAX],ff[MAX];
inline void Add(int u,int v)
{
    e[cnt]=(Line){v,h[u]};
    h[u]=cnt++;
}
struct PQ
{
    priority_queue<int> Q1;
    priority_queue<int> Q2;
    void push(int x)
        {
            Q1.push(x);
        }
    void del(int x)
        {
            Q2.push(x);
        }
    int top()
        {
            while(!Q2.empty()&&Q1.top()==Q2.top()){Q1.pop();Q2.pop();}
            return Q1.empty()?-1:Q1.top();
        }
}t[MAX*5];
int tim,N,M,dfn[MAX];
void DFS1(int u,int f)
{
    size[u]=1;dep[u]=dep[f]+1;
    for(int i=h[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        ff[v]=u;
        DFS1(v,u);
        size[u]+=size[v];
        if(size[v]>size[hson[u]])hson[u]=v;
    }
}
void DFS2(int u,int tp)
{
    top[u]=tp;dfn[u]=++tim;
    if(hson[u])DFS2(hson[u],tp);
    for(int i=h[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==ff[u]||v==hson[u])continue;
        DFS2(v,v);
    }
}
void Update(int now,int l,int r,int al,int ar,int k,int opt)
{
    if(al==l&&ar==r)
    {
        opt?t[now].del(k):t[now].push(k);
        return;
    }
    int mid=(l+r)>>1;
    if(ar<=mid)Update(lson,l,mid,al,ar,k,opt);
    else if(al>mid)Update(rson,mid+1,r,al,ar,k,opt);
    else{Update(lson,l,mid,al,mid,k,opt);Update(rson,mid+1,r,mid+1,ar,k,opt);}
}
int Query(int now,int l,int r,int x)
{
    if(l==r)return t[now].top();
    int mid=(l+r)>>1;
    int ans=t[now].top();
    if(x<=mid)return max(ans,Query(lson,l,mid,x));
    else return max(ans,Query(rson,mid+1,r,x));
}
void Happen(int u,int v,int opt,int xx)
{
    int qq=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        li[++qq]=(Link){dfn[top[u]],dfn[u]};
        u=ff[top[u]];
    }
    if(dep[u]<dep[v])swap(u,v);
    li[++qq]=(Link){dfn[v],dfn[u]};
    sort(&li[1],&li[qq+1]);
    int Left=0;
    for(int i=1;i<=qq;Left=max(Left,li[i++].r))
        if(Left+1<li[i].l)Update(1,1,N,Left+1,li[i].l-1,xx,opt);
    if(Left<N)Update(1,1,N,Left+1,N,xx,opt);
}
int main()
{
    freopen("4538.in","r",stdin);
    N=read();M=read();
    for(int i=1;i<N;++i)
    {
        int u=read(),v=read();
        Add(u,v);Add(v,u);
    }
    DFS1(1,0);DFS2(1,1);
    for(int i=1;i<=M;++i)
    {
        int opt=read();
        if(opt==2)
        {
            int x=read();
            printf("%d\n",Query(1,1,N,dfn[x]));
        }
        else if(opt==1)
        {
            int r=read();
            Happen(tt[r].u,tt[r].v,opt,tt[r].w);
        }
        else
        {
            tt[i]=(Record){read(),read(),read()};
            Happen(tt[i].u,tt[i].v,opt,tt[i].w);
        }
    }
    return 0;
}

评论

  • chill
    NOOB
  • Siris
    NOOB
  • Frozen_Heart
    STO LZ OTL
  • CaptainSlow
    老梁太强啦!
作者: 破壁人 更新时间: 2018-01-03 20:05  在Ta的博客查看    7  

由于这道题的操作只与两个点之间的路径有关,因此以哪个节点为根不影响结果。

再分析题目其实就是一棵树支持添加和删除路径并支持单点询问,这就是树链剖分了。

因此我们随便以一个点为根,把树进行重链剖分加线段树维护。

由于题目要问的是不受某个点影响的最大重要度,

因此我们把每个线段树结点变成一个堆,

然后添加路径的时候把所有不在这条路径上的点所在的线段树结点的堆中加入这条路径的重要度,

因为这些点肯定不会影响这条路径的畅通。

那么直接O(N)的寻找所有不在这条路径上的点肯定会T那么我们采取更高效的办法:

在沿着重链向上跳的过程中,把所经过的重链的首尾记录下来排序之后把与之交错的区间加入线段树即可。

因为同一条重链在线段树中肯定是连续的。

问题在于题目还支持删除路径操作,那么怎么满足呢?

再维护一个堆,删除时把重要度加入这个堆,求值时判断一下两个堆的堆顶元素,

若相同同时pop掉,否则加入堆的堆顶元素就是要求的值。(常规操作,证明很简单就略去了)

当然仅仅使用以上操作你不但会被T飞而且会被M飞。

那么问题出在哪呢?

我们在用线段树求值的时候,一旦发现目标区间包含了当前区间那么当前区间所有值肯定会影响目标区间。

所以维护线段树时是不用下传和合并的。这样就节约了大量时间和空间。

经过层层优化终于可以AC了。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
struct opq
{
    int ax;
    int ay;
}kk[200001];
vector<int> a[200001];
priority_queue<int> segmenttree1[500001],segmenttree2[500001];
int n,m,size[200001],top[200001],position[200001];
int deep[200001],son[200001],fa[200001],z=0;
int u[200001],v[200001],importance[200001];
bool cmp(opq a1,opq a2)
{
    return a1.ax<a2.ax;
}
void dfs1(int o,int p)
{
    size[o]=1;
    fa[o]=p;
    deep[o]=deep[p]+1;
    if(a[o].empty()) return;
    int maxx=0;
    for(int i=0;i<a[o].size();i++)
        if(a[o][i]!=fa[o])
        {
            if(!size[a[o][i]]) dfs1(a[o][i],o);
            size[o]+=size[a[o][i]];
            if(size[a[o][i]]>maxx)
            {
                maxx=size[a[o][i]];
                son[o]=a[o][i];
            }
        }
}
void dfs2(int o,int p)
{
    z++;
    position[o]=z;
    top[o]=p;
    if(son[o]!=0) 
        dfs2(son[o],top[o]);
    for(int i=0;i<a[o].size();i++)
        if((a[o][i]!=son[o])&&(a[o][i]!=fa[o]))
            dfs2(a[o][i],a[o][i]);
}
void put1(int o,int p,int q,int r,int s,int t)//加入堆的操作
{
    if(q>r) return;
    if((q>=o)&&(r<=p)) 
    {
        segmenttree1[s].push(t);
        return;
    }
    int mid=(q+r)/2;
    if(p<=mid) put1(o,p,q,mid,s*2,t);else
    if(o>mid)put1(o,p,mid+1,r,s*2+1,t);else
    {put1(o,mid,q,mid,s*2,t);put1(mid+1,p,mid+1,r,s*2+1,t);}
}
void puttree1(int o,int p,int q)//加入堆的操作
{
    int yu=0;
    while(top[o]!=top[p])
    {
        if(deep[top[o]]<deep[top[p]]){int t=o;o=p;p=t;}
        kk[++yu].ay=position[o];
        kk[yu].ax=position[top[o]];
        o=fa[top[o]];
    }
    if(deep[o]>deep[p]){int t=o;o=p;p=t;}
    kk[++yu].ax=position[o];
    kk[yu].ay=position[p];
    sort(kk+1,kk+yu+1,cmp);//把所经过的重链的首尾记录下来排序
    kk[0].ay=0;
    kk[++yu].ax=n+1;
    for(int i=1;i<=yu;i++)
        if(kk[i-1].ay+1<=kk[i].ax-1)
            put1(kk[i-1].ay+1,kk[i].ax-1,1,n,1,q);//把与之交错的区间加入线段树。
}
void put2(int o,int p,int q,int r,int s,int t)//删除堆的操作
{
    if(q>r) return;
    if((q>=o)&&(r<=p))
    {
        segmenttree2[s].push(t);
        return;
    }
    int mid=(q+r)/2;
    if(p<=mid) put2(o,p,q,mid,s*2,t);else
    if(o>mid)put2(o,p,mid+1,r,s*2+1,t);else
    {put2(o,mid,q,mid,s*2,t);put2(mid+1,p,mid+1,r,s*2+1,t);}
}
void puttree2(int o,int p,int q)//删除堆的操作
{
    int yu=0;
    while(top[o]!=top[p])
    {
        if(deep[top[o]]<deep[top[p]]){int t=o;o=p;p=t;}
        kk[++yu].ay=position[o];
        kk[yu].ax=position[top[o]];
        o=fa[top[o]];
    }
    if(deep[o]>deep[p]){int t=o;o=p;p=t;}
    kk[++yu].ax=position[o];
    kk[yu].ay=position[p];
    sort(kk+1,kk+yu+1,cmp);
    kk[0].ay=0;
    kk[++yu].ax=n+1;
    for(int i=1;i<=yu;i++)
        if(kk[i-1].ay+1<=kk[i].ax-1)
            put2(kk[i-1].ay+1,kk[i].ax-1,1,n,1,q);
}
int get(int o,int p,int q,int r,int s)//回答询问,求值。
{
    int xxx=-1;
    if((q<=o)&&(r>=p))
    {
        while((!segmenttree1[s].empty())&&(!segmenttree2[s].empty()))
        {
            if(segmenttree1[s].top()!=segmenttree2[s].top())break;
            segmenttree1[s].pop();
            segmenttree2[s].pop();
        }
        if(!segmenttree1[s].empty()) xxx=segmenttree1[s].top();
    }
    if(q==r) return xxx;
    int mid=(q+r)/2;
    if(p<=mid) return max(xxx,get(o,p,q,mid,s*2));else
    if(o>mid)return max(xxx,get(o,p,mid+1,r,s*2+1));
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    memset(son,0,sizeof(son));
    memset(size,0,sizeof(size));
    dfs1(1,0);//重链剖分第一次dfs,求出每个结点的重儿子父亲和以其为根的子树大小。
    dfs2(1,1);//重链剖分第二次dfs,求出每个节点在线段树中的位置和所在重链的头。
    for(int i=1;i<=m;i++)
    {
        int yu;
        cin>>yu;
        if(yu==0){cin>>u[i]>>v[i]>>importance[i];puttree1(u[i],v[i],importance[i]);}
        if(yu==1){cin>>u[i];puttree2(u[u[i]],v[u[i]],importance[u[i]]);}
        if(yu==2){cin>>u[i];cout<<get(position[u[i]],position[u[i]],1,n,1)<<endl;}
    }
    return 0;
}

评论

  • 还没有评论
作者: xzz小蒟蒻 更新时间: 2018-10-31 17:46  在Ta的博客查看    2  

打一波广告:https://www.cnblogs.com/xzz_233/p/9884562.html

显然可以想到二分答案。二分一个答案mid,如果所有长度$\geq mid$的路径都过x,那么答案一定$<mid$,否则答案$\geq mid$。

那么就可以写出代码了,树状数组套动态开点线段树即可。时间复杂度$O(n(log_2n)^3)$

然后因为出题人卡空间就炸了。。。如果256M就能过了。。

#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,m,fir[100010],nxt[200010],dis[200010],id;
il vd link(int a,int b){
    nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
    nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
}
int dfn[100010],dep[100010],fa[100010],siz[100010],son[100010];
il vd dfs(int x){
    siz[x]=1;
    for(int i=fir[x];i;i=nxt[i]){
        if(dep[dis[i]])continue;
        dep[dis[i]]=dep[x]+1;
        fa[dis[i]]=x;
        dfs(dis[i]);
        siz[x]+=siz[dis[i]];
        if(siz[son[x]]<=siz[dis[i]])son[x]=dis[i];
    }
}
int top[100010];
il vd dfs2(int x,int tp){
    top[x]=tp;dfn[x]=++dfn[0];
    if(son[x])dfs2(son[x],tp);
    for(int i=fir[x];i;i=nxt[i])if(fa[x]!=dis[i]&&son[x]!=dis[i])dfs2(dis[i],dis[i]);
}
int o[200010],u[200010],v[200010],w[200010];
int uni_w[200010],uni_w_tot;
int cnt,rt[200010],ls[15000001],rs[15000001],lz[15000001];
#define mid ((l+r)>>1)
il vd _update(int&x,int l,int r,const int&L,const int&R,const int&d){
    if(!x)x=++cnt;
    if(L<=l&&r<=R){lz[x]+=d;return;}
    if(L<=mid)_update(ls[x],l,mid,L,R,d);
    if(mid<R)_update(rs[x],mid+1,r,L,R,d);
}
il int _query(int&x,int l,int r,const int&p){
    if(!x)return 0;
    if(l==r)return lz[x];
    if(p<=mid)return lz[x]+_query(ls[x],l,mid,p);
    else return lz[x]+_query(rs[x],mid+1,r,p);
}
#undef mid
il vd Update(const int&p,const int&l,const int&r,const int&d){
    int x=p;
    while(x<=uni_w_tot)_update(rt[x],1,n,l,r,d),x+=x&-x;
}
il int Query(const int&p,const int&l){
    int x=p,ret=0;
    while(x)ret+=_query(rt[x],1,n,l),x-=x&-x;
    return ret;
}
int t[200010];
il vd bit_update(int x,int d){while(x<=uni_w_tot)t[x]+=d,x+=x&-x;}
il int bit_query(int x){int r=0;while(x)r+=t[x],x-=x&-x;return r;}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<n;++i)link(gi(),gi());
    int RT=rand()%n+1;
    dep[RT]=1,dfs(RT),dfs2(RT,RT);
    for(int i=1;i<=m;++i){
        o[i]=gi();
        if(o[i]==0)u[i]=gi(),v[i]=gi(),w[i]=gi(),uni_w[++uni_w_tot]=-w[i];
        else if(o[i]==1){
            int t=gi();
            u[i]=u[t],v[i]=v[t],w[i]=w[t];
        }else if(o[i]==2)u[i]=gi();
    }
    std::sort(uni_w+1,uni_w+uni_w_tot+1);uni_w_tot=std::unique(uni_w+1,uni_w+uni_w_tot+1)-uni_w-1;
    for(int i=1;i<=m;++i)if(o[i]!=2)w[i]=std::lower_bound(uni_w+1,uni_w+uni_w_tot+1,-w[i])-uni_w;
    for(int i=1;i<=uni_w_tot;++i)uni_w[i]=-uni_w[i];
    for(int i=1;i<=m;++i){
        if(o[i]^2){
            int x=u[i],y=v[i],d=o[i]==0?1:-1;
            while(top[x]!=top[y])
                if(dep[top[x]]>dep[top[y]])Update(w[i],dfn[top[x]],dfn[x],d),x=fa[top[x]];
                else Update(w[i],dfn[top[y]],dfn[y],d),y=fa[top[y]];
            if(dfn[x]>dfn[y])std::swap(x,y);
            Update(w[i],dfn[x],dfn[y],d);
            bit_update(w[i],d);
        }else{
            if(!bit_query(uni_w_tot)){puts("-1");continue;}
            int l=1,r=uni_w_tot+1,mid;
            while(l<r){
                mid=((l+r)>>1);
                if(Query(mid,dfn[u[i]])==bit_query(mid))l=mid+1;
                else r=mid;
            }
            if(l<=uni_w_tot)printf("%d\n",uni_w[l]);
            else puts("-1");
        }
    }
    return 0;
}

然后学了一发神仙整体二分

大概就是说答案要用二分求,可以放在一起二分

大概就是void solve(int l,int r,int L,int R),就是$[L,R]$的操作/询问,操作的权值都$\in[l,r]$,这里面的查询都已经确定了在$[l,r]$范围内。

如果$l=r$直接更新答案就好了,否则要确定这里面所有查询的

按时间顺序操作,如果当前是修改而且权值$\geq mid$,就加入/删除一条u-v的路径;如果是询问就所有的路径是否都经过当前点即可,就能知道这个询问的答案是否$\geq mid$。具体实现可以简单树上差分。

然后递归调用下去。

然后代码为了卡常把$\geq$改成了$\leq$,具体见代码。。

#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x;
}
int n,m,fir[100010],nxt[200010],dis[200010],id;
il vd link(int a,int b){
    nxt[++id]=fir[a],fir[a]=id,dis[id]=b;
    nxt[++id]=fir[b],fir[b]=id,dis[id]=a;
}
int dfn[100010],dep[100010],fa[100010],siz[100010],son[100010];
il vd dfs(int x){
    siz[x]=1;
    for(int i=fir[x];i;i=nxt[i]){
        if(dep[dis[i]])continue;
        dep[dis[i]]=dep[x]+1;
        fa[dis[i]]=x;
        dfs(dis[i]);
        siz[x]+=siz[dis[i]];
        if(siz[son[x]]<=siz[dis[i]])son[x]=dis[i];
    }
}
int top[100010];
il vd dfs2(int x,int tp){
    top[x]=tp;dfn[x]=++dfn[0];
    if(son[x])dfs2(son[x],tp);
    for(int i=fir[x];i;i=nxt[i])if(fa[x]!=dis[i]&&son[x]!=dis[i])dfs2(dis[i],dis[i]);
}
struct ques{int o,u,v,w,i,lca;bool y;}s[200010],a[200010],b[200010];
int uni_w[200010],uni_w_tot,ans[200010];
int t[200010];
il vd update(int x,int d){while(x<=n)t[x]+=d,x+=x&-x;}
il int query(int x){int r=0;while(x)r+=t[x],x-=x&-x;return r;}
il vd solve(int l,int r,int L,int R){
    if(L>R)return;
    for(int i=L;i<=R;++i)if(s[i].o==2)goto GG;
    return;GG:;
    if(l==r){for(int i=L;i<=R;++i)if(s[i].i)ans[s[i].i]=l;return;}
    int mid=(l+r)>>1,tot=0,A=0,B=0;
    for(int i=L;i<=R;++i)
        if(s[i].o==2){
            if(query(dfn[s[i].u]+siz[s[i].u]-1)-query(dfn[s[i].u]-1)==tot)b[++B]=s[i];
            else a[++A]=s[i];
        }else if(s[i].w<=mid){
            int d=s[i].o?-1:1;
            tot+=d;
            update(dfn[s[i].u],d);update(dfn[s[i].v],d);
            update(dfn[s[i].lca],-d);if(s[i].lca!=1)update(dfn[fa[s[i].lca]],-d);
            a[++A]=s[i];
        }else b[++B]=s[i];
    memcpy(s+L,a+1,(sizeof(ques))*A);
    memcpy(s+L+A,b+1,(sizeof(ques))*B);
    for(int i=L;i<=R;++i)
        if(s[i].o!=2&&s[i].w<=mid&&s[i].y){
            int d=s[i].o?1:-1;
            update(dfn[s[i].u],d);update(dfn[s[i].v],d);
            update(dfn[s[i].lca],-d);if(s[i].lca!=1)update(dfn[fa[s[i].lca]],-d);
        }
    solve(l,mid,L,L+A-1),solve(mid+1,r,L+A,R);
}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<n;++i)link(gi(),gi());
    dep[1]=1,dfs(1),dfs2(1,1);
    for(int i=1;i<=m;++i){
        s[i].o=gi();
        if(s[i].o==0){
            s[i].u=gi(),s[i].v=gi(),s[i].w=gi(),uni_w[++uni_w_tot]=-s[i].w;s[i].y=1;
            int x=s[i].u,y=s[i].v;
            while(top[x]!=top[y]){
                if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
                else y=fa[top[y]];
            }
            s[i].lca=(dep[x]<dep[y])?x:y;
        }else if(s[i].o==1){
            int x=gi();
            s[i]=s[x],s[i].o=1;
            s[i].y=s[x].y=0;
        }else s[i].u=gi(),s[i].i=++ans[0];
    }
    uni_w[++uni_w_tot]=1;
    std::sort(uni_w+1,uni_w+uni_w_tot+1);uni_w_tot=std::unique(uni_w+1,uni_w+uni_w_tot+1)-uni_w-1;
    for(int i=1;i<=m;++i)if(s[i].o!=2)s[i].w=std::lower_bound(uni_w+1,uni_w+uni_w_tot+1,-s[i].w)-uni_w;
    for(int i=1;i<=uni_w_tot;++i)uni_w[i]=-uni_w[i];
    solve(1,uni_w_tot,1,m);
    for(int i=1;i<=ans[0];++i)printf("%d\n",uni_w[ans[i]]);
    return 0;
}

卡了一波常数就洛咕rk1,bzoj rk7了。。

评论

  • AcFirmament
    三个log强啊
作者: never_see 更新时间: 2017-03-16 22:42  在Ta的博客查看    2  

这是一个要开O2的TJ

强行树链剖分

强行在每个点上维护两个大根堆

一个表示进入的,一个表示删除的

堆顶相同则删掉

每一次删掉或添加一个网络将所有不再该网络上的点的堆中添加当前的网络

然后卡过


#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

template <typename Type> inline void Read( Type &in ){
    in=0;char ch=getchar();Type f=1;
    for(;ch> '9'||ch< '0';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())in=in*10+ch-'0';in*=f;
}

static const int MAXN = 1e5 +1;
static const int MAXM = MAXN<<1;

int n,m,Num,Ct,u,v,Opt,k,Ans;
int Nt[MAXM],H[MAXN],To[MAXM];
int Qu[MAXM],Qv[MAXM],Qw[MAXM];
int Size[MAXN],Top[MAXN],Son[MAXN],Rank[MAXN],Fa[MAXN],Dep[MAXN];

inline void Ins( int From,int _To ){
    Nt[++Num] = H[From];
    H[From] = Num;
    To[Num] = _To;
}

inline void Dfs1( int A ){
    Size[A] = 1;
    for( int i=H[A];i;i=Nt[i] ){
        int B = To[i];if( Fa[A]==B )continue;
        Fa[B] = A;Dep[B] = Dep[A] +1;
        Dfs1( B );
        Size[A] += Size[B];
        if( Size[B]>=Size[Son[A]] ) Son[A] = B;
    }
}

inline void Dfs2( int A,int Chain ){
    Rank[A] = ++Ct;
    Top [A] = Chain;
    if( Son[A] ) Dfs2( Son[A],Chain );
    for( int i=H[A];i;i=Nt[i] )
        if( To[i]!=Fa[A]&&To[i]!=Son[A] )
            Dfs2( To[i],To[i] );
}

struct Segment_Tree{
    priority_queue< int > Ext[2];
    inline int Get(){
        for( ;!Ext[0].empty()&&!Ext[1].empty()&&Ext[0].top()==Ext[1].top();Ext[0].pop(),Ext[1].pop());
        if( Ext[0].empty() ) return -1;
        return Ext[0].top();
    }
}Max[MAXN<<2];

inline void MF( int Nd,int l,int r,int s,int t,int w ){
    if( l>=s&&r<=t ){
        Max[Nd].Ext[Opt].push( w );
        return;
    }
    int Mid = ( l+r )>>1;
    if( Mid>=s )MF( Nd<<1,l,Mid,s,t,w );if( Mid<t )MF( Nd<<1|1,Mid+1,r,s,t,w );
}

inline void Query( int Nd,int l,int r,int s ){
    Ans = max( Ans,Max[Nd].Get() );
    if( l==r )return;
    int Mid = ( l+r )>>1;
    if( Mid>=s ) Query( Nd<<1,l,Mid,s );
    else Query( Nd<<1|1,Mid+1,r,s );
}

struct QUE{
    int l,r;
    inline bool operator < (QUE T)const{return l<T.l;}
}Que[MAXN];

inline void Solve( int A,int B,int C ){
    int Cnt = 0;
    while( Top[A]!=Top[B] ){
        if( Dep[Top[A]]<Dep[Top[B]] )A^=B^=A^=B;
        Que[++Cnt].l=Rank[Top[A]];Que[Cnt].r=Rank[A];
        A = Fa[Top[A]];
    }
    if( Rank[A]>Rank[B] )A^=B^=A^=B;
    Que[++Cnt].l=Rank[A];Que[Cnt].r=Rank[B];
    sort( Que+1,Que+1+Cnt );
    for( int i=1;i<=Cnt;i++ )if( Que[i-1].r+1<=Que[i].l-1 ) MF( 1,1,n,Que[i-1].r+1,Que[i].l-1,C );
    if( Que[Cnt].r+1<=n ) MF( 1,1,n,Que[Cnt].r+1,n,C );
}

int main(){

    Read( n );Read( m );
    for( int i=1;i< n;i++ )Read( u ),Read( v ),Ins( u,v ),Ins( v,u );
    Dfs1( 1 );Dfs2( 1,0 );
    for( int i=1;i<=m;i++ ){
        Read( Opt );
        switch( Opt ){
            case 0:Read( Qu[i] );Read( Qv[i] );Read( Qw[i] );Solve( Qu[i],Qv[i],Qw[i] );break;
            case 1:Read( u );Solve( Qu[u],Qv[u],Qw[u] );break;
            case 2:Read( u );Ans=-1;Query( 1,1,n,Rank[u] );printf("%d\n",Ans);break;
        }
    }
    return 0;
}```