此博客停更

有人问我为什么有些题那么快_(:зゝ∠)_

所以我来解释一下我加的黑科技，题目编号是乱的= =，有想要我解释的题请评论

首先是fastio，bzoj上有了这个就可以轻易rank1吧。。

#define S 100000
char bf[S],*p1=bf,*p2=bf;
#define nc() (p1==p2&&(p2=(p1=bf)+fread(bf,1,S,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;
}
char pf[S],*o1=pf,*o2=pf+S;
#define ot(x) (o1==o2?fwrite(pf,1,S,stdout),*(o1=pf)++=x:*o1++=x)
inline void print(int x){static char s[15],*b;b=s;if(!x)*b++=48;for(;x;*b++=x%10+48,x/=10);for(;b--!=s;ot(*b));}
fwrite(pf,1,o1-pf,stdout);
//for(i=1;i<=m;++i)print(ans[i]),ot('\n');

所以在这里我就不解释用fastio艹上去的题了

bzoj4345

题解在这-->http://qiancl.is-programmer.com/posts/191596.html

我会说黑科技是因为用了splay吗

bzoj4373（已被艹）

题解在这-->http://qiancl.is-programmer.com/posts/192245.html

这题是使过的

bzoj4260

题解在这-->http://qiancl.is-programmer.com/posts/183365.html

这题字母树自带30常数，然后我发现把长度改小也能过，于是嘿嘿嘿

bzoj4278

这题啊。。接下去的几个人都是900+ms了

我的做法是贪心，可以简单的插掉。。做法我想不起来了具体就看代码吧= =

#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;
}
#define N 200020
int n,m,i,j,l,r,L,R,a[N],b[N];
int main(){
	for(n=read(),i=1;i<=n;++i)a[i]=read();
	for(m=read(),i=1;i<=m;++i)b[i]=read();
	l=r=1;a[n+1]=0x7f7f7f7f;b[m+1]=0x7f7f7f7f;
	while(l<=n||r<=m){
		if(a[l]<b[r]){
			if(L){for(i=l-L,r-=R;i<l&&b[r]>=a[i];++i)printf("%d ",a[i]);l=i,L=R=0;}
			else printf("%d ",a[l++]);
		}else if(a[l]==b[r])++L,++l,++r,++R;
		else if(a[l]>b[r]){
			if(L){for(i=r-R,l-=L;i<r&&a[l]>=b[i];++i)printf("%d ",b[i]);r=i,L=R=0;}
			else printf("%d ",b[r++]);
		}
	}
	for(i=n-L+1;i<=n;++i)printf("%d ",a[i]);
	for(i=m-R+1;i<=m;++i)printf("%d ",b[i]);
}

bzoj4281（已被艹）

这题只是求一下LCA，= =LCA怎么求呢。。树剖啊，树剖的log很神奇~，我上面那个估计也应该写的树剖吧。。不过代码长度好鬼畜

bzoj3784

刚开始我还想着用st表来O(1)查询把速度提上去，然后发现跑的真tm慢，还不如人家线段树，既然线段树辣么快，那我写棵zkw好了，没想到效果辣么好

#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,M,cnt,last[N],root,allsz,sz[N],f[N],L,R,ed,can[N<<1],q[N*15],anscnt,mx[N*15*4];
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;}
priority_queue<node>Q;
inline void build(int n){
	for(M=1;M<=n+1;M<<=1);
	for(int i=M+1;i<=M+n;++i)mx[i]=i-M;
	for(int i=M-1;i>0;--i)mx[i]=max(mx[i<<1],mx[i<<1|1]);
}
inline int ask(int l,int r){
	int ans=ed+1;
	for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ans=max(ans,mx[l^1]);
		if(r&1)ans=max(ans,mx[r^1]);
	}return ans;
}
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),q[ed+1]=-0x7f7f7f7f,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);
	}
}

updating...