算法归档 - yingyany

杂项

求sum值 accumulate（范围起点，范围终点，初始值）

priority_queue< int >pq; 大根堆

priority_queue<int, vector< int >, greater<>>pq; 小根堆

*max(min)_element(范围起点，范围终点) 区间最大(小)值

max(min)_element(范围起点，范围终点) - 范围起点区间最大(小)值的坐标

基础数学

最小公倍数和最大公因数

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b; 
}

快速幂

普通快速幂

ll power(ll a, ll b, ll p) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}  //  a^b

这是哥哥的代码（高精度快速幂）

ll mul(ll a, ll b, ill p) {
    ll c = a * b - ll(1.0L * a * b / p) * p;
    c %= p;
    if (c < 0) {
        c += p;
    }
    return c;
}
ll power(ll a, ll b, ll p) {
    ll res = 1;
    for (; b; b /= 2, a = mul(a, a, p)) {
        if (b % 2) {
            res = mul(res, a, p);
        }
    }
    return res;
}

线性筛

由于埃氏筛的复杂度不是最优的，属于线性筛的下位，所以我们直接学习线性筛

线性筛也叫欧拉筛，可以用于求各种积性函数，比如欧拉函数，莫比乌斯函数约数个数和约数和之类的

  vector<int> pri;
  bool not_prime[N];

  void pre(int n) {
    for (int i = 2; i <= n; ++i) {
      if (!not_prime[i]) {
        pri.push_back(i);
      }
      for (int pri_j : pri) {
        if (i * pri_j > n) break;
        not_prime[i * pri_j] = true;
        if (i % pri_j == 0) break;
      }
    }
  }

其中 $n o_{p} r im e$ 判断是否是质数， $p r i$ 表示第i个质数如第一个是2第二个是3以此类推

求欧拉函数

欧拉函数的意思是从1到n-1中有多少个数和n互质

  vector<int> pri;
  bool not_prime[N];
  int phi[N];

  void pre(int n) {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
      if (!not_prime[i]) {
        pri.push_back(i);
        phi[i] = i - 1;
      }
      for (int pri_j : pri) {
        if (i * pri_j > n) break;
        not_prime[i * pri_j] = true;
        if (i % pri_j == 0) {
          phi[i * pri_j] = phi[i] * pri_j;
          break;
        }
        phi[i * pri_j] = phi[i] * phi[pri_j];
      }
    }
  }

其中 $p hi [i]$ 就代表着才从1~i中有多少个数字和i互质

求莫比乌斯函数

根据莫比乌斯函数的定义，设 𝑛是一个合数，𝑝1是 𝑛的最小质因子， $n^{'} = \frac{n}{p _{1}}$ !，有：

莫比乌斯函数 $μ (n)$ 的定义如下：

μ (n) = {0 - μ (n^{'}) n^{'} mod p_{1} = 0 otherwise

若 𝑛 是质数，有 𝜇(𝑛) = −1。

  vector<int> pri;
  bool not_prime[N];
  int mu[N];

  void pre(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
      if (!not_prime[i]) {
        mu[i] = -1;
        pri.push_back(i);
      }
      for (int pri_j : pri) {
        if (i * pri_j > n) break;
        not_prime[i * pri_j] = true;
        if (i % pri_j == 0) {
          mu[i * pri_j] = 0;
          break;
        }
        mu[i * pri_j] = -mu[i];
      }
    }
  }

求约数个数

定理：若 $n = i = 1 \prod m p_{i}^{c_{i}}$ ，则 $d (n) = i = 1 \prod m (c_{i} + 1)$

证明：我们知道 $p_{i}^{c_{i}}$ 的约数有 $p_{i}^{0}, p_{i}^{1}, \dots, p_{i}^{c_{i}}$ 共 $c_{i} + 1$ 个，根据乘法原理， $n$ 的约数个数就是 $i = 1 \prod m (c_{i} + 1)$

用 𝑑[i]表示 𝑖的约数个数，𝑛𝑢𝑚[i]表示 𝑖的最小质因子出现次数。

  vector<int> pri;
  bool not_prime[N];
  int d[N], num[N];

  void pre(int n) {
    d[1] = 1;
    for (int i = 2; i <= n; ++i) {
      if (!not_prime[i]) {
        pri.push_back(i);
        d[i] = 2;
        num[i] = 1;
      }
      for (int pri_j : pri) {
        if (i * pri_j > n) break;
        not_prime[i * pri_j] = true;
        if (i % pri_j == 0) {
          num[i * pri_j] = num[i] + 1;
          d[i * pri_j] = d[i] / num[i * pri_j] * (num[i * pri_j] + 1);
          break;
        }
        num[i * pri_j] = 1;
        d[i * pri_j] = d[i] * 2;
      }
    }
  }

求组合数

当n，m< 100000时使用逆元预处理

ll f[N],g[N],P;
ll power(ll a, ll b, ll p) {
    int res = 1;
    for (; b; b /= 2, a = 1LL * a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}  //  a^b
void init(){
    f[0]=g[0]=1;
    for(int i=1;i<N;i++){
    f[i]=f[i-1]*i%P;
    g[i]=power(f[i],P-2,P)%P;
  }
}
ll C(ll n,ll m){
  return f[n]*g[m]%P*g[n-m]%P;
}
ll A(ll n, ll m) {
  return f[n] * g[n-m] % P;
}
//注意是否需要取模数

当n，m<1e18时但是p<100000我们可以使用卢卡斯定理

ll lucas(ll n, ll m){
  if(m==0) return 1;
  return lucas(n/p,m/p,p)* C(n%p,m%p,p)%p;
}

字符串

KMP算法

const int N=1000010;
string S,P;//S：文本串，P：模式串
int n,m,ne[N];  //前缀函数ne[i]：字符串[1~i]，相等真前缀与真后缀的长度
int main(){
  cin>>S>>P;//n代表S的长度，m代表P的长度
  ne[1]=0;
  for(int i=2,j=0; i<=n; i++){
    while(j && P[i]!=P[j+1]) j=ne[j];
    if(P[i]==P[j+1]) j++;
    ne[i]=j; //ababaa：ne[3]=1,ne[4]=2,ne[5]=3,ne[6]=1
  }

  for(int i=1,j=0; i<=m; i++){
    while(j && S[i]!=P[j+1]) j=ne[j]; //失配前跳
    if(S[i]==P[j+1]) j++;             //匹配后移
    if(j==n) printf("%d\n",i-n+1);    //全配记录
  }

  for(int i=1;i<=n;i++) printf("%d ",ne[i]);

Manecher

const int N=3e7;
char a[N],s[N];
int d[N]; //回文半径函数 

void get_d(char*s,int n){ //d函数
  d[1]=1;
  for(int i=2,l,r=1;i<=n;i++){
    if(i<=r) d[i]=min(d[r-i+l],r-i+1);
    while(s[i-d[i]]==s[i+d[i]]) d[i]++;
    if(i+d[i]-1>r) l=i-d[i]+1,r=i+d[i]-1;
  }  
}
int main(){
  scanf("%s",a+1);
  int n=strlen(a+1),k=0;
  s[0]='$',s[++k]='#';
  for(int i=1;i<=n;i++) s[++k]=a[i],s[++k]='#';
  n=k;

  get_d(s,n);
  int ans=0;
  for(int i=1;i<=n;i++) ans=max(ans,d[i]);

 printf("%d\n",ans-1);
}

jiangly版本

std::vector<int> manacher(std::vector<int> s) {
    std::vector<int> t{0};
    for (auto c : s) {
        t.push_back(c);
        t.push_back(0);
    }
    int n = t.size();
    std::vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = std::min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

字典树

const int N=3000010;
int T,q,n;
char s[N];
int ch[N][65],cnt[N],idx;

int getnum(char x){
  if(x>='A'&&x<='Z') return x-'A'; //0~25
  else if(x>='a'&&x<='z') return x-'a'+26; //26~51
  else return x-'0'+52; //52~61
}
void insert(char *s){
  int p=0;
  for(int i=0; s[i]; i++){
    int j=getnum(s[i]); //字母映射
    if(!ch[p][j]) ch[p][j]=++idx;
    p=ch[p][j];
    cnt[p]++; //插入次数
  }
}
int query(char *s){
  int p=0;
  for(int i=0; s[i]; i++){
    int j=getnum(s[i]);
    if(!ch[p][j]) return 0;
    p=ch[p][j];
  }
  return cnt[p];
}
int main(){
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%s",s), insert(s);
    for(int i=1;i<=q;i++) scanf("%s",s), printf("%d\n",query(s));

    for(int i=0;i<=idx;i++)
    for(int j=0;j<=122;j++) ch[i][j]=0;
    for(int i=0;i<=idx;i++) cnt[i]=0;
    idx=0;
  }
  return 0;
}

图论

DIJ（单源最短路）

复杂度为：O((n+m)logm

const int N=100010;
int n,m,s,a,b,c;
vector<pair<int,int>> e[N];
int d[N],vis[N];

void dijkstra(){
  memset(d,0x3f,sizeof d); d[s]=0;
  priority_queue<pair<int,int>> q;
  q.push({0,s});
  while(q.size()){
    auto u=q.top().second; q.pop();
    if(vis[u])continue; //再出队跳过
    vis[u]=1; //第1次出队
    for(auto [v,w]:e[u]){
      if(d[v]>d[u]+w){ //松弛
        d[v]=d[u]+w;
        q.push({-d[v],v});
      }
    }
  }
}

SPFA(单源最短路判负环)

const int N=10010,M=500010,inf=(1<<31)-1;
int n,m,s,a,b,c;
int h[N],to[M],w[M],ne[M],tot;
void add(int a,int b,int c){
  to[++tot]=b;w[tot]=c;ne[tot]=h[a];h[a]=tot;
}
int d[N],vis[N];

void spfa(){
  for(int i=1;i<=n;i++) d[i]=inf; d[s]=0;
  queue<int>q; q.push(s); vis[s]=1; //在队中
  while(q.size()){
    int u=q.front(); q.pop(); vis[u]=0;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i];
      if(d[v]>d[u]+w[i]){ //松弛
        d[v]=d[u]+w[i];
        if(!vis[v]) q.push(v),vis[v]=1;
      }
    }
  }
}

Floyd(多源最短路)

复杂度O( $n^{3}$ )---（输出i~j的最短路径）

const int N=110;
int n,m,a,b,c;
int d[N][N];

void floyd(){
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

记得要处理重边

Johnson(多源最短路)

复杂度：O(nmlogm)

用虚拟点的思想用spfa和dij优化

int n,m,a,b,c;
struct edge{int v,w;};
vector<edge> e[N];
int vis[N],cnt[N];
long long h[N],d[N];

void spfa(){
    queue<int>q;
    memset(h,63,sizeof h);
    memset(vis,false,sizeof vis);
    h[0]=0,vis[0]=1;q.push(0);
    while(q.size()){
        int u=q.front(); q.pop();vis[u]=0;
        for(auto ed : e[u]){
            int v=ed.v,w=ed.w;
            if(h[v]>h[u]+w){
                h[v]=h[u]+w;
        cnt[v]=cnt[u]+1;
        if(cnt[v]>n){
          printf("-1\n");exit(0);
        }
                if(!vis[v])q.push(v),vis[v]=1;
            }
        }
    }
}
void dijkstra(int s){
    priority_queue<pair<long long,int>>q;
    for(int i=1;i<=n;i++)d[i]=INF;
    memset(vis,false,sizeof vis);
    d[s]=0; q.push({0,s});
    while(q.size()){
        int u=q.top().second;q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto ed : e[u]){
            int v=ed.v,w=ed.w;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!vis[v]) q.push({-d[v],v});
            }
        }
    }
}
int main(){
  cin>>n>>m;
  for(int i=0;i<m;i++)
    cin>>a>>b>>c, e[a].push_back({b,c});
    for(int i=1;i<=n;i++)
      e[0].push_back({i,0});//加虚拟边

    spfa();
    for(int u=1;u<=n;u++)
      for(auto &ed:e[u])
        ed.w+=h[u]-h[ed.v];//构造新边
    for(int i=1;i<=n;i++){
        dijkstra(i);
        long long ans=0;
        for(int j=1;j<=n;j++){
            if(d[j]==INF) ans+=(long long)j*INF;
            else ans+=(long long)j*(d[j]+h[j]-h[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Prim算法--最小生成树

int n,m,a,b,c,ans,cnt;
vector<pair<int,int>> e[N];
int d[N],vis[N];

bool prim(int s){
  for(int i=0;i<=n;i++) d[i]=inf; d[s]=0;
  for(int i=1;i<=n;i++){
    int u=0;
    for(int j=1;j<=n;j++)
      if(!vis[j]&&d[j]<d[u]) u=j;
    vis[u]=1; //选u
    ans+=d[u]; //树边和
    if(d[u]!=inf) cnt++; //点数
    for(auto x:e[u]){
      int v=x.first,w=x.second;
      if(d[v]>w) d[v]=w; //松弛
    }
  }
  return cnt==n;
}
int main(){
  cin>>n>>m;
  for(int i=0; i<m; i++){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
    e[b].push_back({a,c});
  }
  if(!prim(1)) puts("orz");
  else printf("%d\n",ans); 
}

数据结构

并查集（DSU）

struct DSU {
    std::vector<int> f, siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

朴素写法

int fa[N],siz[N]; //子树大小
int find(int x){
  return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unset(int x,int y){
  x=find(x),y=find(y);
  if(x==y)return;
  if(siz[x]<siz[y]) swap(x,y);
  fa[y]=x; siz[x]+=siz[y];
}

ST表

int n,m;//求区间最大值
int f[100005][22]; //f[i][k]区间起点为i,长度为2^k的最大
scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) scanf("%d",&f[i][0]);
  for(int k=1;k<=20;k++) //区间长度
    for(int i=1;i<=n-(1<<k)+1;i++) //区间起点
      f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);

  for(int i=1,a,b;i<=m;i++){
    scanf("%d%d",&a,&b);
    int k=log2(b-a+1); //区间长度的指数
    printf("%d\n",max(f[a][k],f[b-(1<<k)+1][k]));
  }

树状数组

jiangly版本

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    Fenwick(int n_ = 0) {
        init(n_);
    }//定义新数组
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    } //初始化
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }// 单点修改
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }//单点查询0~x的和
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }//区间查询
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }//查询数组中第k大的数
};

朴素版本

struct BIT{
  int s[N];
  void change(int x,int w){
    for(;x<=n;x+=x&-x) s[x]+=w;
  }
  int query(int x){
    int res=0;
    for(;x;x-=x&-x) res+=s[x];
    return res;
  }
};

线段树

线段树的学习——用于维护区间信息( logn )

基于二叉树建树

用以下方法定义父节点与子节点的关系:

    #define lc p << 1
    #define rc p << 1 | 1

设定 $w$ 为需要维护的数组定义：

struct  node {
    int l, r, sum;
}tr [N * 4];

进行建树用 $t r$ 来表示树建完后的状态

占用比一般在0.9左右，所以我们一般开线段树都是四倍的空间

建树

void build(int p, int l,int r) {
    tr [p] = { l,r,w [l] };
    if (l == r)return;
    int mid = l + r >> 1;
    build(lc, l, mid);
    build(rc, mid + 1, r);
    tr [p].sum = tr [lc].sum + tr [rc].sum;
}

点修改---复杂度为O(logn)

void update(int p, int x, int k) {//点修改
    if (tr[p].l == x && tr[p].r == x) {
        tr[p].sum += k;
        return;//叶子修改
    }
    int mid = tr[p].l + tr[p].r >> 1;
    if (x <= mid)update(lc, x, k);
    if (x > mid)update(rc, x, k);
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}

从根节点进入，递归查找叶子节点，修改叶子节点的值，从下到上更新统计值

区间查询

运用的是拆分和拼凑的思想

从根节点进入，递归进行以下操作:

若查询区间 [l, r] 完全覆盖当前节点区间，立即回溯，并返回该节点的sum值
若左子节点与[l, r]有重叠，则递归访问左子树
若右子节点与[l, r]有重叠，则递归访问右子树

int query(int p, int x, int y) {//区间查询
    if (x <= tr[p].l && tr[p].r <= y)
        return tr[p].sum;
    int mid = tr[p].l + tr[p].r >> 1;
    int sum = 0;
    if (x <= mid)sum += query(lc, x, y);
    if (y > mid)sum += query(rc, x, y);
    return sum;
}

线段树模板

区间求和

然后加上一些对懒的学习，可以封装一下做到下面这样的结构体封装：

struct SGT{
  #define lc u<<1
  #define rc u<<1|1
  struct sgt{ int l,r,sum,add; }tr[N*4];

  void pushup(int u){ //上传
    tr[u].sum=tr[lc].sum+tr[rc].sum;
  }
  void pushdown(int u){ //下传
    if(tr[u].add){
      tr[lc].sum+=tr[u].add*(tr[lc].r-tr[lc].l+1),
      tr[rc].sum+=tr[u].add*(tr[rc].r-tr[rc].l+1),
      tr[lc].add+=tr[u].add,
      tr[rc].add+=tr[u].add,
      tr[u].add=0;      
    }
  }
  void build(int u,int l,int r){ //建树
    tr[u]={l,r,w[l],0};
    if(l==r) return;
    int m=l+r>>1;
    build(lc,l,m);
    build(rc,m+1,r);
    pushup(u);
  }
  void change(int u,int x,int y,int k){ //区修
    if(x>tr[u].r || y<tr[u].l) return;
    if(x<=tr[u].l && tr[u].r<=y){
      tr[u].sum+=(tr[u].r-tr[u].l+1)*k;
      tr[u].add+=k;
      return;
    }
    pushdown(u);
    change(lc,x,y,k); 
    change(rc,x,y,k);
    pushup(u);
  }
  int query(int u,int x,int y){ //区查
    if(x>tr[u].r || y<tr[u].l) return 0;
    if(x<=tr[u].l && tr[u].r<=y) return tr[u].sum;
    pushdown(u);
    return query(lc,x,y)+query(rc,x,y);
  }
}S;

多功能线段树

然后在下面放一个多功能线段树便于其他变换的线段树理解

struct STG {
#define lc (u << 1)      // 左儿子索引
#define rc (u << 1 | 1)  // 右儿子索引
    struct Node {
        ll l, r, sum;
        ll min_val, max_val, add;
        Node(ll l = 0, ll r = 0, long long sum = 0, ll min_val = 0, ll max_val = 0, ll add = 0)
            : l(l), r(r), sum(sum), min_val(min_val), max_val(max_val), add(add) {}
    };
    vector<Node> tr; // 线段树数组
    vector<ll>& w;  // 对原始数组的引用
    STG(vector<ll>& nums) : w(nums) {
        ll n = w.size();
        tr.resize(n * 4); // 分配4倍空间
        build(1, 0, n - 1);
    }
    void pushup(ll u) { // 向上更新父节点信息（合并左右子树信息）
        tr[u].sum = tr[lc].sum + tr[rc].sum;
        tr[u].min_val = min(tr[lc].min_val, tr[rc].min_val);
        tr[u].max_val = max(tr[lc].max_val, tr[rc].max_val);
    }
    void pushdown(ll u) {// 向下传递懒惰标记
        if (tr[u].add != 0) { // 如果存在懒惰标记
            ll len_left = tr[lc].r - tr[lc].l + 1;  // 左子树区间长度
            ll len_right = tr[rc].r - tr[rc].l + 1; // 右子树区间长
            tr[lc].sum += (long long)tr[u].add * len_left;
            tr[lc].min_val += tr[u].add;
            tr[lc].max_val += tr[u].add;
            tr[lc].add += tr[u].add;
            // 更新右子树
            tr[rc].sum += (long long)tr[u].add * len_right;
            tr[rc].min_val += tr[u].add;
            tr[rc].max_val += tr[u].add;
            tr[rc].add += tr[u].add;
            tr[u].add = 0; // 清空当前节点的懒惰标记
        }
    }

    void build(ll u, ll l, ll r) {// 建树
        if (l == r) {
            tr[u] = Node(l, r, w[l], w[l], w[l], 0); // 叶子节点
            return;
        }
        tr[u].l = l;
        tr[u].r = r;
        ll mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        pushup(u);
    }
    void update(ll u, ll x, ll y, ll k) {
        if (x > tr[u].r || y < tr[u].l) return;
        if (x <= tr[u].l && tr[u].r <= y) {
            ll len = tr[u].r - tr[u].l + 1;
            tr[u].sum += (long long)k * len;
            tr[u].min_val += k;
            tr[u].max_val += k;
            tr[u].add += k;
            return;
        }
        pushdown(u); // 下传懒惰标记
        ll mid = (tr[u].l + tr[u].r) >> 1;
        if (x <= mid) update(lc, x, y, k);
        if (y > mid) update(rc, x, y, k);
        pushup(u); // 递归后更新当前节点
    }
    void query(ll u, ll x, ll y, long long& sum, ll& min_val, ll& max_val) {
        if (x > tr[u].r || y < tr[u].l) { // 无交集，返回不影响结果的值
            sum = 0;
            min_val = INT_MAX;
            max_val = INT_MIN;
            return;
        }
        if (x <= tr[u].l && tr[u].r <= y) { // 当前区间被完全包含
            sum = tr[u].sum;
            min_val = tr[u].min_val;
            max_val = tr[u].max_val;
            return;
        }
        pushdown(u); // 下传懒惰标记
        ll mid = (tr[u].l + tr[u].r) >> 1;
        ll sum_l = 0, sum_r = 0;
        ll min_l = INT_MAX, min_r = INT_MAX;
        ll max_l = INT_MIN, max_r = INT_MIN;
        if (x <= mid)
            query(lc, x, y, sum_l, min_l, max_l); // 查询左子树
        if (y > mid)
            query(rc, x, y, sum_r, min_r, max_r); // 查询右子树
        sum = sum_l + sum_r;
        min_val = min(min_l, min_r);
        max_val = max(max_l, max_r);
    }
    void change(ll l, ll r, ll k) {
        update(1, l, r, k);
    } // --- 对外的简化接口 ---
    ll query_sum(ll l, ll r) {
        ll sum, min_val, max_val;
        query(1, l, r, sum, min_val, max_val);
        return sum;
    }
    ll query_min(ll l, ll r) {
        ll sum, min_val, max_val;
        query(1, l, r, sum, min_val, max_val);
        return min_val;
    }

    ll query_max(ll l, ll r) {
        ll sum, min_val, max_val;
        query(1, l, r, sum, min_val, max_val);
        return max_val;
    }
};

题目大意：

解析：

题目大意：

解析：

题目大意：

解析：

题目大意：

解析：

杂项

基础数学

最小公倍数和最大公因数

快速幂

线性筛

求欧拉函数

求莫比乌斯函数

求约数个数

求组合数

当n，m< 100000时使用逆元预处理

当n，m<1e18时但是p<100000我们可以使用卢卡斯定理

字符串

KMP算法

Manecher

字典树

图论

DIJ（单源最短路）

SPFA(单源最短路判负环)

Floyd(多源最短路)

Johnson(多源最短路)

Prim算法--最小生成树

数据结构

并查集（DSU）

ST表

树状数组

jiangly版本

朴素版本

线段树

线段树的学习——用于维护区间信息( logn )

基于二叉树建树

建树

点修改---复杂度为O(logn)

区间查询

线段树模板

区间求和

多功能线段树

前言：

C：Annoying Game

D:Palindrome Flipping