昆虫科学院模板库

标签：le int ll long vector 模板昆虫科学院 mod

前言：这是我们昆虫科学院自主开发的模板库。

模板库完整代码 (Private，私人链接)，如果需要私信我（@zyc212303）。

模板库编译选项：

-std=gnu++17 -O2

使用该模板时，请在程序开头加上如下语句：

#include<bits/stdc++.h>
using namespace std;

现已有：快速 IO、并查集、ST 表、树状数组、扫描线、数论相关等内容。

本模板库在部分问题上参考了 AtCoder Library 的处理方式。

快速 IO（Fast IO）

namespace IAOI_lib{
  typedef long long ll;
  inline int read(){
    int x=0; char c=getchar(); bool f=false;
    while(!isdigit(c)){
      if(c=='-')f=true;
      c=getchar();
    }
    while(isdigit(c)){
      x=(x<<1)+(x<<3)+(c^48);
      c=getchar();
    }
    return f?-x:x;
  }
  inline void write(int x){
    if(x<0){putchar('-'); write(-x); return;}
    if(x/10)write(x/10);  putchar(x%10+48);
  }
  inline ll readll(){
    ll x=0; char c=getchar(); bool f=false;
    while(!isdigit(c)){
      if(c=='-')f=true;
      c=getchar();
    }
    while(isdigit(c)){
      x=(x<<1ll)+(x<<3ll)+(c^48ll);
      c=getchar();
    }
    return f?-x:x;
  }
  inline void writell(ll x){
    if(x<0){putchar('-'); write(-x); return;}
    if(x/10)write(x/10);  putchar(x%10+48);
  }
}

功能介绍

int read() / long long readll()：从标准输入读取一个整数；
int write() / long long writell()：向标准输出写入一个整数。

示例代码

P9515「JOC-1A」签到题 by zyc212303

并查集（DSU）

namespace IAOI_lib{
  template<typename T> class dsu{
    private:
      vector<T> a;
      vector<int> s;
    public:
      dsu(){
        a.resize(200000),s.resize(200000);
        iota(a.begin(),a.end(),0);
        fill(s.begin(),s.end(),1);
      }
      dsu(int n){
        a.resize(n),s.resize(n);
        iota(a.begin(),a.end(),0);
        fill(s.begin(),s.end(),1);
      }
      T leader(T x){
        return a[x]==x?x:a[x]=leader(a[x]);
      }
      int size(T x){
        return s[leader(x)];
      }
      void merge(T x,T y){
        x=leader(x),y=leader(y);
        if(s[x]>s[y])swap(x,y);
        s[y]+=s[x],a[x]=y;
      }
      bool same(T x,T y){
        return leader(x)==leader(y);
      }
  };
}

功能介绍

UPD：增加了带权功能（即维护连通块大小）。

dsu<T> d(int n)：创建一个大小为 \(n(1\le n\le 10^8)\)（如果不添加 (int n) 则为默认大小 \(2\times 10^5\)）、存储类型为 T 的并查集，时间复杂度 \(O(n)\)（下文 \(x,y\) 的范围均为 \(0\le x,y<n\)）；
T d.leader(T x)：返回 \(x\) 的祖先，时间复杂度 \(O(\alpha(n))\)；
int d.size(T x)：返回 \(x\) 所在连通块（集合）的大小，时间复杂度 \(O(\alpha(n))\)；
void d.merge(T x,T y)：合并 \(x\) 和 \(y\) 所在的连通块（集合），时间复杂度 \(O(\alpha(n))\)；
bool d.same(T x,T y)：返回 \(x\) 和 \(y\) 是否在同一个连通块（集合）内，时间复杂度 \(O(\alpha(n))\)。

示例代码

P9488 ZHY 的生成树 by zyc212303

ST 表（Sparse Table）

namespace IAOI_lib{
  template<typename T,T(*op)(T,T)> class sparse_table{
    private:
      vector<vector<T> > s;
    public:
      sparse_table(vector<T> a){
        int k=__lg(a.size());
        s.resize(a.size(),vector<T>(k+1));
        for(int i=0;i<a.size();i++)
          s[i][0]=a[i];
        for(int i=1;i<=k;i++)
          for(int j=0;j+(1<<i)<=a.size();j++)
            s[j][i]=op(s[j][i-1],s[j+(1<<i-1)][i-1]);
      }
      T query(int l,int r){
        int k=__lg(r-l+1);
        return op(s[l][k],s[r-(1<<k)+1][k]);
      }
  };
}

功能介绍

sparse_table<T,op> s(vector<T> a)：对于存储 T 类型的 \(a\) 数组（std::vector）创建一个 ST 表，\(op\) 为你需要维护的操作（特别地，它需要满足消去律 \(op(x,x)=x\)），时间复杂度 \(O(n\log n)\)，这里 \(n(1\le n\le 2\times 10^6)\) 为 \(a\) 的大小；
T s.query(int l,int r)：返回 \(op(a_l,a_{l+1},\ldots,a_r)\) 的值，时间复杂度 \(O(1)\)。

示例代码

P2412 查单词 by zyc212303

树状数组（Fenwick Tree）

namespace IAOI_lib{
  template<typename T> class fenwick_tree{
    private:
      vector<int> t;
    public:
      fenwick_tree(){
        t.resize(200000);
      }
      fenwick_tree(int n){
        t.resize(n);
      }
      int lowbit(int x){
        return x&-x;
      }
      void add(int p,T d){
        t[p++]+=d;
        while((p+=lowbit(p))<=t.size())t[p-1]+=d;
      }
      T pre_sum(int p){
        T s=t[p++];
        while((p-=lowbit(p))>0)s+=t[p-1];
        return s;
      }
      T sum(int l,int r){
        return pre_sum(r)-(l?pre_sum(l-1):0);
      }
  };
}

功能介绍

fenwick_tree<T> t：创建一个大小为 \(n(1\le n\le 10^8)\)、存储类型为 T 的树状数组，时间复杂度 \(O(n)\)；
void t.add(int p,T d)：向树状数组 \(t\) 中的第 \(p(0\le p<n)\) 个元素加上 \(d\)，时间复杂度 \(O(\log n)\)；
T t.sum(int l,int r)：返回 \(\sum\limits_{i=l}^r a_i(0\le l\le r<n)\)，时间复杂度 \(O(\log n)\)。

扫描线（Atlantis）

namespace IAOI_lib{
  class atlantis{
#define int long long
    typedef pair<int,int> pii;
    typedef tuple<int,int,int,int> tpi;
    private:
      struct Line{
        int l,r,h,s;
        bool operator <(const Line &x)const{
          return h<x.h;
        }
      };
      int n;
      vector<Line> L;
      vector<pii> B;
      vector<int> X,C,S;
      void build(int u,int l,int r){
        if(B[u]=make_pair(l,r);l==r)return;
        int m=l+r>>1;
        build(u<<1,l,m),build(u<<1|1,m+1,r);
        pushup(u);
      };
      void pushup(int u){
        if(C[u])S[u]=X[B[u].second+1]-X[B[u].first];
        else S[u]=S[u<<1]+S[u<<1|1];
      }
      void update(int u,int l,int r,int c){
        if(X[B[u].second+1]<=l||r<=X[B[u].first])return;
        if(l<=X[B[u].first]&&X[B[u].second+1]<=r)C[u]+=c;
        else update(u<<1,l,r,c),update(u<<1|1,l,r,c);
        pushup(u);
      }
      int all_prod(){return S[1];}
    public:
      int areas_union(vector<tpi> a){
        X.resize(a.size()<<1),L.resize(a.size()<<1);
        for(int i=0;i<a.size();i++){
          auto &[xa,ya,xb,yb]=a[i];
          if(xa>xb)swap(xa,xb); if(ya>yb)swap(ya,yb);
          X[i<<1]=xa,X[i<<1|1]=xb;
          L[i<<1]=(Line){xa,xb,ya,1},L[i<<1|1]=(Line){xa,xb,yb,-1};
        }
        sort(L.begin(),L.end(),[](Line x,Line y){return x.h<y.h;});
        sort(X.begin(),X.end()),n=unique(X.begin(),X.end())-X.begin();
        B.resize(n<<2),C.resize(n<<2),S.resize(n<<3),build(1,0,n-2);
        int c=0;
        for(int i=0;i+1<a.size()<<1;i++){
          update(1,L[i].l,L[i].r,L[i].s);
          c+=all_prod()*(L[i+1].h-L[i].h);
        }
        return c;
      }
  };
}

功能介绍

long long atlantis(vector<tuple<long long,long long,long long,long long> > a)：求若干个四边平行于坐标轴的矩形的面积并。

示例代码

P10096 [ROIR 2023 Day 1] 扫地机器人 by zyc212303

数论（Number Theory）

namespace IAOI_lib{
  vector<int> get_primes(int n){
    vector<bool> b(n+1);
    vector<int> p;
    for(int i=2;i<=n;i++){
      if(!b[i])p.emplace_back(i);
      for(int j:p){
        if(1ll*i*j>n)break;
        b[i*j]=true;
        if(!(i%j))break;
      }
    }
    return p;
  }
  ll safe_mulll(ll a,ll b,ll mod){
    ll r=0;
    while(b){
      if(b&1)(r+=a)%=mod;
      (a<<=1)%=mod; b>>=1;
    }
    return r;
  }
  int pow_mod(int a,int b,int mod){
    int r=1;
    while(b){
      if(b&1)r=r%mod*a%mod;
      a=a%mod*a%mod; b>>=1;
    }
    return r;
  }
  ll pow_modll(ll a,ll b,ll mod){
    ll r=1;
    while(b){
      if(b&1)r=r%mod*a%mod;
      a=a%mod*a%mod; b>>=1;
    }
    return r;
  }
  int inv_p(int x,int mod){
    return pow_mod(x,mod-2,mod);
  }
  ll inv_pll(ll x,ll mod){
    return pow_modll(x,mod-2,mod);
  }
  pair<int,int> exgcd(int a,int b){
    if(!b)return make_pair(1,0);
    auto [x,y]=exgcd(b,a%b);
    int t=x; x=y; y=t-a/b*y;
    return make_pair(x,y);
  }
  pair<ll,ll> exgcdll(ll a,ll b){
    if(!b)return make_pair(1,0);
    auto [x,y]=exgcdll(b,a%b);
    ll t=x; x=y; y=t-a/b*y;
    return make_pair(x,y);
  }
  int inv_cp(int x,int mod){
    if(gcd(x,mod)>1)return -1;
    return (exgcd(x,mod).first%mod+mod)%mod;
  }
  ll inv_cpll(ll x,ll mod){
    if(gcd(x,mod)>1)return -1;
    return (exgcdll(x,mod).first%mod+mod)%mod;
  }
  ll crt(vector<pair<ll,ll> > a){
    ll p=1,s=0;
    for(auto [r,m]:a)p*=m;
    for(auto [r,m]:a){
      ll m2=p/m,i=inv_cpll(m2,m);
      s+=r*m2*i;
    }
    return s;
  }
  ll crt_mod(vector<pair<ll,ll> > a,ll mod){
    ll p=1,s=0;
    for(auto [r,m]:a)p*=m;
    for(auto [r,m]:a){
      ll m2=p/m,i=inv_cpll(m2,m);
      (s+=r*m2%mod*i%mod)%=mod;
    }
    return s;
  }
  double lagrange(vector<pair<int,int> > a,int k){
    double c=0;
    for(int i=0;i<a.size();i++){
      double s1=a[i].nd;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1*=1.0*(k-a[j].first)/(a[i].first-a[j].first);
      c+=s1;
    }
    return c;
  }
  long double lagrange(vector<pair<ll,ll> > a,ll k){
    long double c=0;
    for(int i=0;i<a.size();i++){
      long double s1=a[i].nd;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1*=1.0*(k-a[j].first)/(a[i].first-a[j].first);
      c+=s1;
    }
    return c;
  }
  int lagrange_mod(vector<pair<int,int> > a,int k,int mod){
    int c=0;
    for(int i=0;i<a.size();i++){
      int s1=a[i].nd%mod,s2=1;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1=s1*(k-a[j].first)%mod,
          s2=s2*(a[i].first-a[j].first)%mod;
      (c+=s1*inv_cp((s2%mod+mod)%mod,mod)%mod+mod)%=mod;
    }
    return c;
  }
  ll lagrange_modll(vector<pair<ll,ll> > a,ll k,ll mod){
    ll c=0;
    for(int i=0;i<a.size();i++){
      ll s1=a[i].nd%mod,s2=1;
      for(int j=0;j<a.size();j++)
        if(i!=j)s1=s1*(k-a[j].first)%mod,
          s2=s2*(a[i].first-a[j].first)%mod;
      (c+=s1*inv_cpll((s2%mod+mod)%mod,mod)%mod+mod)%=mod;
    }
    return c;
  }
}

功能介绍

vector<int> get_primes(int n)：查找 \([2,n](2\le n\le 10^8)\) 以内的所有质数，并返回包含它们的一个数组（std::vector），时间复杂度 \(O(n)\)；
long long safe_mulll(long long a,long long b,long long mod)：返回 \(a\times b\bmod mod(0\le a,b\le 10^{18},1\le mod\le 10^{18})\) 的值，时间复杂度 \(O(\log b)\)；
int pow_mod(int a,int b,int mod) / long long pow_modll(long long a,long long n,long long mod)：返回 \(a^b\bmod mod(0\le a,b\le 10^{9},1\le mod\le 10^{9})\) 的值，时间复杂度 \(O(\log b)\)；
int inv_p(int x,int mod) / long long inv_pll(long long x,long long mod)：返回 \(x(1\le x<mod)\) 在模 \(mod(1\le mod\le 10^9)\)（\(mod\) 是质数）意义下的逆元，时间复杂度 \(O(\log mod)\)；
pair<int,int> exgcd(int a,int b)：返回关于 \(x,y\) 的不定方程 \(ax+by=1\) 的解 \((x,y)\)，时间复杂度 \(O(\log\max(a,b))\)；
int inv_cp(int x,int mod) / long long inv_cpll(long long x,long long mod)：返回 \(x(1\le x<mod)\) 在模 \(mod(1\le mod\le 10^9)\)（\(mod\) 不一定是质数）意义下的逆元，如果 \(x\) 没有逆元返回 \(-1\)，时间复杂度 \(O(\log mod)\)；
long long crt(vector<pair<long long,long long> > a) / long long crt_mod(vector<pair<long long,long long> > a,int mod)：返回满足 \(\forall1\le i,j\le n\land i\ne j,m_i\perp m_j\) 的方程组

\[\begin{cases} x\equiv r_0\pmod {m_0}\\ x\equiv r_1\pmod {m_1}\\ \vdots\\ x\equiv r_{n-1}\pmod {m_{n-1}}\\ \end{cases} \]
的最小非负整数解 \(x\)，时间复杂度 \(O(n\log\max\{m_i\})\)。可选择是否将 \(x\) 对某个数 \(mod\) 取模；
double lagrange(vector<pair<int,int> > a,int k) / long double lagrange(vector<pair<long long,long long> > a,long long k)：通过其在若干个点上的值确定一个多项式 \(f(x)\) 并求出 \(f(k)\)，时间复杂度 \(O(n^2)\)，这里 \(n\) 是 \(a\) 的大小，即给出的点的个数；
int lagrange_mod(vector<pair<int,int> > a,int k,int mod) / long long lagrange_modll(vector<pair<long long,long long> > a,long long k,long long mod)：同上，求出 \(f(k)\bmod mod\)，时间复杂度 \(O(n^2)\)。

示例代码

P2480 古代猪文 by zyc212303

标签：le,int,ll,long,vector,模板,昆虫,科学院,mod
From： https://www.cnblogs.com/physics212303/p/17981109

快速 IO（Fast IO）

功能介绍

示例代码

并查集（DSU）

功能介绍

示例代码

ST 表（Sparse Table）

功能介绍

示例代码

树状数组（Fenwick Tree）

功能介绍

扫描线（Atlantis）

功能介绍

示例代码

数论（Number Theory）

功能介绍

示例代码

相关文章

赞助商

阅读排行