首页 > 其他分享 >一些板子

一些板子

时间:2024-09-08 16:38:39浏览次数:3  
标签:va ch return int 板子 ans 一些 root

平衡树系列

splay

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int siz[N],cnt[N],tot,fa[N],ch[N][2],val[N],root,n;
inline int read(){
	register int ans=0;register char ch=getchar();register bool flag=0;
	while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar();}
	while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return flag?(~ans+1):ans;
}
void print(register int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+'0');
}
void update(int x){
	siz[x]=cnt[x]+siz[ch[x][0]]+siz[ch[x][1]];
}
void rotate(int x){
	int y=fa[x],z=fa[y];
	int k=ch[y][1]==x;
	ch[z][ch[z][1]==y]=x;
	fa[x]=z;
	ch[y][k]=ch[x][k^1];
	fa[ch[x][k^1]]=y;
	ch[x][k^1]=y;
	fa[y]=x;
	update(y);update(x);
}
void splay(int x,int s){
	while(fa[x]!=s){
		int y=fa[x],z=fa[y];
		if(z^s){
			(ch[z][1]==y)^(ch[y][1]==x)?rotate(x):rotate(y);
		}rotate(x);
	}
	if(!s)root=x;
}
void find(int x){
	int u=root;
	if(!u)return;
	while(ch[u][x>val[u]]&&x!=val[u])
		u=ch[u][x>val[u]];
	splay(u,0);
}
void insert(int x){
	int u=root,y=0;
	while(u&&val[u]!=x){
		y=u;
		u=ch[u][x>val[u]];
	}
	if(u)cnt[u]++;
	else{
		u=++tot;
		if(y)ch[y][x>val[y]]=u;
		ch[u][0]=ch[u][1]=0;
		fa[tot]=y;val[tot]=x;
		siz[tot]=cnt[tot]=1;
	}
	splay(u,0);
}
int lower(int x){
	//返回前驱的编号
	find(x);
	int u=root;
	if(val[u]<x)return u;
	u=ch[u][0];
	while(ch[u][1])u=ch[u][1];
	return u;
}
int upper(int x){
	//返回后继的编号
	find(x);
	int u=root;
	if(val[u]>x)return u;
	u=ch[u][1];
	while(ch[u][0])u=ch[u][0];
	return u;
}
void del(int x){
	//删除键值为x的点
	int last=lower(x),nxt=upper(x);
	splay(last,0);splay(nxt,last);
	int d=ch[nxt][0];
	if(cnt[d]>1){
		cnt[d]--;
		splay(d,0);
	}else ch[nxt][0]=0;
}
int get_kth(int k){
	int u=root;
	if(siz[u]<k)return 0;
	while(1){
		int y=ch[u][0];
		if(k>siz[y]+cnt[u]){
			k-=siz[y]+cnt[u];
			u=ch[u][1];
		}else if(k<=siz[y])u=y;
		else return val[u];
	}
}
int main(){
	n=read();
	insert(INT_MAX);
	insert(INT_MIN);
	while(n--){
		int op=read(),x=read();
		switch(op){
			case 1:{insert(x);break;}
			case 2:{del(x);break;}			
			case 3:{find(x),print(siz[ch[root][0]]+(x>val[root])),puts("");break;}			
			case 4:{print(get_kth(x+1)),putchar('\n');break;}
			case 5:{print(val[lower(x)]),putchar('\n');break;}
			case 6:{print(val[upper(x)]),putchar('\n');break;}
		}
	} 
	return 0;
}

无旋Treap

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int rd[N],ch[N][2],siz[N],val[N],n,root,tot;
inline int read(){
	register int ans=0;register char ch=getchar_unlocked();register bool flag=0;
	while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar_unlocked();}
	while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar_unlocked();
	return flag?(~ans+1):ans;
}
void print(register int x){
	if(x<0)putchar_unlocked('-'),x=-x;
	if(x>9)print(x/10);
	putchar_unlocked(x%10+'0');
}
void update(int x){
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
}
int newpoint(int va){
	val[++tot]=va;rd[tot]=rand();
	siz[tot]=1;
	return tot;
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(rd[x]<rd[y])return ch[x][1]=merge(ch[x][1],y),update(x),x;
	return ch[y][0]=merge(x,ch[y][0]),update(y),y;
}
void va_split(int x,int va,int &a,int &b){
	if(!x){
		a=b=0;
		return;
	}
	if(val[x]<=va)a=x,va_split(ch[x][1],va,ch[x][1],b);
	else b=x,va_split(ch[x][0],va,a,ch[x][0]);
	update(x);
}
int get_kth(int x,int k){
	while(1){
		if(k<=siz[ch[x][0]])x=ch[x][0];
		else if(k>siz[ch[x][0]]+1)k-=siz[ch[x][0]]+1,x=ch[x][1];
		else return val[x];
	}
}
void insert(int va){
	int x,y;
	va_split(root,va,x,y);
	root=merge(merge(x,newpoint(va)),y);
}
void del(int va){
	int x,y,z;
	va_split(root,va,x,y);
	va_split(x,va-1,x,z);
	z=merge(ch[z][0],ch[z][1]);
	root=merge(merge(x,z),y);
}
int get_rank(int va){
	int x,y,ans;
	va_split(root,va-1,x,y),ans=siz[x]+1;
	return root=merge(x,y),ans;
}
int lower(int va){
	int x,y,ans;
	va_split(root,va-1,x,y),ans=get_kth(x,siz[x]);
	return root=merge(x,y),ans;
}
int upper(int va){
	int x,y,ans;
	va_split(root,va,x,y),ans=get_kth(y,1);
	return root=merge(x,y),ans;
}
int main(){
	n=read();
	while(n--){
		int op=read(),x=read();
		switch(op){
			case 1:{insert(x);break;}
			case 2:{del(x);break;}
			case 3:{print(get_rank(x)),putchar_unlocked('\n');break;}
			case 4:{print(get_kth(root,x)),putchar_unlocked('\n');break;}
			case 5:{print(lower(x)),putchar_unlocked('\n');break;}
			case 6:{print(upper(x)),putchar_unlocked('\n');break;}
		}
	}
}

树链剖分

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ld (x<<1)
#define rd (x<<1|1)
const int N=3e4+10;
inline int read(){
    int ans=0;char ch=getchar();bool flag=0;
    while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar();}
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return flag?~ans+1:ans;
}
void print(register int x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10|48);}
struct stu{
    int l,r,m,sum;
}s[N<<2];
int top[N],fa[N],son[N],siz[N],to[N<<1],nt[N<<1],tot,h[N],w[N];
int n,m,rnk[N],dfn[N],dfntot,dep[N];
void push_up(int x){
    s[x].m=max(s[ld].m,s[rd].m);
    s[x].sum=s[ld].sum+s[rd].sum;
}
void build(int x,int l,int r){
    s[x].l=l,s[x].r=r;
    if(l==r){
        s[x].m=s[x].sum=w[rnk[l]];
        return;
    }
    int mid=l+r>>1;
    build(ld,l,mid);
    build(rd,mid+1,r);
    push_up(x);
}
int query(int x,int l,int r){
    if(l<=s[x].l&&s[x].r<=r)return s[x].sum;
    int ans=0,mid=s[x].l+s[x].r>>1;
    if(l<=mid)ans+=query(ld,l,r);
    if(r>mid)ans+=query(rd,l,r);
    return ans;
}
int query_x(int x,int y){
    int ans=0;
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=query(1,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans+=query(1,dfn[x],dfn[y]);
    return ans;
}
int get_max(int x,int l,int r){
    if(l<=s[x].l&&s[x].r<=r)return s[x].m;
    int ans=INT_MIN,mid=s[x].l+s[x].r>>1;
    if(l<=mid)ans=max(ans,get_max(ld,l,r));
    if(r>mid)ans=max(ans,get_max(rd,l,r));
    return ans;
}
int get_max_x(int x,int y){
    int ans=INT_MIN;
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=max(ans,get_max(1,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=max(ans,get_max(1,dfn[x],dfn[y]));
    return ans;
}
void change(int x,int pos,int val){
    if(s[x].l==s[x].r){
        s[x].m=s[x].sum=val;
        return;
    }
    int mid=s[x].l+s[x].r>>1;
    if(pos<=mid)change(ld,pos,val);
    else change(rd,pos,val);
    push_up(x);
}
void add(int x,int y){
    to[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
}
void dfs1(int x){
    siz[x]=1;
    for(int i=h[x];i;i=nt[i]){
        int y=to[i];
        if(!dep[y]){
            fa[y]=x;
            dep[y]=dep[x]+1;
            dfs1(y);
            siz[x]+=siz[y];
            if(siz[son[x]]<siz[y])son[x]=y;
        }
    }
}
void dfs2(int x,int t){
    dfn[x]=++dfntot;
    rnk[dfntot]=x;
    top[x]=t;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i=h[x];i;i=nt[i]){
        int y=to[i];
        if((fa[x]^y)&&(son[x]^y))dfs2(y,y);
    }
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++)w[i]=read();
    dep[1]=1;dfs1(1);dfs2(1,1);
    build(1,1,n);
    m=read();
    while(m--){
        string s;cin>>s;
        int x=read(),y=read();
        if(s[0]=='Q'){
            if(s[1]=='M')print(get_max_x(x,y)),putchar('\n');
            else print(query_x(x,y)),putchar('\n');
        }
        else change(1,dfn[x],y);
    }
    return 0;
}

主席树

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int sum[N<<5],ld[N<<5],rd[N<<5],tot,n,m;
int a[N],b[N],len,rt[N<<5];
inline int read(){
    int ans=0;bool flag=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar();}
    while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return flag?~ans+1:ans;
}
void build(int &x,int l,int r){
    x=++tot;
    if(l==r)return;
    int mid=l+r>>1;
    build(ld[x],l,mid);
    build(rd[x],mid+1,r);
}
int update(int x,int l,int r,int pos){
    int op=++tot;
    ld[op]=ld[x],rd[op]=rd[x];
    sum[op]=sum[x]+1;
    if(l==r)return op;
    int mid=l+r>>1;
    if(pos<=mid)ld[op]=update(ld[x],l,mid,pos);
    else rd[op]=update(rd[x],mid+1,r,pos);
    return op;
}
int query(int x,int y,int l,int r,int k){
    if(l==r)return l;
    int mid=l+r>>1,pos=sum[ld[y]]-sum[ld[x]];
    if(k<=pos)return query(ld[x],ld[y],l,mid,k);
    else return query(rd[x],rd[y],mid+1,r,k-pos);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)b[i]=a[i]=read();
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    build(rt[0],1,len);
    for(int i=1;i<=n;i++)rt[i]=update(rt[i-1],1,len,lower_bound(b+1,b+1+len,a[i])-b);
    while(m--){
        int l=read(),r=read(),k=read();
        printf("%d\n",b[query(rt[l-1],rt[r],1,len,k)]);
    }
}

Tarjan

求强连通分量
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,dfn[N],low[N],to[N],nt[N],tot,h[N],cnt;
int t,siz[N];bool vis[N];
stack<int>q;
void add(int x,int y){
    to[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    vis[x]=1;q.push(x);
    for(int i=h[x];i;i=nt[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(vis[x])low[x]=min(dfn[y],low[x]);
    }
    if(low[x]==dfn[x]){
        t++;int y;
        do{
            y=q.top();
            q.pop();
            vis[y]=0;
            siz[t]++;
        }while(x^y);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        add(i,x);
    }tot=INT_MAX;
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=t;i++)tot=min(tot,siz[i]==1?INT_MAX:siz[i]);
    printf("%d",tot);
}
求割点
#include<bits/stdc++.h>
using namespace std;
const int N=150;
int dfn[N],to[N<<1],nt[N<<1],h[N],tot;
int low[N],cut[N],n,m,cnt,root;
void add(int x,int y){
    to[++tot]=y;
    nt[tot]=h[x];
    h[x]=tot;
}
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    int son=0;
    for(int i=h[x];i;i=nt[i]){
        int y=to[i];
        if(!dfn[y]){
            son++;
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<=low[y])
                if(x!=root||son>1)cut[x]=1;
        }else low[x]=min(low[x],dfn[y]);
    }
}
int main(){
    scanf("%d",&n);
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF){
        add(x,y);add(y,x);
    }       
    for(int i=1;i<=n;i++){
        root=i;
        fill(dfn+1,dfn+1+n,0);
        fill(low+1,low+1+n,0);
        tarjan(i);
    }root=0;
    for(int i=1;i<=n;i++)root+=cut[i];
    printf("%d\n",root);
    for(int i=1;i<=n;i++)
        (cut[i])&&(printf("%d\n",i));
    return 0;
}

高斯消元

慢一点,但是可以判断无解、无数解、唯一解。

高斯消元
#include<bits/stdc++.h>
using namespace std;
const int N=150;
double a[N][N],eps=1e-6,ans[N];
int n;
int solve(int n,int m){
    int c=1,r=1;
    for(;r<=n&&c<=m;r++,c++){
        int mr=r;
        for(int i=r+1;i<=n;i++){
            if(abs(a[i][c])>abs(a[mr][c])){
                mr=i;
            }
        }
        if(mr!=r)swap(a[r],a[mr]);
        if(fabs(a[r][c])<eps){
            r--;
            continue;
        }
        for(int i=r+1;i<=n;i++){
            if(fabs(a[i][c])>eps){
                double k=a[i][c]/a[r][c];
                for(int j=c;j<=m+1;j++)a[i][j]-=a[r][j]*k;
                a[i][c]=0;
            }
        }
    }
    for(int i=r;i<=m;i++){
        if(fabs(a[i][c])>eps){
            return -1;
            //无解
        }
    }
    if(r<=m)return m-r+1;
    //有无数组解
    for(int i=m;i;i--){
        for(int j=i+1;j<=m;j++)a[i][m+1]-=a[i][j]*ans[j];
        ans[i]=a[i][m+1]/a[i][i];
    }
    return 0;
}
int main(){
    // freopen("1.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+1;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    int cnt=solve(n,n);
    if(cnt==-1)printf("-1");
    else if(cnt)printf("0");
    else{
        for(int i=1;i<=n;i++){
            // printf("%.2lf\n",ans[i]);
            // if(fabs(ans[i])<eps)printf("x%d=0\n",i);
            // else 
            printf("x%d=%.2lf\n",i,ans[i]);
        }
    }
    return 0;
}

快一点,但是只能判断有无唯一解。
upd:实测并没有快多少

标签:va,ch,return,int,板子,ans,一些,root
From: https://www.cnblogs.com/0shadow0/p/18395355

相关文章

  • selenium中解决非input标签上传文件时的一些问题
    最近在上传文件时遇到了一些问题:一、使用pyautogui①、使用pyautogui模拟在windows弹窗中输入文件路径,因系统输入法默认为中文,导致上传失败②、后来修改代码,在每次输入文件路径之前,先用热键将输入法切换为英文,然而稳定性不高importtimetry:sel......
  • 华为鸿蒙手机安装好谷歌商店,GMS服务,谷歌三件套,谷歌框架后,下载的一些应用无法正常定位,
    最近有有小伙伴问为什么他下载好一些定位的软件,能正常的进入,定位权限也是开启的,但是就是定不了位,,给我们小伙伴带来了烦恼,那我们怎么解决呢?我这里给大家讲解一下,避免大家以后遇见后不知道怎么去解决解决方法1.首先我们需要在我们的手机设置里面找到我们的应用和服务,进去后点......
  • Hive的一些基本函数(二)
    一、窗口函数当查询的要求,既要明细查询又要统计查询的时候,这时候考虑开窗,通过over语法让两种查询同时执行比如:需求:查询每个订单的信息,以及订单的总数姓名,购买日期,购买数量saml,2018-01-01,10saml,2018-01-08,55tony,2018-01-07,50saml,2018-01-05,46tony,2018-01-04......
  • 图论板子
    Primtypedefpair<int,int>P;intprim(){intans=0,cnt=0;priority_queue<P,vector<P>,greater<P>>q;fill(d+1,d+n+1,INF);d[1]=0;q.push(P(d[1],1));while(!q.empty()&&cnt<......
  • flutter 的一些概念三
    本文同步发布于公众号:stringwu的互联网杂谈:flutter的一些概念三1Stream与Future的关系Stream和Future都是Flutter中常用的异步编程模型,Future适用于一次性异步操作,Stream适用于连续的异步操作1.1FutureFuture一次性的操作,只会返回一个结果;可以使用await和asy......
  • AS-V1000视频监控平台客户端播放实时视频时,一些视频画面显示的时间不准确的解决方法
    目录一、背景说明二、解决过程  1、查看设备时间  2、查看服务器时间  3、ntp介绍  1)ntp的概念  2)ntp的同步方式  3)ntp的优势  4、自动校准服务器和设备时间  1)下载ntp  2)修改ntp.conf  3)重启ntp服务,自动校准时间......
  • 高中数学题的一些背景思考 1 —— 裴蜀定理
    1裴蜀定理「\(\in\)数论」题目设集合\(M=\left\{7m+5n\left|m,n\in\Z\right.\right\},N=\left\{3m-2n\left|m,n\in\Z\right.\right\}\)。试判断集合\(M,N\)的关系。从gcd和Euclid说起比方说我要求\(\gcd(a,b)\),不妨\(a>b\)。令\(r_0=b\),\[\begin{align......
  • 高中数学题的一些背景思考 2 —— Chebyshev 多项式
    Chebyshev多项式「\({\in}\)代数」这个家伙十分重要!可以牵扯出一堆相关的东西。题目1已知\(a,b,c\in\R,\forallx\in[-1,1]\),都有\(\left|ax^2+bx+c\right|\le1\),则当\(x\in[-1,1]\)时,函数\(f(x)=\left|\left(ax^2+bx+c\right)\left(cx^2+bx+a\right)\right|\)的最......
  • 回归の一些想法
    现在是2024.9.520:00我坐在离BJUT2公里外的一家星巴克里简短的写下这些文字距离第一次接触算法竞赛已经过去了三年“我并没有如此强大闪耀一次就足够”感谢:感谢我的父母家人对我无限的支持感谢GG带我进入OI的世界感谢KHIN、wind_whisper两位神仙给予我莫大的帮助......
  • canvas版本的俄罗斯方块,少一个全行填充消除,有兴趣再加,俄罗斯方块还是复杂一些
    代码:<!Doctypehtml><htmllang="zh_cn"><head><metahttp-equiv="Content-Type"content="text/html;charset=utf-8"/><title>俄罗斯方块</title><metaname="Ke......