我的模板

树套树

#include<algorithm>
#include<cstdio>
#define W while
#define I inline
#define LL long long
#define gc getchar
#define ig(c) ('0'<=(c)&&(c)<='9')
#define pc(c) putchar((c))
I int read(){int x=0,f=1;char c=gc();W(!ig(c)) f=c=='-'?-1:f,c=gc();W(ig(c)) x=(x<<3)+(x<<1)+(c&15),c=gc();return x*f;}
I void write(int x){x<0&&(pc('-'),0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
const int N=50010;
int n,m,rt[N],a[N],cnt,lsh[N<<1],tot,op[N],l[N],r[N],k[N];
struct node{int ls,rs,sum;}tr[N*200+5];
I int lowbit(int x){return x&(-x);}
I void update(int &x,int l,int r,int pos,int v){
	if(!x) x=++cnt;
	if(l==r) return void(tr[x].sum+=v);
	int mid=l+r>>1;
	if(pos<=mid) update(tr[x].ls,l,mid,pos,v);
	else update(tr[x].rs,mid+1,r,pos,v);
	tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum;
}
I void Upd(int i,int pos,int v){W(i<=n) update(rt[i],0,tot,pos,v),i+=lowbit(i);}
I int query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return tr[x].sum;
	int mid=l+r>>1,res=0;
	if(L<=mid) res+=query(tr[x].ls,l,mid,L,R);
	if(R>mid) res+=query(tr[x].rs,mid+1,r,L,R);
	return res;
}
I int Getsum(int i,int x){int s=0;W(i>0) s+=query(rt[i],0,tot,0,x),i-=lowbit(i);return s;}
I int kth(int l,int r,int k){int L=0,R=tot,mid,s;W(L<=R) mid=L+R>>1,Getsum(r,mid)-Getsum(l-1,mid)>=k?(s=mid,R=mid-1,0):(L=mid+1,0);return s;}
I int Get(int x){return std::lower_bound(lsh+1,lsh+tot+1,x)-lsh;}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read(),lsh[++tot]=a[i];
	for(int i=1;i<=m;i++) op[i]=read(),l[i]=read(),r[i]=read(),op[i]==3?(lsh[++tot]=r[i],0):(k[i]=read(),op[i]!=2&&(lsh[++tot]=k[i],0),0);
	std::sort(lsh+1,lsh+tot+1);
	tot=std::unique(lsh+1,lsh+tot+1)-lsh-1;
	for(int i=1;i<=n;i++) a[i]=Get(a[i]),Upd(i,a[i],1);
	for(int i=1;i<=m;i++) switch(op[i]){
		case 1:k[i]=Get(k[i]),write(Getsum(r[i],k[i]-1)-Getsum(l[i]-1,k[i]-1)+1),pc('\n');break;
		case 2:write(lsh[kth(l[i],r[i],k[i])]),pc('\n');break;
		case 3:Upd(l[i],a[l[i]],-1),Upd(l[i],a[l[i]]=r[i]=Get(r[i]),1);break;
		case 4:k[i]=Get(k[i]),write(lsh[kth(l[i],r[i],Getsum(r[i],k[i]-1)-Getsum(l[i]-1,k[i]-1))]),pc('\n');break;
		case 5:k[i]=Get(k[i]),write(lsh[kth(l[i],r[i],Getsum(r[i],k[i])-Getsum(l[i]-1,k[i])+1)]),pc('\n');break;
	}
	return 0;
}

Link Cut Tree

#include<cstdio>
#define N 200010
#define min(x,y) ((x)>(y)?(y):(x))
#define ls tr[x].ch[0]
#define rs tr[x].ch[1]
int n,m,a[N];
struct node{int fa,ch[2],v,s,tag;}tr[N];
inline int get(int x){return (tr[tr[x].fa].ch[0]==x?0:(tr[tr[x].fa].ch[1]==x?1:-1));}
inline void add(int x,int y,int k){tr[x].fa=y,(~k&&(tr[y].ch[k]=x,0));}
inline void pushup(int x){tr[x].s=tr[ls].s^tr[rs].s^tr[x].v;}
inline void pushdown(int x){if(!tr[x].tag) return ;ls^=rs^=ls^=rs;tr[ls].tag^=1,tr[rs].tag^=1,tr[x].tag=0;}
inline void pushall(int x){if(~get(x)) pushall(tr[x].fa);pushdown(x);}
inline void rotate(int x){int y=tr[x].fa,z=tr[y].fa,kx=get(x),ky=get(y);add(tr[x].ch[kx^1],y,kx),add(y,x,kx^1),add(x,z,ky),pushup(y),pushup(x);}
inline void splay(int x){pushall(x);while(~get(x)){if(~get(tr[x].fa)) rotate(get(x)^get(tr[x].fa)?x:tr[x].fa);rotate(x);}}
inline void access(int x){for(int y=0;x;x=tr[y=x].fa) splay(x),rs=y,pushup(x);}
inline void makeroot(int x){access(x),splay(x),tr[x].tag^=1,pushdown(x);}
inline void split(int x,int y){makeroot(x),access(y),splay(y);}
inline int findroot(int x){access(x),splay(x);while(ls) pushdown(x),x=ls;splay(x);return x;}
inline void link(int x,int y){makeroot(x);if(findroot(y)^x) tr[x].fa=y;}
inline void cut(int x,int y){if(findroot(x)^findroot(y)) return ;split(x,y);if(tr[x].fa!=y||rs) return ;tr[x].fa=tr[y].ch[0]=0,pushup(x);}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),tr[i].v=a[i];
	for(int op,x,y,i=1;i<=m;i++){
		scanf("%d%d%d",&op,&x,&y);
		if(op==0) split(x,y),printf("%d\n",tr[y].s);
		else if(op==1) link(x,y);
		else if(op==2) cut(x,y);
		else if(op==3) splay(x),tr[x].v=y;
	}
}

Big Integer

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Int{
	#define BASE 1000000000
	public:
	typedef long long value;
	void New(size_t l){
		if (a!=NULL)delete[] a;a=new value[l];
		len=1;a[0]=0;sign=1;
	}
	Int():a(NULL),base(BASE){New(1);}
	Int(value x):a(NULL),base(BASE){New(1);*this=x;}
	Int(value x,value _base):a(NULL),base(_base){New(1);*this=x;}
	Int(const Int &B):a(NULL),base(BASE){New(1);*this=B;}
	~Int(){delete[] a;}
	Int& operator =(value x){
		size_t l=1;for (value x1=max(x,-x);x1>=base;++l,x1/=base);New(l);
		if (x<0)x=-x,sign=0;else sign=1;
		len=0;while (x)a[len++]=x%base,x/=base;
		if (!len)a[len++]=0;
		return *this;
	}
	Int& operator =(const Int &A){
		New(A.len);len=A.len;memcpy(a,A.a,sizeof(value)*len);
		base=A.base;sign=A.sign;return *this;
	}
	friend Int operator -(Int A){A.sign=1-A.sign;return A;}
	bool operator !(){if (len==1&&a[0]==0)return 1;else return 0;}
	friend Int operator +(Int A,Int B){
		if (A.sign!=B.sign){B.sign=1-B.sign;return A-B;}
		if (A.base!=B.base)
			if (A.base>B.base)B.set_base(A.base);
			else A.set_base(B.base);
		Int res;res.set_base(A.base); int len=A.len>B.len?A.len:B.len;
		res.New(len+1);res.sign=A.sign;
		memset(res.a,0,(len+1)*sizeof(value));
		for (int i=0;i<len;++i){
			if (i<A.len)res.a[i]+=A.a[i];
			if (i<B.len)res.a[i]+=B.a[i];
		}
		for (int i=0;i<len;++i)
			if (res.a[i]>=res.base)++res.a[i+1],res.a[i]-=res.base;
		if (res.a[len])res.len=len+1;else res.len=len;
		if (!res)res.sign=1;return res;
	}
	friend Int operator -(Int A,Int B){
		if (A.sign!=B.sign){B.sign=1-B.sign;return A+B;}
		if (A.base!=B.base)
			if (A.base>B.base)B.set_base(A.base);
			else A.set_base(B.base);
		if (small(A,B))swap(A,B),A.sign=1-A.sign;
		Int res;res.set_base(A.base); int len=A.len>B.len?A.len:B.len;
		res.New(len);res.sign=A.sign;
		memset(res.a,0,len*sizeof(value));
		for (int i=0;i<len;++i){
			if (i>=B.len)res.a[i]+=A.a[i];
			else res.a[i]+=A.a[i]-B.a[i];
			if (res.a[i]<0)res.a[i]+=res.base,--res.a[i+1];
		}
		while (len>1&&!res.a[len-1])--len;res.len=len;
		if (!res)res.sign=1;return res;
	}
	friend Int operator *(Int A,Int B){
		if (A.base!=B.base)
			if (A.base>B.base)B.set_base(A.base);
			else A.set_base(B.base);
		Int res;res.set_base(A.base); int len=A.len+B.len;
		res.New(len);res.sign=(A.sign==B.sign);
		memset(res.a,0,len*sizeof(value));
		for (int i=0;i<A.len;++i)
			for (int j=0;j<B.len;++j){
				res.a[i+j]+=A.a[i]*B.a[j];
				res.a[i+j+1]+=res.a[i+j]/res.base;
				res.a[i+j]%=res.base;
			}
		/*
		for (int i=0;i<A.len;++i)
			for (int j=0;j<B.len;++j)res.a[i+j]+=A.a[i]*B.a[j];
		for (int i=0;i<len-1;++i)res.a[i+1]+=res.a[i]/res.base,res.a[i]%=res.base;
		*/
		while (len>1&&!res.a[len-1])--len;res.len=len;
		return res;
	}
	friend pair<Int,Int> divide(Int A,Int B){
		if (!B){puts("error:div zero!");for (;;);}
		if (A.base!=B.base)
			if (A.base>B.base)B.set_base(A.base);
			else A.set_base(B.base);
		if (small(A,B))return make_pair(Int(0),A);
		Int C,D;C.set_base(A.base);D.set_base(A.base);C.New(A.len);C.len=A.len;
		bool Csign=(A.sign==B.sign),Dsign=A.sign;A.sign=B.sign=1;
		for (int i=A.len-1;i>=0;--i){
			C.a[i]=0;D=D*D.base;D.a[0]=A.a[i];
			int l=0,r=A.base-1,mid;
			while (l<r){
				mid=(l+r+1)>>1;
				if (small(B*mid,D+1))l=mid;
					else r=mid-1;
			}
			C.a[i]=l;D=D-B*l;
		}
		C.sign=Csign;D.sign=Dsign;if (!D)D.sign=1;
		while (C.len>1&&!C.a[C.len-1])--C.len;
		return make_pair(C,D);
	}
	Int operator /(value x){
		if (!x){puts("error:div zero!");for (;;);}
		value d=0;Int res;res.set_base(base);res.New(len);res.len=len;
		if (x<0)x=-x,res.sign=(sign==0);
		else res.sign=(sign==1);
		for (int i=len-1;i>=0;--i)
			d=d*base+a[i],res.a[i]=d/x,d%=x;
		while (res.len>1&&!res.a[res.len-1])--res.len;
		return res;
	}
	Int operator %(value x){
		value d=0;if (x<0)x=-x;
		for (int i=len-1;i>=0;--i)d=(d*base+a[i])%x;
		return d;
	}
	friend Int abs(Int A){A.sign=1;return A;}
	friend bool small(Int A,Int B){
		if (A.base!=B.base)
			if (A.base>B.base)B.set_base(A.base);
			else A.set_base(B.base);
		if (A.len!=B.len)return A.len<B.len;
		for (int i=A.len-1;i>=0;--i)
			if (A.a[i]!=B.a[i])return A.a[i]<B.a[i];
		return 0;
	}
	friend bool operator <(Int A,Int B){
		if (A.sign!=B.sign)return A.sign<B.sign;
		return A.sign==1?small(A,B):small(B,A);
	}
	friend bool operator ==(Int A,Int B){
		if (A.base!=B.base)
			if (A.base>B.base)B.set_base(A.base);
			else A.set_base(B.base);
		if (A.sign!=B.sign||A.len!=B.len)return 0;
		for (int i=0;i<A.len;++i)if (A.a[i]!=B.a[i])return 0;
		return 1;
	}
	friend bool operator !=(Int A,Int B){return !(A==B);}
	friend bool operator >(Int A,Int B){return !(A<B||A==B);}
	friend bool operator <=(Int A,Int B){return A<B||A==B;}
	friend bool operator >=(Int A,Int B){return A>B||A==B;}
	Int operator /(Int B){return divide(*this,B).first;}
	Int operator %(Int B){return divide(*this,B).second;}
	Int& operator +=(Int B){*this=*this+B;return *this;}
	Int& operator -=(Int B){*this=*this-B;return *this;}
	Int& operator *=(Int B){*this=*this*B;return *this;}
	Int& operator /=(Int B){*this=*this/B;return *this;}
	Int& operator %=(Int B){*this=*this%B;return *this;}
	Int& operator ++(){*this=*this+1;return *this;}
	Int& operator --(){*this=*this-1;return *this;}
	Int operator ++(int){Int res(*this);*this=*this+1;return res;}
	Int operator --(int){Int res(*this);*this=*this-1;return res;}
	Int operator +(value x){return *this+Int(x,this->base);}
	Int operator -(value x){return *this-Int(x,this->base);}
	Int operator *(value x){return *this*Int(x,this->base);}
	//Int operator /(value x){Int T;T=x;return *this/T;}
	//Int operator %(value x){Int T;T=x;return *this%T;}
	Int& operator *=(value x){*this=*this*x;return *this;}
	Int& operator +=(value x){*this=*this+x;return *this;}
	Int& operator -=(value x){*this=*this-x;return *this;}
	Int& operator /=(value x){*this=*this/x;return *this;}
	Int& operator %=(value x){*this=*this%x;return *this;}
	bool operator ==(value x){return *this==Int(x,this->base);}
	bool operator !=(value x){return *this!=Int(x,this->base);}
	bool operator <=(value x){return *this<=Int(x,this->base);}
	bool operator >=(value x){return *this>=Int(x,this->base);}
	bool operator <(value x){return *this<Int(x,this->base);}
	bool operator >(value x){return *this>Int(x,this->base);}
	friend Int gcd(Int x,Int y){
		Int t;int cnt=0;
		while (1){
			if (x<y)t=x,x=y,y=t;
			if (y==0){
				while (cnt--)x*=2;
				return x;
			}
			if (x%2==0&&y%2==0)x/=2,y/=2,++cnt;
			else if (x%2==0)x/=2;
			else if (y%2==0)y/=2;
			else {t=x;x=y;y=t-y;}
		}
	}
	void to_arr(char *c){
		char *c1=c;
		for (int i=0;i<len-1;++i)
			for (value x=a[i],b=base/10;b>=1;b/=10)*c1++='0'+x%10,x/=10;
		for (value x=a[len-1];x>0;x/=10)*c1++='0'+x%10;
		if (len==1&&a[len]==0)*c1++='0';
		if (sign==0)*c1++='-';*c1=0;reverse(c,c1);
	}
	void from_arr(char *c){
		size_t base_l=get_basel(),b=1;int cl=strlen(c);value x=0;
		New((cl+base_l-1)/base_l);len=0;
		if (*c=='-')sign=0,++c,--cl;else sign=1;
		while (--cl>=0){
			x+=(c[cl]-'0')*b;b*=10;if (b==base)a[len++]=x,x=0,b=1;
		}
		if (!len||x)a[len++]=x;
		while (len>1&&!a[len-1])--len;
	}
	void set_base(int _base){
		if (base==_base)return;
		char *c=new char[len*get_basel()+1];
		to_arr(c);base=_base;from_arr(c);
		delete[] c;
	}
	void set_basel(int _l){
		size_t _base=1;while (_l--)_base*=10;set_base(_base);
	}
	void read(){
		vector<char> s;char ch;
		scanf(" %c",&ch);if (ch=='-')s.push_back('-'),ch=getchar();
		for (;ch>='0'&&ch<='9';ch=getchar())s.push_back(ch);
		char *c=new char[s.size()+1];
		for (int i=0;i<s.size();++i)c[i]=s[i];c[s.size()]=0;
		from_arr(c);delete[] c;
		if (!*this)this->sign=1;
	}
	void print(){
		if (!sign)putchar('-');
		printf("%d",int(a[len-1]));
		for (int i=len-2;i>=0;--i){
			for (int j=base/10;j>=10;j/=10)
				if (a[i]<j)putchar('0');
					else break;
			printf("%d",(int)a[i]);
		}
	}
	void println(){print();putchar('\n');}
	private:
	value *a,base;int len;bool sign;  //0="-"
	size_t get_basel()const{
		size_t res=0;for (int b=base/10;b>=1;b/=10,++res);
		return res;
	}
	#undef BASE
};
Int a,b,c;
int main()
{
	int t1=clock();
	a.read();b.read();(a*b/gcd(a,b)).println();
	return 0;
}