求助线段树分治+LCT
查看原帖
求助线段树分治+LCT
538677
Rad_Forever楼主2022/6/29 21:00
#include<bits/stdc++.h>
#define int long long
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define LL long long
#define mid (l+r>>1)
using namespace std;
const int N=4e5+5,limit=32766;

inline LL read() {
    LL x=0,w=0; char ch=getchar(); 
    while(!isdigit(ch)) w|=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return w?-x:x;
}

struct Edge { int x,y; LL z; }e[N<<1];
int node,n,m,topf,ia,sta[N],a[N*20],tp[N*20];
int hd[N<<2],to[N*20],ne[N*20],tc=1;
int fa[N],ch[N][2],pos[N];
LL sum,mx[N],val[N],ans[N];
bool f[N];

inline void Insert(int,int,int,int,int,int);
inline void Getans(int,int,int);
inline void Rotate(int);
inline void Splay(int);
inline int Getroot(int);
inline void Down(int);
inline void Del(int,int);
inline void update(int);
inline void add(int x,int v) { to[++tc]=v; ne[tc]=hd[x]; hd[x]=tc; }
inline void Access(int x) { for(int s=0;x;x=fa[s=x]) Splay(x), rc(x)=s, update(x); }
inline void Root(int x) { Access(x); Splay(x); f[x]^=1; swap(lc(x),rc(x)); }
inline bool Get(int x) { return rc(fa[x])==x; }
inline bool Isroot(int x) { return lc(fa[x])!=x && rc(fa[x])!=x; }
inline void Link(int x,int y) { Root(x); if(Getroot(y)^x) fa[x]=y; }

signed main() {
    n=read();
    for(int i=1;i<n;i++) 
        e[i].x=read(), e[i].y=read(), mx[i]=val[i]=e[i].z=read(), pos[i]=i;
    m=read(); node=n+m-1;
    for(int i=n,l,r;i<n+m;i++) {
        e[i].x=read()+node, 
        e[i].y=read()+node, 
        mx[i]=val[i]=e[i].z=read(), pos[i]=i, 
        l=read(), r=read();
        Insert(1,1,limit,l,r,i);
    }
    for(int i=1;i<n;i++) {
        e[i].x+=node, e[i].y+=node, sum+=e[i].z;
        Link(e[i].x,i), Link(e[i].y,i);
    }
    for(int i=node+1;i<=node+n;i++) pos[i]=i, mx[i]=val[i]=0; 
    Getans(1,1,limit);
    for(int i=1;i<=limit;i++) printf("%lld\n",ans[i]);
    return 0;
}

inline void Rotate(int x) {
    int f=fa[x],g=fa[f],o=Get(x),w=ch[x][o^1];
    if(!Isroot(f)) ch[g][Get(f)]=x;
    ch[x][o^1]=f; ch[f][o]=w;
    if(w) fa[w]=f;
    fa[f]=x; fa[x]=g;
    update(f); update(x);
}

inline void Splay(int x) {
    int f=0,y=x; sta[topf=1]=x;
    while(!Isroot(y)) sta[++topf]=y=fa[y];
    while(topf) Down(sta[topf--]);
    while(!Isroot(x)) {
        f=fa[x];
        if(!Isroot(f)) Rotate(Get(x)==Get(f)?f:x);
        Rotate(x);
    } 
}

inline int Getroot(int x) {
    Access(x); Splay(x);
    while(lc(x)) Down(x), x=lc(x);
    return Splay(x), x;
}

inline void Del(int x,int y) {
    Root(x);
    if(Getroot(y)!=x || fa[y]!=x || lc(y)) return ;
    fa[y]=rc(x)=0; update(x);
}

inline void Down(int k) {
    if(!f[k]) return ;
    if(lc(k)) f[lc(k)]^=1, swap(lc(lc(k)),rc(lc(k)));
    if(rc(k)) f[rc(k)]^=1, swap(lc(rc(k)),rc(rc(k)));
    f[k]=0;
}

inline void update(int k) {
    mx[k]=val[k]; pos[k]=k;
    if(lc(k)) if(mx[lc(k)]>mx[k]) mx[k]=mx[lc(k)], pos[k]=pos[lc(k)];
    if(rc(k)) if(mx[rc(k)]>mx[k]) mx[k]=mx[rc(k)], pos[k]=pos[rc(k)];
}

inline void Insert(int k,int l,int r,int L,int R,int p) {
    if(L<=l && R>=r) return add(k,p);
    if(L<=mid) Insert(k<<1,l,mid,L,R,p);
    if(R>mid) Insert(k<<1|1,mid+1,r,L,R,p);
}

inline void Getans(int k,int l,int r) {
    int g=ia;
    for(int i=hd[k],p,x,y,v;i;i=ne[i]) {
        p=to[i]; x=e[p].x; y=e[p].y;
        Root(x); Access(y); Splay(y);
        if(mx[y]>e[p].z) {
            sum-=(mx[y]-e[p].z);
            a[++ia]=v=pos[y]; tp[ia]=0;
			a[++ia]=p; tp[ia]=1;
            Del(e[v].x,v); 
            Del(e[v].y,v);
            Link(x,p); Link(y,p);
        }
    }
    if(l==r) ans[l]=sum+1;
    else Getans(k<<1,l,mid), Getans(k<<1|1,mid+1,r);
    int p,t;
    while(ia>g) {
		t=tp[ia], p=a[ia--];
		if(!t) f[p]=0, mx[p]=val[p],pos[p]=p,fa[p]=0,lc(p)=rc(p)=0,Link(p,e[p].x),Link(p,e[p].y), sum+=e[p].z;
		else Del(p,e[p].x), Del(p,e[p].y), sum-=e[p].z;
	}
}
2022/6/29 21:00
加载中...