BZOJ 1146 [CTSC2008]网络管理Network

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1146

题意:求待修改的树上路径第K大。

思路:树状数组套主席树,首先对于原来的树我们建立一棵主席树,维护每个点到根节点的权值线段树,然后我们用树状数组维护增量,具体维护方式即用树状数组套动态开点的权值线段树维护每个点到根的链上的增量,这时候每个点的下标应该是它的 DFS 序下标,因为修改一个点的时候会影响到他的子树,而DFS序对应的子树正好为连续的一段下标,所以可以在左端点加一,右端点减一,很好的解决了这个问题。顺带一提的是今天才知道原来树链剖分也可以求LCA,而且写起来也挺方便的。

P.S:这里的第K大是真正意义上的第K大了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=8e4+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct qu{
    int a,b,k;
}q[maxn];
int n,Q,u,v,m,cnt,dfs_clock,crt[maxn],L[maxn],R[maxn],root[maxn],ls[maxn*128],rs[maxn*128],sum[maxn*128],w[maxn],mp[maxn<<1],dep[maxn],bel[maxn],id[maxn],fa[maxn],sz[maxn],son[maxn];
vector<int>G[maxn];
int Bin(int v){
    int l=1,r=m;
    while (l<=r){
        int mid=l+((r-l)>>1);
        if (mp[mid]==v) return mid;
        else if (v<mp[mid]) r=mid-1;
        else l=mid+1;
    }
    return 0;
}
void compress(){
    sort(mp+1,mp+1+m);
    int p=0;mp[++p]=mp[1];
    for (int i=2;i<=m;i++) if (mp[i]!=mp[i-1]) mp[++p]=mp[i];
    m=p;
    for(int i=1;i<=n;i++) w[i]=Bin(w[i]);
}
void dfs1(int u,int f){
    dep[u]=(f==-1?1:dep[f]+1);fa[u]=f;sz[u]=1;son[u]=-1;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if (son[u]==-1 || sz[v]>sz[son[u]]){
            son[u]=v;
        }
    }
}
void dfs2(int u,int f){
    id[u]=L[u]=++dfs_clock;
    bel[u]=f;
    if (son[u]==-1) return;
    dfs2(son[u],f);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
    R[u]=dfs_clock;
}
int lca(int u,int v){
    while (bel[u]!=bel[v]){
        if (dep[bel[u]]<dep[bel[v]]) swap(u,v);
        u=fa[bel[u]];
    }
    if (id[u]>id[v]) swap(u,v);
    return u;
}
void ins(int &y,int l,int r,int k,int d){
    sum[++cnt]=sum[y]+d;
    ls[cnt]=ls[y],rs[cnt]=rs[y];
    y=cnt;
    if (l==r) return;
    int mid=l+((r-l)>>1);
    if (k<=mid) ins(ls[y],l,mid,k,d);
    else ins(rs[y],mid+1,r,k,d);
}
void build(int u){
    root[u]=root[fa[u]];
    ins(root[u],1,m,w[u],1);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==fa[u]) continue;
        build(v);
    }
}
inline int lowbit(int x){return x&(-x);}
void add(int x,int v,int d){
    for (int i=x;i<=dfs_clock;i+=lowbit(i)) ins(crt[i],1,m,v,d);
}
int A[maxn*2],B[maxn*2],a,b;
bool check(int k){
    int suml=0,sumr=0;
    for (int i=1;i<=a;i++) suml+=sum[A[i]];
    for (int i=1;i<=b;i++) sumr+=sum[B[i]];
    return sumr-suml>=k;
}
int cal(){
    int suml=0,sumr=0;
    for (int i=1;i<=a;i++) suml+=sum[rs[A[i]]];
    for (int i=1;i<=b;i++) sumr+=sum[rs[B[i]]];
    return sumr-suml;
}
void query(int ql,int qr,int k){
    a=b=0;int p=lca(ql,qr);
    B[++b]=root[ql],B[++b]=root[qr];
    A[++a]=root[p],A[++a]=root[fa[p]];
    for (int i=L[ql];i;i-=lowbit(i)) B[++b]=crt[i];
    for (int i=L[qr];i;i-=lowbit(i)) B[++b]=crt[i];
    for (int i=L[p];i;i-=lowbit(i)) A[++a]=crt[i];
    for (int i=L[fa[p]];i;i-=lowbit(i)) A[++a]=crt[i];
    if (!check(k)){
        puts("invalid request!");
        return;
    }
    int l=1,r=m;
    while (l<r){
        int mid=l+((r-l)>>1);
        int num=cal();
        if (num>=k){
            l=mid+1;
            for (int i=1;i<=a;i++) A[i]=rs[A[i]];
            for (int i=1;i<=b;i++) B[i]=rs[B[i]];
        }
        else{
            r=mid;
            k-=num;
            for (int i=1;i<=a;i++) A[i]=ls[A[i]];
            for (int i=1;i<=b;i++) B[i]=ls[B[i]];
        }
    }
    printf("%d\n",mp[l]);
}
int main(){
    read(n),read(Q);
    for (int i=1;i<=n;i++) mp[++m]=read(w[i]);
    for (int i=1;i<n;i++){
        read(u),read(v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,-1);
    dfs2(1,1);
    for (int i=1;i<=Q;i++){
        read(q[i].k),read(q[i].a),read(q[i].b);
        if (!q[i].k) mp[++m]=q[i].b;
    }
    compress();
    build(1);
    for (int i=1;i<=Q;i++){
        int k=q[i].k,a=q[i].a,b=q[i].b;
        if (!k){
            add(L[a],w[a],-1),add(R[a]+1,w[a],1);
            w[a]=Bin(b);
            add(L[a],w[a],1),add(R[a]+1,w[a],-1);
        }
        else query(a,b,k);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注