此博客停更

这不是裸题吗？干嘛拿出来，太闲？

是是是，您教导的是

主要促使我写这题的动力是：怎么他们写的都是$splay$和$treap$？

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

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

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

现在做了多少：  10/10

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

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

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3545

sb题

离线做，把边和询问都排序，然后一条条加边，维护连通块，于是这就是个平衡树合并裸题。。然而只有我这种都比被卡了辣么久- =

一发5s，感觉跑好慢……，一看榜，发现rank3而且代码也很短2333

#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 100010
int i,j,k,m,n,x,y,Q,h[N],cnt,fa[N],pp[N],ans[N*5],top;
struct edge{
	int x,y,z;
	inline void in(){x=read(),y=read(),z=read();}
	bool operator <(const edge&a)const{return z<a.z;}	
}e[N*5];
struct ques{
	int v,x,k,id;
	inline void in(){v=read(),x=read(),k=read(),id=i;}
	bool operator <(const ques&a)const{return x<a.x;}
}q[N*5];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
struct node{
	node*ch[2];int r,sz,h,id;inline void up(){sz=ch[0]->sz+ch[1]->sz+1;}
	inline int cmp(int x)const{return x>h;}
}C[N],Null,*null=&Null;
inline void rotate(node*&o,int d){node*k=o->ch[d^1];o->ch[d^1]=k->ch[d],k->ch[d]=o,k->sz=o->sz,o->up(),o=k;}
int insert(node*&o,int x,int id){
	if(o==null)o=&C[id],o->id=id,o->h=x,o->ch[0]=o->ch[1]=null,o->sz=1,o->r=rand();
	else{
		int d=o->cmp(x);++o->sz;
		insert(o->ch[d],x,id);if(o->ch[d]->r>o->r)rotate(o,d^1);
	}
	return o->id;
}
void Add(node*x,node*y){if(x==null)return;Add(x->ch[0],y),Add(x->ch[1],y),top=insert(y=&(C[top]),x->h,x->id);}
inline void link(int u,int v){
	if(u==v)return;
	if((C+u)->sz<(C+v)->sz)swap(u,v);
	fa[v]=u,top=pp[u],Add(C+pp[v],C+pp[u]),pp[u]=top;
}
int kth(node*o,int k){
	if(o==null||k<=0||k>o->sz)return 0x7f7f7f7f;
	if(k<=o->ch[0]->sz)return kth(o->ch[0],k);
	if(k>o->ch[0]->sz+1)return kth(o->ch[1],k-o->ch[0]->sz-1);
	return o->h;
}
int main(){
	for(n=read(),m=read(),Q=read(),i=1;i<=n;++i)h[i]=read(),fa[i]=i,pp[i]=i,(C+i)->id=i,(C+i)->h=h[i],(C+i)->sz=1,(C+i)->ch[0]=(C+i)->ch[1]=null,(C+i)->r=rand();
	for(i=1;i<=m;++i)e[i].in();for(i=1;i<=Q;++i)q[i].in();
	for(cnt=1,sort(e+1,e+m+1),sort(q+1,q+Q+1),i=1;i<=Q;++i){
		while(e[cnt].z<=q[i].x&&cnt<=m)link(find(e[cnt].x),find(e[cnt].y)),++cnt;
		ans[q[i].id]=kth(C+pp[find(q[i].v)],(C+pp[find(q[i].v)])->sz-q[i].k+1);
	}
	for(i=1;i<=Q;++i)if(ans[i]==0x7f7f7f7f)puts("-1");else printf("%d\n",ans[i]);
}

-->http://qiancl.is-programmer.com/user_files/qiancl/Image/Problem%203072.%20--%20[Pa2012]Two%20Cakes.html

……第一眼挺简单-。-

……第二眼不会-。-|||

……考虑DP$f[i][j]$表示 $a$串取了$i$次，$b$串取了$j$次，于是

$f[i-1][j] -> f[i][j]$

$f[i][j-1] -> f[i][j]$

$f[i-1][j-1] -> f[i][j] (a[i]!=b[j])$

#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 1000100
int i,j,k,m,n,x,y,a[N],b[N],rk[N],f[5005][5005],g[N];
int main(){
    for(n=read(),i=1;i<=n;++i)a[i]=read(),rk[a[i]]=i;
    for(i=1;i<=n;++i)b[i]=read();
    memset(f,0x3f,sizeof f);
    f[0][0]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j){
            f[i][j]=min(f[i][j],f[i-1][j]+1);
            f[i][j]=min(f[i][j],f[i][j-1]+1);
            if(a[i]!=b[j])f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    printf("%d\n",f[n][n]);
}