整理的各种模板（随时弃坑emmmmm）-白红宇

整理的各种模板（随时弃坑emmmmm）

阅读量：5248 次

发布时间：2019-06-14

本文共 11908 字，大约阅读时间需要 39 分钟。

线段树：

#include
    
     #include
     
      #include
      
       #include
       
        #define lson rt<<1#define rson rt<<1|1#define ll long longusing namespace std;inline ll read(){    char c=getchar();ll num=0,f=1;    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) num=num*10+c-'0';    return num*f;}const ll N=1e5+5;ll n,m;ll a[N];struct Tree{    ll len;                   //记录掌管的区间的长度数(元素个数     ll maxn,minn,sum;         //最大最小值、区间和     ll lazy;                  //lazy标记 }tree[N<<2];inline void pushup(ll rt)     //用儿子更新当前节点 {    tree[rt].maxn=max(tree[lson].maxn,tree[rson].maxn);    tree[rt].minn=min(tree[lson].minn,tree[rson].minn);    tree[rt].sum=tree[lson].sum+tree[rson].sum;    return;}void build(ll rt,ll l,ll r)    //rt为当前的树根，l,r为rt对应的区间 {    tree[rt].len=r-l+1;        //当前节点掌管的区间长度(元素个数     if(l==r)                   //建到叶子节点了     {        tree[rt].maxn=a[l];    //rt就是位置l对应的节点         tree[rt].minn=a[l];        tree[rt].sum=a[l];        return;    }    ll mid=(l+r)>>1;    build(lson,l,mid);          //建左儿子rt*2，对应区间[l,mid]     build(rson,mid+1,r);        //建右儿子rt*2+1，对应区间[mid+1,r]     pushup(rt);                 //更新当前区间 }inline void pushdown(ll rt)     //下传lazy标记 {    if(tree[rt].lazy)    {        //更新孩子的lazy标记         tree[lson].lazy+=tree[rt].lazy;        tree[rson].lazy+=tree[rt].lazy;        //更新孩子的最大值         tree[lson].maxn+=tree[rt].lazy;        tree[rson].maxn+=tree[rt].lazy;        //更新孩子的最小值         tree[lson].minn+=tree[rt].lazy;        tree[rson].minn+=tree[rt].lazy;        //更新孩子的区间和         tree[lson].sum+=tree[rt].lazy*tree[lson].len;        tree[rson].sum+=tree[rt].lazy*tree[rson].len;        //lazy重置         tree[rt].lazy=0;    }    return;}void modify(ll rt,ll l,ll r,ll pos,ll val)  //单点修改 {    if(l==r)    //找到pos对应的叶子节点了     {        tree[rt].maxn+=val;        tree[rt].minn+=val;        tree[rt].sum+=val;        return;    }    pushdown(rt);                 //下放当前区间lazy标记    ll mid=(l+r)>>1;    if(pos<=mid)                  //pos在左儿子里         modify(lson,l,mid,pos,val);    else                       //在右儿子里         modify(rson,mid+1,r,pos,val);     pushup(rt);                 //更新当前区间 }void Modify(ll rt,ll l,ll r,ll L,ll R,ll val)   //区间修改 {    if(l==L&&r==R)  //找到一个合法区间     {        tree[rt].sum+=tree[rt].len*val;        tree[rt].maxn+=val;        tree[rt].minn+=val;        tree[rt].lazy+=val;        return;    }    pushdown(rt);    ll mid=(l+r)>>1;    if(R<=mid)        Modify(lson,l,mid,L,R,val);    else if(L>mid)        Modify(rson,mid+1,r,L,R,val);    else        Modify(lson,l,mid,L,mid,val),Modify(rson,mid+1,r,mid+1,R,val);    pushup(rt);                               //不要忘了pushup }ll query_sum(ll rt,ll l,ll r,ll L,ll R)         //查询区间和 {    if(l==L&&r==R)                           //找到了一个合法区间，返回区间和         return tree[rt].sum;    pushdown(rt);    ll mid=(l+r)>>1;    if(R<=mid)                              //查询区间全在左子树         return query_sum(lson,l,mid,L,R);    else if(L>mid)                          //查询区间全在右子树         return query_sum(rson,mid+1,r,L,R);    else                                     //一块在左子树，一块在右子树         return query_sum(lson,l,mid,L,mid)+query_sum(rson,mid+1,r,mid+1,R);}ll query_max(ll rt,ll l,ll r,ll L,ll R){    if(l==L&&r==R)        return tree[rt].maxn;    pushdown(rt);    ll mid=(l+r)>>1;    if(R<=mid)        return query_max(lson,l,mid,L,R);    else if(L>mid)        return query_max(rson,mid+1,r,L,R);    else        return max(query_max(lson,l,mid,L,mid),query_max(rson,mid+1,r,L,R));}ll query_min(ll rt,ll l,ll r,ll L,ll R){    if(l==L&&r==R)        return tree[rt].minn;    pushdown(rt);    ll mid=(l+r)>>1;    if(R<=mid)        return query_min(lson,l,mid,L,R);    else if(L>mid)        return query_min(rson,mid+1,r,L,R);    else        return min(query_min(lson,l,mid,L,mid),query_min(rson,mid+1,r,L,R));};ll opt;ll x,l,r,val;int main(){    n=read(),m=read();    for(ll i=1;i<=n;++i)        a[i]=read();    build(1,1,n);    while(m--)    {        opt=read();        if(opt==2)        {            l=read(),r=read();            cout<
        
         <<'\n';        }        else if(opt==1)        {            l=read(),r=read(),val=read();            Modify(1,1,n,l,r,val);        }    }    return 0;}

st表：

#include
    
     #include
     
      #include
      
       using namespace std;int n,m,f[100005][33],lg[100005];int main(){    scanf("%d%d",&n,&m);    lg[0]=-1;    for(int i=1;i<=n;++i)    {        scanf("%d",&f[i][0]);        lg[i]=lg[i>>1]+1;    }    for(int j=1;j<=19;++j)    {        for(int i=1;i+(1<
       
        <=n;++i)        {            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);        }    }    for(int i=1,l,r;i<=m;++i)    {        scanf("%d%d",&l,&r);        int k=lg[r-l+1];        cout<
        
         <
         
          <<"\n"; } return 0;}

dijkstra(O(n²))：

#include
    
     #include
     
      #include
      
       #include
       
         #define maxn 500000+1#define maxn1 10000+1using namespace std;inline int qread(){    char c=getchar();int num=0,f=1;    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) num=num*10+c-'0';    return num*f;}struct Edge{    int v,w,nxt;}edge[maxn];int head[maxn],num;void ct(int u,int v,int w){    edge[++num].v=v;    edge[num].w=w;    edge[num].nxt=head[u];    head[u]=num;}int n,m,s;int dis[maxn1],vis[maxn1];void dijkstra(){    dis[s]=0;    for(int i=1;i<=n;++i)    {        int minn=0x7fffffff,u=-1;        for(int j=1;j<=n;++j)        {            if(!vis[j]&&dis[j]
        
         dis[u]+edge[j].w)              dis[v]=dis[u]+edge[j].w;        }    }}int main(){    n=qread(),m=qread(),s=qread();    for(int i=1;i<=n;++i)    dis[i]=0x7fffffff;    for(int i=1,u,v,w;i<=m;++i)    {        u=qread(),v=qread(),w=qread();        ct(u,v,w);    }    dijkstra();    for(int i=1;i<=n;++i)    printf("%d ",dis[i]);    return 0;}

堆优化dijkstra(O(nlogn))：

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 200000+1#define maxn1 100000+1using namespace std;struct Edge{    int v,nxt,w;}edge[maxn];int num,head[maxn],n,m,s,dis[maxn1];struct node{    int x,y;    bool operator < (const node &a) const    {        return y>a.y;    } };inline void ct(int u,int v,int w){    edge[++num].v=v;    edge[num].w=w;    edge[num].nxt=head[u];    head[u]=num;}inline int qread(){    char c=getchar();int num=0,f=1;    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) num=num*10+c-'0';    return num*f;}inline void dijkstra(){    memset(dis,0x3f,sizeof(dis));    dis[s]=0;    priority_queue
        
         q;    q.push((node){s,0});    while(!q.empty())    {        int u=q.top().x,d=q.top().y;        q.pop();        if(d!=dis[u]) continue;        for(int i=head[u];i;i=edge[i].nxt)        {            int v=edge[i].v;            if(dis[v]>dis[u]+edge[i].w)            {                dis[v]=dis[u]+edge[i].w;                q.push((node){v,dis[v]});               }           }       } }int main(){    n=qread(),m=qread(),s=qread();    for(int i=1,u,v,w;i<=m;++i)    {        u=qread(),v=qread(),w=qread();        ct(u,v,w);    }    dijkstra();    for(int i=1;i<=n;++i)        cout<
         
          <<" "; return 0;}

堆：

#include
    
     #include
     
      #include
      
       using namespace std;int n;int main(){    priority_queue

,greater

>q; scanf("%d",&n); while(n--) { int k; scanf("%d",&k); if(k==1) { scanf("%d",&k); q.push(k); } else if(k==2) printf("%d\n",q.top()); else q.pop(); } return 0;}

并查集：

#include
    
     #include
     
      #define X 10000+10using namespace std;int fa[X];int find(int x){    if(fa[x]!=x) return fa[x]=find(fa[x]);    return x;}void fac(int x,int y){    x=find(x),y=find(y);    fa[x]=y;}bool pd(int x,int y){    if(find(x)==find(y)) return 1;    return 0;}int main(){    int n,m,a,b,z;    cin>>n>>m;    for(int i=1;i<=n;++i)    fa[i]=i;    while(m--)    {        cin>>z>>a>>b;        if(z==1)         {            if(find(a)!=find(b))             fac(a,b);        }         if(z==2)        {            if(pd(a,b)==1) cout<<"Y"<

乘法逆元：

#include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;const int maxn=3e6+1;ll inv[maxn],n,p;int main(){    scanf("%lld%lld",&n,&p);    inv[1]=1;    for(int i=2;i<=n;++i)    {        inv[i]=(ll)(p-p/i)*inv[p%i]%p;    }    for(int i=1;i<=n;++i)    {        cout<
       
        <<'\n';    }    return 0;}

LCA：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define maxn 500001using namespace std;int n,m,s,num,d[maxn],head[maxn],f[maxn][21];inline int qread(){    char c=getchar();int num=0,f=1;    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;    for(;isdigit(c);c=getchar()) num=num*10+c-'0';    return num*f;}struct node{    int v,nxt;}e[maxn<<1];inline void ct(int u,int v){    e[++num].v=v;    e[num].nxt=head[u];    head[u]=num;}void dfs(int u,int fa){    for(int i=head[u];i;i=e[i].nxt)    {        int v=e[i].v;        if(v!=fa)        {            d[v]=d[u]+1;            f[v][0]=u;            dfs(v,u);        }    }}inline int lca(int a,int b){    if(d[a]>d[b]) swap(a,b);    for(int i=20;i>=0;--i)    if(d[a]<=d[b]-(1<
         
          =0;--i) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i]; return f[a][0];}int main(){ n=qread();m=qread();s=qread(); for(int i=1,u,v;i

缩点：

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 10001using namespace std;bool vis[maxn];int n,m,head[maxn],block[maxn],bel[maxn],size[maxn],js,cnt,num,dfn[maxn],low[maxn];int f[maxn],zrj,w[maxn];struct node {  int u,v,nxt;}e[100001];inline void ct(int u, int v) {  e[++num].u=u;  e[num].v=v;  e[num].nxt=head[u];  head[u]=num;}stack
        
         q;void tarjan(int u) {  dfn[u]=low[u]=++cnt;  q.push(u),vis[u]=1;  for(int i=head[u];i;i=e[i].nxt) {    int v=e[i].v;    if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);    else if(vis[v]) low[u]=min(low[u],dfn[v]);  }  if(dfn[u]==low[u]) {    int x;js++;    while(x!=u) {      x=q.top(),q.pop();      size[js]++,bel[x]=js;      block[js]+=w[x];      vis[x]=0;    }  }}void dfs(int u) {  int maxx=0;  if(f[u]) return;  f[u]=block[u];  for(int i=head[u];i;i=e[i].nxt) {    int v=e[i].v;    if(!f[v]) dfs(v);    maxx=max(maxx,f[v]);  }  f[u]+=maxx;}int main() {  scanf("%d%d",&n,&m);  for(int i=1;i<=n;++i) scanf("%d",&w[i]);  for(int i=1,u,v;i<=m;++i) {    scanf("%d%d",&u,&v);    ct(u,v);  }  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);  memset(head,0,sizeof(head));num=0;  for(int i=1;i<=m;++i) if(bel[e[i].u]!=bel[e[i].v]) ct(bel[e[i].u],bel[e[i].v]);  for(int i=1;i<=js;++i) {    if(!f[i]) dfs(i);    zrj=max(zrj,f[i]);  }  printf("%d\n",zrj);  return 0;}

割点：

#include
    
     #include
     
      #define maxn 20007using namespace std;int n,m,head[maxn],dfn[maxn],low[maxn],bel[maxn],size[maxn],num,cnt,js,zrj;bool vis[maxn],bj[maxn];struct node {  int v,nxt;}e[200007];inline void ct(int u, int v) {  e[++num].v=v;  e[num].nxt=head[u];  head[u]=num;}void tarjan(int u, int fa) {  int child=0;  dfn[u]=low[u]=++cnt;  for(int i=head[u];i;i=e[i].nxt) {    int v=e[i].v;    if(!dfn[v]) {      tarjan(v, fa);      low[u]=min(low[u],low[v]);      if(u!=fa&&low[v]>=dfn[u]) bj[u]=1;      if(u==fa) child++;    }    low[u]=min(low[u],dfn[v]);  }  if(u==fa&&child>=2) bj[u]=1;}int main() {  scanf("%d%d",&n,&m);  for(int i=1,u,v;i<=m;++i) {    scanf("%d%d",&u,&v);    ct(u,v),ct(v,u);  }  for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,i);  for(int i=1;i<=n;++i) if(bj[i]) zrj++;    printf("%d\n",zrj);  for(int i=1;i<=n;++i) if(bj[i]) printf("%d ",i);  printf("\n");  return 0;}

转载于:https://www.cnblogs.com/grcyh/p/9790106.html

你可能感兴趣的文章

SPI ServiceLoader源码分析