本模板前前后后不断更新,未来还将会加入更多算法模板,敬请期待。

本模板借鉴/搬运/指导于诸位神犇,特此鸣谢:L@in 熊腾浩

基础算法

关同步

ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

二分

int l=0,r=MAX,mid,ans;
while(l<=r){
    mid=(l+r)/2;
    if(check(mid)){
        ans=mid;
        l=mid+1;
    }
    else r=mid-1;
}

离散化

int lsh[N];
for(int i=1;i<=n;i++) lsh[i]=a[i];
sort(lsh+1,lsh+n+1);
int SIZE=unique(lsh+1,lsh+n+1)-(lsh+1);  
for(int i=1;i<=n;i++){
    a[i]=upper_bound(lsh+1,lsh+SIZE+1,a[i])-(lsh+1);
}

模拟退火

int fans;
int ans=1e18;
int cal(int x){
    fans=0;
    //calculate a answer by x
    return fans;
}
void SA(){
    double T=1926087; //起始温度
    int x=0; //起始x值
    while(T>1e-14){ //终止温度
        int new_x=x-(rand()*2-RAND_MAX)*T;
        int new_ans=cal(new_x);
        int dE=new_ans-ans;
        if(dE<0){
            x=new_x;
            ans=new_ans;
        }
        else if(exp(-dE/T)*RAND_MAX>rand()){
            x=new_x;
        }
        T*=0.993;
    }
}

数学

快速幂

typedef long long ll;
ll qpow(ll a, ll n, ll mod){
    ll res=1;
    while(n){
        if(n&1) res=(res*a)%mod;
        n>>=1;
        a=(a*a)%mod;
    }
    return res;
}

最大公因数&最小公倍数

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

数据结构

扩展线段树(区间加 区间乘 区间赋值 区间最值)
点击查看经典线段树模板

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

const int inf = 1e16;
const int N = 1e5 + 7;
int n,m;
int a[N*4],sum[N*4],max_[N*4];
struct LazyTag{
    int add,mul,col;//三种懒标记
}tag[N*4];

void pushup(int x) { //上传标记
    sum[x] = sum[x<<1] + sum[x<<1|1];
    max_[x] = max(max_[x<<1],max_[x<<1|1]);
}
void build(int x,int l,int r) {//建树
    if(l == r){
        sum[x] = a[l];
        max_[x] = max(max_[x<<1],max_[x<<1|1]);
        return;
    }
    int mid = (l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void pushdown(int x,int l,int r) {//下放标记
    int ls = x<<1,rs = x<<1|1,mid = (l+r)>>1;
    if(tag[x].col != -1){//有赋值标记
        int c = tag[x].col;
        tag[ls].add = tag[rs].add = 0;
        tag[ls].mul = tag[rs].mul = 1;
        sum[ls] = c * (mid - l + 1);
        sum[rs] = c * (r - mid );
        tag[ls].col = tag[rs].col = c;
        max_[ls] = max_[rs] = c;
        tag[x].col = -1;
    }
    if(tag[x].mul != 1){ //有乘法标记
        int c = tag[x].mul;
        tag[ls].mul *= c;
        tag[rs].mul *= c;
        sum[ls] *= c;
        sum[rs] *= c;
        max_[ls] *= c;
        max_[rs] *= c;
        tag[ls].add *= c;
        tag[rs].add *= c;
        tag[x].mul = 1;
    }
    if(tag[x].add > 0){ //有加法标记
        int c = tag[x].add;
        tag[ls].add += c;
        tag[rs].add += c;
        sum[ls] += c * (mid - l + 1);
        sum[rs] += c * (r - mid);
        max_[ls] += c;
        max_[rs] += c;
        tag[x].add = 0;
    }
    return;
}
void updata_col(int x,int l,int r,int ll,int rr,int k) { //将[ll,rr]赋值为k
    if(r < ll || l > rr) return;
    if(l >= ll && r <= rr){
        sum[x] = k * (r - l + 1);
        max_[x] = k;
        tag[x].mul = 1;
        tag[x].add = 0;
        tag[x].col = k;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    updata_col(x<<1,l,mid,ll,rr,k);
    updata_col(x<<1|1,mid+1,r,ll,rr,k);
    pushup(x);
}

void updata_mul(int x,int l,int r,int ll,int rr,int k) { //将[ll,rr]乘以k
    if(r < ll || l > rr) return;
    if(l >= ll && r <= rr){
        sum[x] = sum[x] * k;
        max_[x] = max_[x] * k;
        tag[x].mul = tag[x].mul * k;
        tag[x].add = tag[x].add * k;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    updata_mul(x<<1,l,mid,ll,rr,k);
    updata_mul(x<<1|1,mid+1,r,ll,rr,k);
    pushup(x);
}
void updata_add(int x,int l,int r,int ll,int rr,int k) { //将[ll,rr]加上k
    if(r < ll || l > rr) return;
    if(l >= ll && r <= rr){
        sum[x] = sum[x] + k * (r - l + 1);
        max_[x] = max_[x] + k;
        tag[x].add = tag[x].add + k;
        return;
    }
    pushdown(x,l,r);
    int mid = (l+r)>>1;
    updata_add(x<<1,l,mid,ll,rr,k);
    updata_add(x<<1|1,mid+1,r,ll,rr,k);
    pushup(x);
}
int query(int x,int l,int r,int ll,int rr) {//查询区间和
    if(r < ll || l > rr) return 0;
    if(l >= ll && r <= rr){
        return sum[x];
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    return query(x<<1,l,mid,ll,rr)+query(x<<1|1,mid+1,r,ll,rr);
}

int query_mx(int x,int l,int r,int ll,int rr) {//查询区间最值
    if(r < ll || l > rr) return -inf;
    if(l >= ll && r <= rr){
        return max_[x];
    }
    pushdown(x,l,r);
    int mid=(l+r)>>1;
    return max(query_mx(x<<1,l,mid,ll,rr),query_mx(x<<1|1,mid+1,r,ll,rr));
}

void init() { //初始化
    cin>>n>>m;
    for(int i = 1;i <= 4 * n;i++) tag[i].mul = 1;
    for(int i = 1;i <= 4 * n;i++) tag[i].col = -1;
    for(int i = 1;i <= n;i++){
        cin>>a[i];
    }
    build(1,1,n);
}
分类: 模板

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注