此博客停更

遍地都是坑，一个一个填，由于本人懒数据结构弱的一笔所以就慢慢填

由于日常%了Claris，于是得到了Claris的课件，题都是课件里找的_(:зゝ∠)_

你要课件？你tm真的以为我会给你吗？

现在做了多少：  10/10

$3.7$  $qiancl:$喵的填坑填辣么慢

$3.10$  $qiancl:$嘿嘿嘿填完了

bzoj4293 把a数组排序线段树乱搞就行

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define nc() getchar()
inline ll read(){
	ll x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define N 500050
int i,j,k,m,n,x,y,L,R;ll a[N],V,last;
struct tree{ll mx,ad,sum,cr;}T[N<<2];
struct Q{ll d,b;bool operator <(const Q&b)const{return d<b.d;};}q[N];
#define max(a,b) ((a)>(b)?(a):(b))
#define up(k) (T[k].mx=max(T[k<<1].mx,T[k<<1|1].mx),T[k].sum=T[k<<1].sum+T[k<<1|1].sum)
void build(int k,int l,int r){
	T[k].cr=-1;if(l==r)return;
	int m=l+r>>1;build(lson),build(rson),up(k);
}
inline void down(int k,int l,int r){
	int m=l+r>>1;
	T[k<<1].ad+=T[k].ad,T[k<<1|1].ad+=T[k].ad;
	T[k<<1].sum+=(a[m]-a[l-1])*T[k].ad,T[k<<1|1].sum+=(a[r]-a[m])*T[k].ad;
	T[k<<1].mx+=(a[m]-a[m-1])*T[k].ad,T[k<<1|1].mx+=(a[r]-a[r-1])*T[k].ad,T[k].ad=0;
}
inline void Down(int k,int l,int r){
	int m=l+r>>1;
	T[k<<1].cr=T[k<<1|1].cr=T[k<<1].mx=T[k<<1|1].mx=T[k].cr;
	T[k<<1].sum=T[k].cr*(m-l+1),T[k<<1|1].sum=T[k].cr*(r-m);
	T[k<<1].ad=T[k<<1|1].ad=0,T[k].cr=-1;
}
void cover(int k,int l,int r){
	if(l>=L&&r<=R){T[k].mx=q[i].b,T[k].sum=(r-l+1)*q[i].b,T[k].ad=0,T[k].cr=q[i].b;return;}
	if(T[k].cr!=-1)Down(k,l,r);if(T[k].ad)down(k,l,r);
	int m=l+r>>1;
	if(L<=m)cover(lson);
	if(R>m)cover(rson);up(k);
}
int find(int k,int l,int r){
	if(l==r)return T[k].sum>q[i].b?l:l+1;if(T[k].cr!=-1)Down(k,l,r);if(T[k].ad)down(k,l,r);int m=l+r>>1;
	if(T[k<<1].mx>q[i].b)return find(lson);else return find(rson);up(k);
}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)a[i]=read();
	for(sort(a+1,a+n+1),i=1;i<=m;++i)q[i].d=read(),q[i].b=read();
	for(build(1,1,n),i=1;i<=n;++i)a[i]+=a[i-1];
	for(last=0,sort(q+1,q+m+1),i=1;i<=m;++i){
		V=q[i].d-last,last=q[i].d,T[1].ad+=V,T[1].sum+=(a[n])*V,T[1].mx+=V*(a[n]-a[n-1]),L=find(1,1,n),R=n;
		if(L<=R)V=T[1].sum,cover(1,1,n),printf("%lld\n",V-T[1].sum);
		else printf("%d\n",0);
	}
}

bzoj4383 考虑构图，对于每个$ki$，向比它小的点连一条权值为1的边，表示$ki-1>=ai$，构好图就可以直接拓扑DP了，但是直接连边是$n^2$的，所以要用线段树优化连边，考虑每个$ki$，比它小的一定是一段段连续的，于是可以新开一个节点，$ki$向这个节点连边，然后这个节点再向区间连边，这样就行了

#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100010
int i,j,l,r,k,m,n,x,y,s,a[N*6],g[N*6],cnt,last[N*6],mx,q[N*6],L,R,V,du[N*6];
map<pair<int,int>,int>mp;bool vis[N*6],f=1;
#define mr(l,r) make_pair(l,r)
struct edge{int to,next,v;}e[N*40];
inline void Mx(int &a,int b){if(b>a)a=b;}
inline void Mn(int &a,int b){if(b<a)a=b;}
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
inline void add(int u,int v,int w){
	e[++cnt]=(edge){v,last[u],w},last[u]=cnt,++du[v];
//	e[++cnt]=(edge){u,last[v],w},last[v]=cnt;
}
void build(int k,int l,int r){
	Mx(mx,k);mp[mr(l,r)]=k;if(l==r)return;int m=l+r>>1;
	add(k,k<<1,0),add(k,k<<1|1,0),build(lson),build(rson);
}
void Build(int k,int l,int r){
	if(l>=L&&r<=R){add(V,mp[mr(l,r)],1);return;}
	int m=l+r>>1;if(L<=m)Build(lson);if(R>m)Build(rson);
}
inline void sortDP(){
	int l=1,r=0;
	for(int i=1;i<=mx;++i)if(!du[i])q[++r]=i;
	if(!a[mp[mr(1,n)]])a[mp[mr(1,n)]]=1000000000;
	while(l<=r){
		int now=q[l++];vis[now]=1;
		for(int i=last[now],v;i;i=e[i].next){
			v=e[i].to;
			if(a[v])Mn(a[v],a[now]-e[i].v);else a[v]=a[now]-e[i].v;
			if(g[v]&&a[v]<g[v]){f=0;return;}
			if(!--du[v])q[++r]=v;
		}
	}
}
int main(){
	for(n=read(),s=read(),m=read(),build(1,1,n),i=1;i<=s;++i){
		x=read(),y=read();
		if(a[k=mp[mr(x,x)]]!=y&&a[k])return puts("NIE"),0;else g[k]=a[k]=y;
	}
	for(;m--;){
		l=read(),r=read(),k=read();
		for(q[1]=l-1,++mx,i=2;i<=k+1;++i)q[i]=read(),add(mp[mr(q[i],q[i])],mx,0);
		for(q[k+2]=r+1,i=2;i<=k+2;++i){
			L=q[i-1]+1,R=q[i]-1,V=mx;
			if(L<=R)Build(1,1,n);
		}
	}
	sortDP();if(f){
		for(i=1;i<=n;++i)if(!vis[mp[mr(i,i)]]||a[mp[mr(i,i)]]<1)return puts("NIE"),0;
		puts("TAK");
		for(i=1;i<n;++i)printf("%d ",a[mp[mr(i,i)]]);
		printf("%d\n",a[mp[mr(n,n)]]);
	}else puts("NIE");
}

bzoj1895 同poj3580，splay裸题，比较年轻的时候写的代码，感觉写的很浪

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')f=-1,ch=nc();for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return f*x;
}inline void read(char &c){for(c=nc();c==' '||c=='\n';c=nc());}
const int oo=1<<30;
struct Splay *null;
struct Splay{
	#define min(a,b) ((a)<(b)?(a):(b))
	Splay *ch[2];
	int v,s,mn,ad;bool flip;
	Splay(int _v=0):v(_v),s(1),mn(oo),flip(0),ad(0){ch[0]=ch[1]=null;}
	inline int cmp(int k)const{k-=ch[0]->s;if(k==1)return -1;return k<=0?0:1;}
	inline void ups(){
		s=ch[0]->s+ch[1]->s+1,mn=v;
		if(ch[0]!=null)mn=min(mn,ch[0]->mn);
		if(ch[1]!=null)mn=min(mn,ch[1]->mn);
	}
	inline void down(){
		if(ad)ch[0]->v+=ad,ch[1]->v+=ad,ch[0]->mn+=ad,ch[1]->mn+=ad,ch[0]->ad+=ad,ch[1]->ad+=ad,ad=0;
		if(flip)flip=0,swap(ch[0],ch[1]),ch[0]->flip^=1,ch[1]->flip^=1;
	}
};
Splay *root,N[200000+20],Null;
int i,j,k,m,n,x,y,a[100000+20];
inline void rotate(Splay *&o,int d){Splay *k=o->ch[d^1];o->ch[d^1]=k->ch[d],k->ch[d]=o,o->ups(),k->ups(),o=k;}
inline void splay(Splay *&o,int k){
	o->down();int d=o->cmp(k);
	if(d==1)k-=o->ch[0]->s+1;
	if(d!=-1){
		Splay *p=o->ch[d];p->down();
		int d2=p->cmp(k),k2=d2?k-p->ch[0]->s-1:k;
		if(d2!=-1)splay(p->ch[d2],k2),d==d2?rotate(o,d^1):rotate(o->ch[d],d);
		rotate(o,d^1);
	}
}
Splay *build(int l,int r){
	if(l>=r)return null;
	int m=l+r>>1;Splay *o=new Splay();o->v=o->mn=a[m];
	if(l<m)o->ch[0]=build(l,m);if(m+1<r)o->ch[1]=build(m+1,r);
	return o->ups(),o;
}
inline void init(){
	for(n=read(),memset(a,0x7f,sizeof a),i=1;i<=n;++i)a[i]=read();
	null=&Null,null->s=0,null->mn=oo,root=build(0,n+2);
}
inline Splay *out(Splay *&o,int k){splay(o,k);Splay *p=o->ch[0];return o->ch[0]=null,o->ups(),p;}
inline void merge(Splay *&o,Splay *p){splay(o,o->s),splay(p,1),o->ch[1]=p,o->ups();}
int main(){
	init(),m=read();
	while(m--){
		int l,r,v;char f;read(f);
		if(f=='A'){
			l=read(),r=read(),v=read();
			splay(root,l),splay(root->ch[1],r+1-root->ch[0]->s);
			root->ch[1]->ch[0]->ad+=v,root->ch[1]->ch[0]->v+=v,root->ch[1]->ch[0]->mn+=v;
		}else if(f=='R'){
			read(f),read(f),read(f);
			if(f=='E'){
				l=read(),r=read();if(l==r)continue;
				splay(root,l),splay(root->ch[1],r+1-root->ch[0]->s);
				root->ch[1]->ch[0]->flip^=1;
			}else{
				l=read(),r=read(),v=read();if(l==r)continue;
				splay(root,l),splay(root->ch[1],r+1-root->ch[0]->s);
				v%=root->ch[1]->ch[0]->s;
				if(v!=0){
					Splay *root2=root->ch[1]->ch[0],*root3=out(root2,root2->s-v+1);
					merge(root2,root3),root->ch[1]->ch[0]=root2,root->ch[1]->ch[0]->ups();
				}
			}
		}else if(f=='I'){
			l=read(),r=read();
			Splay *root2=out(root,l+2),*u=new Splay();u->v=u->mn=r,u->s=1;
			merge(root2,u),splay(root2,root2->s),splay(root,1),root->ch[0]=root2,root->ups();
		}else if(f=='D'){
			l=read();Splay *root2=out(root,l+1);
			out(root,2),merge(root2,root),root=root2,root->ups();
		}else{
			l=read(),r=read();
			splay(root,l),splay(root->ch[1],r+1-root->ch[0]->s);
			printf("%d\n",root->ch[1]->ch[0]->mn);
		}
	}
}

bzoj4381 对于$k$比较小的，可以$O(n)$求出每个点到根步伐为$k$的$ans$，对于$k$比较大的，直接暴力跳，我用了树剖，于是$k$取$\sqrt{n}$时有最优复杂度$O(n\sqrt{n})$，但是，不知道为什么，理论复杂度$O(\frac{n^2}{10})$跑的比$O(n\sqrt{n})$快到不知道哪里去了

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 50050
int i,j,k,n,m,x,y,v[N],b[N],c[N],cnt,last[N],o,q[N],l,fa[N],top[N],id[N],son[N],rk[N],now,sz[N],dep[N],d[N],len[11][N],dfs_clock,mark[N];
struct edge{int to,next;}e[N<<1];bool used[N],vis[N];
inline void add(int u,int v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
void dfs1(int x,int d){
	sz[x]=1,dep[x]=d;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]){
		fa[y]=x,dfs1(y,d+1),sz[x]+=sz[y];
		if(sz[son[x]]<sz[y])son[x]=y;
	}
}
void dfs2(int x,int d){
	top[x]=d,rk[id[x]=++now]=x;
	if(son[x])dfs2(son[x],d);
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]&&y!=son[x])dfs2(y,y);
}
#define max(a,b) ((a)>(b)?(a):(b))
inline int up(int x,int k){
	while(top[x]!=1)if(dep[x]-dep[top[x]]<k)k-=dep[x]-dep[top[x]]+1,x=fa[top[x]];else return rk[id[x]-k];
	return rk[max(0,id[x]-k)];
}
inline void work(int x,int k){
	len[k][x]=v[x];if(dep[x]>k)len[k][x]+=len[k][up(x,k)];
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x])work(y,k);
}
inline int lca(int l,int r){
	if(l==r)return l;
	for(;top[l]!=top[r];dep[top[l]]<dep[top[r]]?r=fa[top[r]]:l=fa[top[l]]);
	return dep[l]<dep[r]?l:r;
}
inline int dis(int l,int r){return dep[l]+dep[r]-(dep[lca(l,r)]<<1);}
inline void ad(int&ans,int x){if(mark[x]!=dfs_clock)ans+=v[x];mark[x]=dfs_clock;}
inline int Up(int l,int r,int k){
	int z=lca(l,r),len=dis(l,r),ans=0,p;++dfs_clock;
	for(;;){ad(ans,l),p=up(l,k);if(dep[p]>=dep[z])l=p;else break;}
	ad(ans,r),r=up(r,len%k);
	while(dep[r]>dep[z]){ad(ans,r),p=up(r,k);if(dep[p]>dep[z])r=p;else break;}
	return ans;
}
int main(){
	for(n=read(),i=1;i<=n;++i)v[i]=read();
	for(i=1;i<n;++i)add(read(),read());
	for(i=1;i<=n;++i)b[i]=read();for(i=1;i<n;++i)c[i]=read();
	for(o=10,i=1;i<n;++i)if(c[i]<=o)q[++l]=c[i],used[i]=1;
	for(dfs1(1,1),dfs2(1,1),i=1;i<=l;++i)if(!vis[q[i]])work(1,q[i]),vis[q[i]]=1;
	for(i=1;i<n;++i)if(used[i]){
		int l=b[i],r=b[i+1],z=lca(l,r),le=dis(l,r),x=up(l,(dep[l]-dep[z])/c[i]*c[i]),ans=len[c[i]][l]-len[c[i]][x]+v[x],y=up(r,le%c[i]),w=up(y,(dep[y]-dep[z])/c[i]*c[i]);
		if(y!=r)ans+=v[r];ans+=len[c[i]][y]-len[c[i]][w]+v[w];
		if(x==w)ans-=v[w];printf("%d\n",ans);
	}else printf("%d\n",Up(b[i],b[i+1],c[i]));
}

bzoj2908 身败名裂的一题，考虑每位分开独立，显然是互不影响的，树剖后线段树，线段树维护这个区间从左到右操作，输入$0$会得到什么，输入$1$会得到什么，以及从右到左同理，然后就是各种用树剖爬树了，从下往上直接爬就好，从上往下递归做就好，由于这题的独特性，线段树写法也不一样，从左往右要强制先做左，从右往左同理，于是只要$32$棵线段树乱搞就行，我刚开始$3$发$RE$，后来发现是读入优化写萎了_(:зゝ∠)_，乘$10$写成了乘$1$，呵呵，难怪样例妥妥的过了，改过来后果然$WA$了，为什么呢，居然是我单点修改写错了，诶果然写的不能太浪，$32$棵线段树我应该压成一棵做，这样应该能快很多，复杂度$O(k · n\log^2 n)$

#include<cstring>
#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
#define uint unsigned int
#define nc() getchar()
inline uint read(){
	uint x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define N 100100
uint i,j,K,m,n,x,y,L,cnt,l,r,top[N],sz[N],fa[N],id[N],ret,dep[N],son[N],rk[N],now,last[N],v[N],ans;
struct edge{uint to,next;}e[N<<1];bitset<32>o[N],V;char f;
struct tree{bool l[2],r[2];}T[32][N<<2];
void dfs1(uint x,uint d){
	dep[x]=d,sz[x]=1;
	for(uint i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]){
		fa[y]=x,dfs1(y,d+1),sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs2(uint x,uint d){
	top[x]=d,rk[id[x]=++now]=x;if(son[x])dfs2(son[x],d);
	for(uint i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]&&y!=son[x])dfs2(y,y);
}
inline void add(uint u,uint v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
inline void up(uint k){
	for(uint i=0;i<K;++i){
		T[i][k].l[0]=T[i][k<<1|1].l[T[i][k<<1].l[0]];
		T[i][k].r[0]=T[i][k<<1].r[T[i][k<<1|1].r[0]];
		T[i][k].l[1]=T[i][k<<1|1].l[T[i][k<<1].l[1]];
		T[i][k].r[1]=T[i][k<<1].r[T[i][k<<1|1].r[1]];
	}
}
void build(uint k,uint l,uint r){
	if(l==r){for(uint i=0;i<K;++i)T[i][k].r[0]=T[i][k].l[0]=(o[rk[l]][i]&0)^1,T[i][k].r[1]=T[i][k].l[1]=(o[rk[l]][i]&1)^1;return;}
	uint m=l+r>>1;build(lson),build(rson),up(k);
}
inline uint lca(uint l,uint r){
	for(;top[l]!=top[r];dep[top[l]]<dep[top[r]]?r=fa[top[r]]:l=fa[top[l]]);
	return dep[l]<dep[r]?l:r;
}
uint askr(uint k,uint l,uint r,uint L,uint R,uint pre){
	if(l>=L&&r<=R){
		uint ans=0;bitset<32>o=pre;
		for(uint i=0;i<K;++i)if(T[i][k].r[o[i]])ans+=1<<i;
		return ans;
	}uint m=l+r>>1;
	if(R<=m)return askr(lson,L,R,pre);
	if(L>m)return askr(rson,L,R,pre);
	uint o=askr(rson,m+1,R,pre);return askr(lson,L,m,o);
}
inline uint Up(uint l,uint r){
	for(ret=0;top[l]!=top[r];)ret=askr(1,1,n,id[top[l]],id[l],ret),l=fa[top[l]];
	return ret=askr(1,1,n,id[r],id[l],ret);
}
uint askl(uint k,uint l,uint r,uint L,uint R,uint pre){
	if(l>=L&&r<=R){
		uint ans=0;bitset<32>o=pre;
		for(uint i=0;i<K;++i)if(T[i][k].l[o[i]])ans+=1<<i;
		return ans;
	}uint m=l+r>>1;
	if(R<=m)return askl(lson,L,R,pre);
	if(L>m)return askl(rson,L,R,pre);
	uint o=askl(lson,L,m,pre);return askl(rson,m+1,R,o);
}
uint Down(uint l,uint r){
	if(dep[l]>dep[r])return ret;
	if(top[l]!=top[r])ret=Down(l,fa[top[r]]),ret=askl(1,1,n,id[top[r]],id[r],ret);
	else return ret=askl(1,1,n,id[l],id[r],ret);
}
#define max(a,b) ((a)>(b)?(a):(b))
inline uint go(uint x,uint k){
    while(top[x]!=1)if(dep[x]-dep[top[x]]<k)k-=dep[x]-dep[top[x]]+1,x=fa[top[x]];else return rk[id[x]-k];
    return rk[max(0,id[x]-k)];
}
inline uint query(uint l,uint r){
	uint Lca=lca(l,r),ans=0;
	ans=Up(l,Lca);
	if(dep[r]-dep[Lca]!=0)ans=Down(go(r,dep[r]-dep[Lca]-1),r);
	return ans;
}
inline void change(uint k,uint l,uint r){
	if(l==r){for(uint i=0;i<K;++i)T[i][k].r[0]=T[i][k].l[0]=(V[i]&0)^1,T[i][k].r[1]=T[i][k].l[1]=(V[i]&1)^1;return;}
	uint m=l+r>>1;if(m>=L)change(lson);else change(rson);up(k);
}
int main(){
//	freopen("2908.in","r",stdin);
//	freopen("2908.out","w",stdout);
	for(n=read(),m=read(),K=read(),i=1;i<=n;++i)o[i]=v[i]=read();
	for(i=1;i<n;++i)add(read(),read());
	for(dfs1(1,0),dfs2(1,1),build(1,1,n);m--;){
		read(f),l=read(),r=read();
		if(f=='Q')printf("%u\n",query(l,r));
		else L=id[l],V=r,change(1,1,n);
	}
}

bzoj3784 先点分，预处理出数组$q$，存的是所有点到当前重心的$dis$，于是对于一棵子树，合法的路径一定是$q[l]$到$q[r]$中某个数加上子树内某点到重心的距离，第$k$大很显然可以用堆来扩展状态，定义$(v,l,m,r,w)$，表示当前路径长$v$，在$l..r$中选出最大的$m$，加上$w$，以$v$构造大根堆，每次扩展出$l..m-1$与$m+1..r$两个状态，这里有个区间最值查询，可以用$st$表做到$O(1)$查询，复杂度$O(n\log^2 n)$

但这题让我明白了，不要相信$st$表的$O(1)$，直接用线段树跑的比它快到不知道哪里去了，第一次我$st$表跑了$7800ms$，把$st$表删了后，加了点黑科技，然后就飞起了233

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 50050
int i,j,k,m,n,x,y,cnt,last[N],root,allsz,sz[N],f[N],L,R,ed,can[N<<1],q[N*15],anscnt,mx[N*15][22],l[22];
struct node{
	int v,l,m,r,w;
	inline bool operator<(const node&b)const{return v<b.v;}
}pre[N*15];
struct edge{int to,next,v;}e[N<<1];
inline void add(int w,int v,int u){
	e[++cnt]=(edge){v,last[u],w},last[u]=cnt;
	e[++cnt]=(edge){u,last[v],w},last[v]=cnt;
}
inline void Mx(int&a,int b){if(b>a)a=b;}
void find(int x,int fa){
	sz[x]=1,f[x]=0;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa&&can[i])find(y,x),sz[x]+=sz[y],Mx(f[x],sz[y]);
	Mx(f[x],allsz-sz[x]);if(f[x]<f[root])root=x;
}
void dfs(int x,int fa,int w){
	q[++ed]=w,pre[++anscnt]=(node){L,R,w};
	for(int i=last[x];i;i=e[i].next)if(e[i].to!=fa&&can[i])dfs(e[i].to,x,w+e[i].v);
}
void work(int x){
	L=ed+1;for(int i=last[x];i;i=e[i].next)if(can[i])R=ed,dfs(e[i].to,x,e[i].v);
	pre[++anscnt]=(node){L,ed,0};
	for(int i=last[x];i;i=e[i].next)if(can[i])can[i^1]=0,f[0]=allsz=sz[e[i].to],find(e[i].to,root=0),work(root);
}
inline int max(int a,int b){return q[a]>q[b]?a:b;}
inline void build(int n){
	for(int i=1;i<=n;++i)mx[i][0]=i;
	int m=floor(log((double)n)/log(2.0));
	for(int i=0,o=1;i<=m;++i,o<<=1)l[i]=o;
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j){
			int t=j+l[i-1];
			if(t<=n)mx[j][i]=max(mx[j][i-1],mx[t][i-1]);
			else mx[j][i]=mx[j][i-1];
		}
}
priority_queue<node>Q;
inline int ask(int l,int r){
	int m=floor(log((double)(r-l+1))/log(2.0));
	return max(mx[l][m],mx[r-(1<<m)+1][m]);   
}
inline void insert(int l,int r,int w){
	if(l>r)return;int x=ask(l,r);
	Q.push((node){q[x]+w,l,x,r,w});
}
int main(){
	for(n=read(),m=read(),cnt=i=1,memset(can,1,sizeof can);i<n;++i)add(read(),read(),read());
	for(f[0]=allsz=n,find(1,root=0),work(root),build(ed),i=1;i<=anscnt;++i)insert(pre[i].v,pre[i].l,pre[i].m);
	while(m--){
		node now=Q.top();Q.pop(),printf("%d\n",now.v);
		insert(now.l,now.m-1,now.w),insert(now.m+1,now.r,now.w);
	}
}

bzoj4388 第一眼很眼熟，好像做过加强版，但仔细一看还是不一样0 0，先把$A$，$B$离散，然后线段树搞出离散掉的答案，然后考虑最大生成树，直接用$prim$做，然后发现其实$C$是没用的，用线段树维护还未加入的点与边，然后就和$prim$流程一样了，每次选权最大的边，把对应的点与该对应的边加进来，线段树上连边只要对应区间与对应限制序号连边就行了，在找连的边的时候只要线段树从上到下每个节点连的边都找就行了，找到一遍加入然后删掉，复杂度$O(n\log n)$，然而常数巨大_(:зゝ∠)_

#include<cstring>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 100100
#define ll long long
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define P pair<int,int>
int i,j,k,m,n,x,y,c,v[N<<3],seq[N<<1],L,R,V;ll ans;bool vis[N];
struct question{int l1,r1,l2,r2,v;inline void in(){l1=read(),r1=read(),l2=read(),r2=read(),v=read();}}que[N]; 
priority_queue<P >Q;
inline void Mn(int&a,int b){if(a<b)a=b;}
struct tree{
	int i,j,mx,hs[N<<1],len,cnt,last[N<<3],n,_n,L,R,V,v[N<<3];
	struct edge{int to,next;}e[N<<5];
	inline void pre(){for(hs[++n]=1,hs[++n]=len,sort(hs+1,hs+n+1),_n=n,n=0,i=1;i<=_n;++i)if(hs[i]!=hs[i-1])hs[++n]=hs[i];}
	inline void hash(int&a,int&b){a=lower_bound(hs+1,hs+n+1,a)-hs,b=lower_bound(hs+1,hs+n+1,b)-hs;}
	inline void check(){
		for(int i=1;i<n;++i)if(hs[i+1]-hs[i]-1){
			if(!seq[i]){puts("-1");exit(0);}
			ans+=1ll*seq[i]*(hs[i+1]-hs[i]-1);
		}
	}
	void build(int k,int l,int r){v[k]=r;if(l==r)return;int m=l+r>>1;build(lson),build(rson);}
	void insert(int k,int l,int r){
		if(l>=L&&r<=R){e[++cnt]=(edge){V,last[k]},last[k]=cnt;return;}
		int m=l+r>>1;if(L<=m)insert(lson);if(R>m)insert(rson);
	}
	#define max(a,b) ((a)>(b)?(a):(b))
	void push(int k,int l,int r){
		for(int&i=last[k];i;i=e[i].next)if(!vis[e[i].to])Q.push(P(que[e[i].to].v,e[i].to)),vis[e[i].to]=1;
		if(l==r){v[k]=0;return;}int m=l+r>>1;if(V<=m)push(lson);else push(rson);v[k]=max(v[k<<1],v[k<<1|1]);
	}
	int ask(int k,int l,int r){
		if(l>=L&&r<=R)return v[k];
		int m=l+r>>1,ans=0;if(L<=m)ans=ask(lson);if(R>m)Mn(ans,ask(rson));
		return ans;
	}
}A,B;
void clear(int k,int l,int r){v[k]=0;if(l==r)return;int m=l+r>>1;clear(lson),clear(rson);}
void cover(int k,int l,int r){
	if(l>=L&&r<=R){Mn(v[k],V);return;}
	int m=l+r>>1;
	if(L<=m)cover(lson);if(R>m)cover(rson);
}
void getseq(int k,int l,int r){
	if(l==r){seq[l]=v[k];return;}
	int m=l+r>>1;Mn(v[k<<1],v[k]),Mn(v[k<<1|1],v[k]),getseq(lson),getseq(rson);	
}
int main(){
	for(A.len=read(),B.len=read(),read(),n=read(),i=1;i<=n;++i)que[i].in(),A.hs[++A.n]=que[i].l1,A.hs[++A.n]=que[i].r1,B.hs[++B.n]=que[i].l2,B.hs[++B.n]=que[i].r2;
	for(A.pre(),B.pre(),clear(1,1,A.n),i=1;i<=n;++i){
		A.hash(que[i].l1,que[i].r1);
		if(que[i].l1<que[i].r1)L=que[i].l1,R=que[i].r1-1,V=que[i].v,cover(1,1,A.n);
	}
	for(getseq(1,1,A.n),A.check(),clear(1,1,B.n),i=1;i<=n;++i){
		B.hash(que[i].l2,que[i].r2);
		if(que[i].l2<que[i].r2)L=que[i].l2,R=que[i].r2-1,V=que[i].v,cover(1,1,B.n);
	}
	for(getseq(1,1,B.n),B.check(),A.build(1,1,A.n),B.build(1,1,B.n),i=1;i<=n;++i){
		A.L=que[i].l1,A.R=que[i].r1,A.V=i,A.insert(1,1,A.n);
		B.L=que[i].l2,B.R=que[i].r2,B.V=i,B.insert(1,1,B.n);
	}
	for(A.V=1,A.push(1,1,A.n);!Q.empty();){
		int k=Q.top().second;Q.pop(),A.L=que[k].l1,A.R=que[k].r1;
		if(c=A.ask(1,1,A.n)){ans+=que[k].v,A.V=c,A.push(1,1,A.n),Q.push(P(que[k].v,k));continue;}
		B.L=que[k].l2,B.R=que[k].r2;
		if(c=B.ask(1,1,B.n)){ans+=que[k].v,B.V=c,B.push(1,1,B.n),Q.push(P(que[k].v,k));continue;}
	}
	if(A.v[1]||B.v[1])return puts("-1"),0;
	else printf("%lld\n",ans);
}

bzoj3779 操作一和操作二怎么这么熟悉0 0，操作一不就是$access$操作吗，不就是统计到根路径上虚边条数$+1$吗，操作二不就是换根$+access$吗，操作三$Lct$似乎不支持维护子树，辣么我$dfs$序线段树随便维护一下不就行了吗_(:зゝ∠)_，$access$的时候也就是一段或两段$dfs$序加一或减一，$md$感觉好麻烦，数据结构应该要优美，这么能像这样要码农_(:зゝ∠)_，复杂度：$O(m\log^2 n)$，一遍过真是太爽了

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 100100
#define ll long long
int i,j,k,m,n,x,L,R,V,y,cnt,last[N],fa[N],dep[N],sz[N],in[N],out[N],now,son[N],rk[N],id[N],top[N],v[N];
struct edge{int to,next;}e[N<<1];char ch;
struct tree{int cov;ll s;}T[N<<2];
struct node{
	node*l,*r,*fa;bool f;
	inline void down(){
		if(fa->l==this||fa->r==this)fa->down();
		if(f)l->f^=1,r->f^=1,swap(l,r),f^=1;
	}
	inline void D(){if(f)l->f^=1,r->f^=1,swap(l,r),f^=1;}
}C[N],*c=C,Null,*null=&Null,*root=null;
inline void add(int u,int v){
	e[++cnt]=(edge){v,last[u]},last[u]=cnt;
	e[++cnt]=(edge){u,last[v]},last[v]=cnt;
}
void dfs1(int x,int d){
	dep[x]=d,sz[x]=1,v[x]=d+1;
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]){
		fa[y]=x,(c+y)->fa=(c+x),dfs1(y,d+1),sz[x]+=sz[y];
		if(sz[son[x]]<sz[y])son[x]=y;
	}
}
void dfs2(int x,int d){
	rk[id[x]=in[x]=++now]=x,top[x]=d;
	if(son[x])dfs2(son[x],d);
	for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]&&y!=son[x])dfs2(y,y);
	out[x]=now;
}
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define up(k) (T[k].s=T[k<<1].s+T[k<<1|1].s)
#define isroot(o) (o->fa->l==o||o->fa->r==o)
void build(int k,int l,int r){
	if(l==r){T[k].s=v[rk[l]];return;}
	int m=l+r>>1;build(lson),build(rson),up(k);
}
inline void zig(node *o){
	node *y=o->fa;y->l=o->r,o->r->fa=y,o->r=y,o->fa=y->fa;
	if(y==y->fa->l)y->fa->l=o;else if(y==y->fa->r)y->fa->r=o;
	y->fa=o;
}
inline void zag(node *o){
	node *y=o->fa;y->r=o->l,o->l->fa=y,o->l=y,o->fa=y->fa;
	if(y==y->fa->l)y->fa->l=o;else if(y==y->fa->r)y->fa->r=o;
	y->fa=o;
}
void splay(node*o){
	o->down();
	while(isroot(o)){
		node*y=o->fa,*z=y->fa;
		if(o==y->l){if(y==z->l)zig(y);zig(o);}
		else{if(y==z->r)zag(y);zag(o);}
	}
}
inline node*find(node*x){for(x->D();x->l!=null;x=x->l,x->D());return x;}
inline void down(int k,int l,int r){
	int m=l+r>>1;T[k<<1].cov+=T[k].cov,T[k<<1|1].cov+=T[k].cov;
	T[k<<1].s+=1ll*(m-l+1)*T[k].cov,T[k<<1|1].s+=1ll*(r-m)*T[k].cov,T[k].cov=0;
}
void add(int k,int l,int r){
	if(L>R)return;if(l>=L&&r<=R){T[k].s+=1ll*(r-l+1)*V,T[k].cov+=V;return;}
	if(T[k].cov)down(k,l,r);int m=l+r>>1;
	if(L<=m)add(lson);if(R>m)add(rson);up(k);
}
inline int Lca(int l,int r){
	int t=0;for(;top[l]!=top[r];t=top[l],l=fa[top[l]]);
	return l==r?t:son[r];
}
inline void modify(node*x,int v){
	if(root==x){L=1,R=n,V=v,add(1,1,n);return;}
	if(in[x-c]>in[root-c]||out[x-c]<out[root-c]){L=in[x-c],R=out[x-c],V=v,add(1,1,n);return;}
	int lca=Lca(root-c,x-c);L=1,R=in[lca]-1,V=v,add(1,1,n),L=out[lca]+1,R=n,V=v,add(1,1,n);
}
inline void access(node*x){
	node*y=null;
	while(x!=null){splay(x);if(x->r!=null)modify(find(x->r),1);if(y!=null)modify(find(y),-1);x->r=y,y=x,x=x->fa;}
}
inline void make_root(node*x){access(x),splay(x),x->f^=1,root=x;}
ll ask(int k,int l,int r){
	if(L>R)return 0;if(l>=L&&r<=R)return T[k].s;
	if(T[k].cov)down(k,l,r);int m=l+r>>1;ll ans=0;
	if(L<=m)ans+=ask(lson);if(R>m)ans+=ask(rson);return ans;
}
double query(node*x){
	if(root-c==x-c){L=1,R=n;return(double)ask(1,1,n)/n;}
	if(in[x-c]>in[root-c]||out[x-c]<out[root-c]){L=in[x-c],R=out[x-c];return(double)ask(1,1,n)/(out[x-c]-in[x-c]+1);}
	int t=Lca(root-c,x-c);double ans=0;
	L=1,R=in[t]-1,ans+=ask(1,1,n),L=out[t]+1,R=n,ans+=ask(1,1,n);
	return ans/(n-out[t]+in[t]-1);
}
int main(){
	for(n=read(),m=read(),i=1;i<n;++i)add(read(),read());
	for(i=1;i<=n;++i)(c+i)->l=(c+i)->r=(c+i)->fa=null;
	for(root=c+1,dfs1(1,0),dfs2(1,1),build(1,1,n);m--;){
		read(ch),read(ch),read(ch),x=read();
		if(ch=='L')access(c+x);
		else if(ch=='C')make_root(c+x);
		else printf("%.10lf\n",query(c+x));
	}
}

bzoj2888 很明显可以看出，最优的$ans$就是重心，也就是说现在动态加边，要维护每个联通块的重心与重心到每个点的$dis$，即可以用$LCT$维护以重心为根，每棵子树的$size$，以及所有点到该点的距离和，合并的时候暴力启发式合并，每次新加入叶子，该叶子到重心路径上的$size$都$+1$，$dis$的话那就是加一个等差数列，重心的话要移动肯定是移动到叶子路径的第一个点，于是暴力，$woc$细节真多，人真是越来越傻了，两发$wa$的原因居然是变量类型开错了，还在纠结为什么小数据拍不出呢_(:зゝ∠)_，复杂度：$O(n\log^2 n)$

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c!='A'&&c!='Q';c=nc());}
#define N 40040
#define isroot(o) (o->fa->l==o||o->fa->r==o)
int i,j,k,m,n,x,y,cnt,ans,last[N];char ch;
struct edge{int to,next;}e[N<<1];
struct node*null;
struct node{
	node*l,*r,*fa;bool rev;int flg,sz,s,k,sm,v;
	inline void sm_up(int S,int d){if(this==null)return;sm+=S+r->sz*d,s+=S,k+=d;}
	inline void down(){
		if(fa->l==this||fa->r==this)fa->down();
		if(rev)rev=0,l->rev^=1,r->rev^=1,swap(l,r);
		if(flg)l->v+=flg,l->flg+=flg,r->v+=flg,r->flg+=flg,flg=0;
		if(k)l->sm_up(s+(r->sz+1)*k,k),r->sm_up(s,k),s=k=0;
	}
	inline void sz_up(){sz=l->sz+r->sz+1;}
}C[N],*c=C,Null,*root;
inline void zig(node*o){
	node*y=o->fa;y->l=o->r,o->r->fa=y,o->r=y,o->fa=y->fa;
	if(y==y->fa->l)y->fa->l=o;
	else if(y==y->fa->r)y->fa->r=o;y->fa=o,y->sz_up();
}
inline void zag(node*o){
	node*y=o->fa;y->r=o->l,o->l->fa=y,o->l=y,o->fa=y->fa;
	if(y==y->fa->l)y->fa->l=o;
	else if(y==y->fa->r)y->fa->r=o;y->fa=o,y->sz_up();
}
inline void splay(node*o){
	for(o->down();isroot(o);){
		node*y=o->fa,*z=y->fa;
		if(o==y->l){if(y==z->l)zig(y);zig(o);}
		else{if(y==z->r)zag(y);zag(o);}
	}o->sz_up();
}
inline void access(node*x){node*y=null;while(x!=null)splay(x),x->r=y,x->sz_up(),y=x,x=x->fa;}
inline int find(int x){for(access(c+x),splay(c+x);(c+x)->l!=null;x=((c+x)->l)-c);return x;}
inline void Add(int f,int x){
	node*o=&C[x];o->fa=c+f,o->v=o->flg=o->sm=o->s=o->k=0,o->sz=1;
	o->l=o->r=null,f=find(f),access(o),splay(c+f),(c+f)->v+=1,(c+f)->flg+=1,(c+f)->sm_up(0,1);
	for(o=(c+f)->r;o->l!=null;o=o->l);splay(o);int v1=(c+f)->v,v2=o->v;
	if(v2<<1>v1){
		o->v=v1,(c+f)->v-=v2,(c+f)->sm-=o->sm+v2;
		o->sm+=(c+f)->sm+v1-v2,access(o),splay(c+f),(c+f)->l=o,(c+f)->r=null;
	}
}
void dfs(int x,int fa){Add(fa,x);for(int i=last[x];i;i=e[i].next)if(e[i].to!=fa)dfs(e[i].to,x);}
inline void insert(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
inline void add(int v,int u){
	int x=find(u),y=find(v);ans-=(c+x)->sm+(c+y)->sm;
	if((c+x)->v<(c+y)->v)swap(u,v);
	dfs(v,u),insert(u,v),insert(v,u),ans+=(c+find(u))->sm;
}
int main(){
	for(null=&Null,n=read(),i=1;i<=n;++i)(c+i)->v=(c+i)->sz=1,(c+i)->l=(c+i)->r=(c+i)->fa=null;
	for(m=read();m--;){
		read(ch);if(ch=='A')add(read(),read());
		else printf("%d\n",ans);
	}
}

bzoj3069 题意可以看成"询问$x$到$y$的路径上存不存在桥边"，删边的话考虑离线倒着加边，对于一条新加的边，如果本来不连通，那么这条边一定是桥边，否则显然就不是桥边，然后用$LCT$随意打标记即可，哦，你问我为什么$RE$辣么多发，呵呵我难道会和你说我预处理范围小了吗

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define N 200100
char bf[N],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,N,stdin),p2==p1)?-1:*p1++)
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}inline void read(char&c){for(c=nc();c!='Z'&&c!='P';c=nc());}
#define isroot(o) (o->fa->l==o||o->fa->r==o)
struct node*null;
struct ABC{int x,y;bool operator <(const ABC&b)const{return(x<b.x)||(x==b.x&&y<b.y);}}B[N];
int i,k,m,n,ans[N],j,x,y,fa[N],q;char ch,f[N];map<ABC,bool>mp;
struct node{
	node*l,*r,*fa;bool rev,flg,sm,v;
	inline void D(){if(this!=null)swap(l,r),rev^=1;}
	inline void _D(){if(this!=null)sm=v=0,flg=1;}
	inline void down(){
		if((fa!=null)&&(fa->l==this||fa->r==this))fa->down();
		if(rev)rev=0,l->D(),r->D();
		if(flg)l->_D(),r->_D(),flg=0;
	}
	inline void up(){sm=v|l->sm|r->sm;}
}Null,C[N],*c=C;
inline void zig(node*o){
	node*y=o->fa;y->l=o->r,o->r->fa=y,o->r=y,o->fa=y->fa;
	if(y==y->fa->l)y->fa->l=o;
	else if(y==y->fa->r)y->fa->r=o;y->fa=o,y->up();
}
inline void zag(node*o){
	node*y=o->fa;y->r=o->l,o->l->fa=y,o->l=y,o->fa=y->fa;
	if(y==y->fa->l)y->fa->l=o;
	else if(y==y->fa->r)y->fa->r=o;y->fa=o,y->up();
}
inline void splay(node*o){
	for(o->down();isroot(o);){
		node*y=o->fa,*z=y->fa;
		if(o==y->l){if(y==z->l)zig(y);zig(o);}
		else{if(y==z->r)zag(y);zag(o);}
	}o->up();
}
inline void access(node*o){for(node*y=null;o!=null;splay(o),o->r=y,o->up(),y=o,o=o->fa);}
inline void make_root(node*o){access(o),splay(o),o->D();}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void link(node*x,node*y){make_root(x),x->fa=y;}
inline void cover(int x,int y){
	int p=find(x),q=find(y);
	if(p!=q){fa[q]=p,++n,(c+n)->sm=(c+n)->v=1,link(c+x,c+n),link(c+n,c+y);return;}
	make_root(c+x),access(c+y),splay(c+x),(c+x)->_D();
}
inline int ask(int x,int y){int p=find(x),q=find(y);return p!=q?1:(make_root(c+x),access(c+y),splay(c+x),(c+x)->sm);}
int main(){
	for(n=read(),m=read(),q=read(),i=1;i<=n;++i)fa[i]=i;
	for(null=&Null,i=1;i<N;++i)(c+i)->l=(c+i)->r=(c+i)->fa=null;
	for(i=1;i<=m;++i){
		B[i].x=read(),B[i].y=read();
		if(B[i].x>B[i].y)swap(B[i].x,B[i].y);
	}
	for(i=1;i<=q;++i){
		read(f[i]),B[i+m].x=read(),B[i+m].y=read();
		if(B[i+m].x>B[i+m].y)swap(B[i+m].x,B[i+m].y);
		if(f[i]=='Z')mp[B[i+m]]=1;
	}
	for(i=1;i<=m;++i)if(!mp[B[i]]){
		int p=find(B[i].x),q=find(B[i].y);
		if(p!=q)fa[q]=p,++n,(c+n)->sm=(c+n)->v=1,link(c+B[i].x,c+n),link(c+n,c+B[i].y),mp[B[i]]=1;
	}
	for(i=1;i<=m;++i)if(!mp[B[i]])cover(B[i].x,B[i].y);
	for(i=q;i>=1;--i)if(f[i]=='Z')cover(B[i+m].x,B[i+m].y);else ans[i]=ask(B[i+m].x,B[i+m].y);
	for(i=1;i<=q;++i)if(f[i]!='Z')puts(ans[i]?"NIE":"TAK");
}

$*填坑总结$

1.诶感觉填完了更傻了

2.诶感觉填完了更傻了

3.诶感觉填完了更傻了

4.zbhydyazdpyjy_(:зゝ∠)_

loading...