板子（更新ing_牛客博客

优化

取消同步流

ios::sync_with_stdio(0);
cin.tie(0);

读入优化

朴素读入优化

int read() {
  int x = 0, w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x * w;
}

fread读入优化

inline char getcha(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int read(){
    int res=0;char ch=getcha();bool XX=false;
    for(;!isdigit(ch);ch=getcha())
      (ch=='-') && (XX=true);
    for(;isdigit(ch);ch=getcha())
      res=(res<<3)+(res<<1)+(ch^48);
    return XX?-res:res;
}

实数读入优化

inline double dbread(){
    double X=0,Y=1.0; int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
    ch=getchar();//读入小数点
    while(isdigit(ch)) X+=(Y/=10)*(ch^48),ch=getchar();
    return w?-X:X;
}

输出优化

朴素输出优化

void write(int x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}

write输出优化

char pbuf[100000],*pp=pbuf;
void push(const char c) {
    if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf;
    *pp++=c;
}
void write(int x){
    static int sta[35];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top) push(sta[--top]+'0');
}
//请大家在程序结束前加上一句fwrite(pbuf,1,pp-pbuf,stdout);pp=pbuf;
//防止出现没输出完成的类似错误

O2O3优化

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

离散化

int a[N],b[N],x[N*2],p[N*2]; //乘几具体看题目

int n;cin>>n;
for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    x[cnt++]=a[i];
    x[cnt++]=b[i];
}
sort(x,x+cnt);
cnt=unique(x,x+cnt)-x;
for(int i=0;i<n;i++){
    a[i]=lower_bound(x,x+cnt,a[i])-x;
    b[i]=lower_bound(x,x+cnt,b[i])-x;
}

数论模板

欧几里得算法（辗转相除法）

gcd(a,b)=gcd(b,a%b)

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

a,b的最小公倍数

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

扩展欧几里得算法

裴蜀定理：若 a,b 是整数,且 gcd(a,b)=d，那么对于任意的整数 x,y, ax+by 都一定是 d 的倍数，特别地，一定存在整数 x,y，使 ax+by=d 成立。

扩展欧几里德常用在求解模线性方程及方程组中。

https://www.luogu.com.cn/problem/P1082

#include <bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int gcd=exgcd(b,a%b,x,y),temp=x;
    x=y,y=temp-a/b*y;
    return gcd;
}

int main(){
    int a,b,x,y;
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b<<"\n";
    return 0;
}

快速幂（a^b % mod)

ll fpow(ll a,ll b,ll mod){
    if(mod==1) return 0;
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct node{
    ll mat[105][105];
};
int n;
node mul(node x,node y){
    node tmp;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            tmp.mat[i][j]=0;
            for(int k=0;k<n;k++){
                tmp.mat[i][j]+=(x.mat[i][k]*y.mat[k][j])%mod;
            }
            tmp.mat[i][j]%=mod;
        }
    }
    return tmp;
}
node matpow(node x,node y,ll num){
    while(num){
        if(num&1){
            y=mul(x,y);
        }
        x=mul(x,x);
        num=num>>1;
    }
    return y;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    node x,y;//x是系数矩阵,y是单位矩阵 
    ll k;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>x.mat[i][j];
            if(i==j) y.mat[i][j]=1;
        }
    }
    node c=matpow(x,y,k);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<c.mat[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

乘法逆元

快速幂逆元

https://www.acwing.com/problem/content/878/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod;
ll fpow(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main(){
    int n; cin>>n;
    while(n--){
        int a;
        cin>>a>>mod;
        if(a%mod==0) puts("impossible");
        else cout<<fpow(a,mod-2)<<"\n";
    }
    return 0;
}

线性递推求逆元

https://www.luogu.com.cn/problem/P3811

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+10;
ll n,mod,inv[N];
int main(){
    cin>>n>>mod;
    inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=(mod-(mod/i))*inv[mod%i]%mod;
    for(int i=1;i<=n;i++) cout<<inv[i]<<"\n";
    return 0;
}

分数取模(求单个)

https://ac.nowcoder.com/acm/contest/80/B

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
typedef long long ll;
ll fpow(ll a,ll b){
    if(mod==1) return 0;
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main() {
    ll n,m,fz,fm;
    cin>>n>>m;
    fz=n*n-m;fm=n*n;
    cout<<(fz%mod)*fpow(fm,mod-2)%mod<<"\n";
    return 0;
}

分数取模(存数组)（补

素数筛（补

筛法求积性函数

中国剩余定理

整除分块

数据结构

树状数组

单点修改，区间查询

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int q[N],t[N];
int n,m;

// 算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
inline int lowbit(int x){
    return x&(-x);
}

void add(int x,int v){    //在x位置加上v
    while(x<=n){
        t[x]+=v;
        x+=lowbit(x);
    }
}

//求前缀和
int getsum(int x){
    int res=0;
    while(x>0){
        res+=t[x];
        x-=lowbit(x);
    }
    return res;
}

int main(){
    int k,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        scanf("%d",&q[i]);
        add(i,q[i]);   //树状数组
    }

    for(int i=0;i<m;i++){
        scanf("%d%d%d",&k,&a,&b);
        if(k==2) printf("%d\n",getsum(b)-getsum(a-1));
        else if(k==1) add(a,b);
    }
    return 0;
}

区间修改，单点查询

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int q[N],d[N],tree[N],n,m;

inline int lowbit(int x){
    return x&(-x);
}

void add(int p,int x){
    for(int i=p;i<=n;i+=lowbit(i)) tree[i]+=x;
}

int getsum(int p){
    int ans=0;
    for(int i=p;i;i-=lowbit(i)) ans+=tree[i];
    return ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>q[i];
        d[i]=q[i]-q[i-1];
        add(i,d[i]);
    }
    for(int i=0;i<m;i++){
        int op,x,y,k;
        cin>>op;
        if(op==1) {
            cin>>x>>y>>k;
            add(x,k),add(y+1,-k);
        }
        else{
            cin>>x;
            cout<<getsum(x)<<"\n";
        }
    }
    return 0;
}

线段树

区间修改，区间查询

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll a[N];
ll tree[N<<2];
ll lazy[N<<2];

inline ll ls(ll x){return x<<1;}
inline ll rs(ll x){return x<<1|1;}

inline void pushup(ll u){
    tree[u]=tree[ls(u)]+tree[rs(u)];
}

inline void build(ll u,ll ul,ll ur){
    lazy[u]=0; 
    if(ul==ur){tree[u]=a[ul];return;}
    ll mid=(ul+ur)>>1;
    build(ls(u),ul,mid);
    build(rs(u),mid+1,ur);
    pushup(u);
}

inline void addlazy(ll u,ll ul,ll ur,ll v){
    lazy[u]+=v;
    tree[u]+=v*(ur-ul+1);
}

inline void pushdown(ll u,ll ul,ll ur){
    if(lazy[u]){
        ll mid=(ul+ur)>>1;
        addlazy(ls(u),ul,mid,lazy[u]);
        addlazy(rs(u),mid+1,ur,lazy[u]);
        lazy[u]=0;
    }
}

//区间修改
inline void update(ll l,ll r,ll u,ll ul,ll ur,ll v){
    if(l<=ul&&ur<=r){
        addlazy(u,ul,ur,v);
        return;
    }
    pushdown(u,ul,ur);
    ll mid=(ul+ur)>>1;
    if(l<=mid) update(l,r,ls(u),ul,mid,v);
    if(r>mid) update(l,r,rs(u),mid+1,ur,v);
    pushup(u);
} 

//区间查询
inline ll query(ll l,ll r,ll u,ll ul,ll ur){
    if(l<=ul&&ur<=r) return tree[u]; 
    pushdown(u,ul,ur);
    ll res=0;
    ll mid=(ul+ur)>>1;
    if(l<=mid) res+=query(l,r,ls(u),ul,mid);
    if(r>mid) res+=query(l,r,rs(u),mid+1,ur);
    return res;
}

int main(){
    ll n,m;cin>>n>>m;
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--){
        int t;scanf("%d",&t);
        ll l,r,v;
        if(t==1){
            scanf("%lld%lld%lld",&l,&r,&v);
            update(l,r,1,1,n,v);
        }
        else{
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(l,r,1,1,n));
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
ll q[N];
int p;
struct node{
    int l,r; //tree[i].l和tree[i].r分别表示这个点代表的线段的左右下标
    ll sum; //tree[i].sum表示这个节点表示的线段和
    ll addlazy,mullazy; //懒标记
}tree[N<<2];  //开四倍空间

inline void pushup(int u){        //更新函数
    tree[u].sum=(tree[u<<1].sum+tree[u<<1|1].sum)%p; //父节点的和等于两个子节点之和
}

inline void pushdown(int u){
    tree[u<<1].sum=((tree[u].mullazy*tree[u<<1].sum)%p+(tree[u].addlazy*(tree[u<<1].r-tree[u<<1].l+1))%p)%p;
    tree[u<<1|1].sum=((tree[u].mullazy*tree[u<<1|1].sum)%p+(tree[u].addlazy*(tree[u<<1|1].r-tree[u<<1|1].l+1))%p)%p;

    tree[u<<1].mullazy=(tree[u<<1].mullazy*tree[u].mullazy)%p;
    tree[u<<1|1].mullazy=(tree[u<<1|1].mullazy*tree[u].mullazy)%p;

    tree[u<<1].addlazy=((tree[u<<1].addlazy*tree[u].mullazy)%p+tree[u].addlazy)%p;
    tree[u<<1|1].addlazy=((tree[u<<1|1].addlazy*tree[u].mullazy)%p+tree[u].addlazy)%p;

    tree[u].mullazy=1;
    tree[u].addlazy=0;
}

//一个节点为x 它的父节点为x/2（x>>1） 左儿子2x(x<<1) 右儿子2x+1(x<<1|1)
inline void build(int u,int l,int r){
    tree[u].l=l;
    tree[u].r=r;
    tree[u].mullazy=1;
    if(l==r){     //左端点等于右端点，即为叶子节点，直接赋值即可
        tree[u].sum=q[l]%p;
        return;
    }

    int mid=(l+r)>>1;    //mid则为中间点，左儿子的结点区间为[l,mid],右儿子的结点区间为[m+1,r]
    build(u<<1,l,mid);    //递归构造左儿子结点
    build(u<<1|1,mid+1,r);    //递归构造右儿子结点
    pushup(u);    //更新父节点
}

inline void add(int u,int l,int r,ll v) {  //u为结点下标，[l,r]为修改区间，v为要加上的值
    if(l<=tree[u].l&&r>=tree[u].r){
        tree[u].sum=(tree[u].sum+((tree[u].r-tree[u].l+1)*v)%p)%p;
        tree[u].addlazy=(tree[u].addlazy+v)%p;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid) add(u<<1,l,r,v);
    if(r>mid) add(u<<1|1,l,r,v);
    pushup(u);
} 

inline void mul(int u,int l,int r,ll v) {  //u为结点下标，[l,r]为修改区间，v为要乘上的值
    if(l<=tree[u].l&&r>=tree[u].r){
        tree[u].sum=(tree[u].sum*v)%p;
        tree[u].mullazy=(tree[u].mullazy*v)%p;
        tree[u].addlazy=(tree[u].addlazy*v)%p;
        return;
    }
    pushdown(u);
    int mid=(tree[u].l+tree[u].r)>>1;
    if(l<=mid) mul(u<<1,l,r,v);
    if(r>mid) mul(u<<1|1,l,r,v);
    pushup(u);
} 

//区间查询
inline ll query(int u,int l,int r){    //u为结点下标, [l,r]即为要查询的区间
    if(tree[u].l>=l&&tree[u].r<=r)    //如果当前结点的区间包含于(?)要查询的区间内，则返回结点信息且不需要往下递归
        return tree[u].sum;
    ll sum=0;

    pushdown(u);

    int mid=(tree[u].l+tree[u].r)>>1;    //mid则为中间点，左儿子的结点区间为[l,mid],右儿子的结点区间为[mid+1,r]

    if(l<=mid)   //先找和左边无交集
        sum=(sum+query(u<<1,l,r))%p; //左儿子

    if(r>mid)   //再找和右边无交集
        sum=(sum+query(u<<1|1,l,r))%p; //加上右儿子

    return sum;    //返回当前结点得到的信息
}


int main(){
    int n,m;
    int t,x,y;
    ll k;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) scanf("%lld",&q[i]);

    build(1,1,n);

    for(int i=0;i<m;i++){
        scanf("%d",&t);
        if(t==1){
            scanf("%d%d%lld",&x,&y,&k);
            mul(1,x,y,k);
        }
        else if(t==2){
            scanf("%d%d%lld",&x,&y,&k);
            add(1,x,y,k);
        } 
        else if(t==3){
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}

维护区间最值操作与区间历史最值

1 l r k：对于所有的 $i\in[l,r]$ ，将 $A_i$ 加上 $k$ （ $k$ 可以为负数）。
2 l r v：对于所有的 $i\in[l,r]$ ，将 $A_i$ 变成 $\min(A_i,v)$ 。
3 l r：求 $\sum_{i=l}^{r}A_i$ 。
4 l r：对于所有的 $i\in[l,r]$ ，求 $A_i$ 的最大值。
5 l r：对于所有的 $i\in[l,r]$ ，求 $B_i$ 的最大值。

在每一次操作后，我们都进行一次更新，让 $B_i\gets\max(B_i,A_i)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10,INF=0x3f3f3f3f;

struct SegmentTree{
    struct Node{
        int l, r;
        int mx, mx_, se, cnt; ll sum;
        int add1, add1_, add2, add2_;
    } tr[N<<2];
    #define lc (o<<1)
    #define rc (o<<1|1)
    void pushup(int o){
        tr[o].sum=tr[lc].sum+tr[rc].sum;
        tr[o].mx_=max(tr[lc].mx_, tr[rc].mx_);
        if (tr[lc].mx==tr[rc].mx){
            tr[o].mx=tr[lc].mx;
            tr[o].se=max(tr[lc].se, tr[rc].se);
            tr[o].cnt=tr[lc].cnt+tr[rc].cnt;
        }
        else if (tr[lc].mx>tr[rc].mx){
            tr[o].mx=tr[lc].mx;
            tr[o].se=max(tr[lc].se, tr[rc].mx);
            tr[o].cnt=tr[lc].cnt;
        }
        else{
            tr[o].mx=tr[rc].mx;
            tr[o].se=max(tr[lc].mx, tr[rc].se);
            tr[o].cnt=tr[rc].cnt;
        }
    }
    void update(int o, int k1, int k1_, int k2, int k2_){
        tr[o].sum+=1ll*k1*tr[o].cnt+1ll*k2*(tr[o].r-tr[o].l+1-tr[o].cnt);
        tr[o].mx_=max(tr[o].mx_, tr[o].mx+k1_);
        tr[o].add1_=max(tr[o].add1_, tr[o].add1+k1_);
        tr[o].mx+=k1, tr[o].add1+=k1;
        tr[o].add2_=max(tr[o].add2_, tr[o].add2+k2_);
        if (tr[o].se!=-INF) tr[o].se+=k2;
        tr[o].add2+=k2;
    }
    void pushdown(int o){
        int tmp=max(tr[lc].mx, tr[rc].mx);
        if (tr[lc].mx==tmp)
            update(lc, tr[o].add1, tr[o].add1_, tr[o].add2, tr[o].add2_);
        else update(lc, tr[o].add2, tr[o].add2_, tr[o].add2, tr[o].add2_);
        if (tr[rc].mx==tmp)
            update(rc, tr[o].add1, tr[o].add1_, tr[o].add2, tr[o].add2_);
        else update(rc, tr[o].add2, tr[o].add2_, tr[o].add2, tr[o].add2_);
        tr[o].add1=tr[o].add1_=tr[o].add2=tr[o].add2_=0;
    }
    void build(int o, int l, int r, int* a){
        tr[o].l=l, tr[o].r=r;
        tr[o].add1=tr[o].add1_=tr[o].add2=tr[o].add2_=0;
        if (l==r){
            tr[o].sum=tr[o].mx_=tr[o].mx=a[l];
            tr[o].se=-INF, tr[o].cnt=1;
            return;
        }
        int mid=l+r>>1;
        build(lc, l, mid, a);
        build(rc, mid+1, r, a);
        pushup(o);
    }
    void modify1(int o, int l, int r, int k){
        if (tr[o].l>r||tr[o].r<l) return;
        if (l<=tr[o].l&&tr[o].r<=r)
            { update(o, k, k, k, k); return; }
        pushdown(o);
        modify1(lc, l, r, k), modify1(rc, l, r, k);
        pushup(o);
    }
    void modify2(int o, int l, int r, int k){
        if (tr[o].l>r||tr[o].r<l||k>=tr[o].mx) return;
        if (l<=tr[o].l&&tr[o].r<=r&&k>tr[o].se)
            { update(o, k-tr[o].mx, k-tr[o].mx, 0, 0); return; }
        pushdown(o);
        modify2(lc, l, r, k), modify2(rc, l, r, k);
        pushup(o);
    }
    ll query3(int o, int l, int r){
        if (tr[o].l>r||tr[o].r<l) return 0;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].sum;
        pushdown(o);
        return query3(lc, l, r)+query3(rc, l, r);
    }
    int query4(int o, int l, int r){
        if (tr[o].l>r||tr[o].r<l) return -INF;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].mx;
        pushdown(o);
        return max(query4(lc, l, r), query4(rc, l, r));
    }
    int query5(int o, int l, int r){
        if (tr[o].l>r||tr[o].r<l) return -INF;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].mx_;
        pushdown(o);
        return max(query5(lc, l, r), query5(rc, l, r));
    }
    #undef lc
    #undef rc
} sgt;
int a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sgt.build(1, 1, n, a);
    while (m--){
        int op, l, r, k;
        cin>>op;
        switch (op){
            case 1:
                cin>>l>>r>>k;
                sgt.modify1(1, l, r, k);
                break;
            case 2:
                cin>>l>>r>>k;
                sgt.modify2(1, l, r, k);
                break;
            case 3:
                cin>>l>>r;
                cout<<sgt.query3(1, l, r)<<"\n";
                break;
            case 4:
                cin>>l>>r;
                cout<<sgt.query4(1, l, r)<<"\n";
                break;
            case 5:
                cin>>l>>r;
                cout<<sgt.query5(1, l, r)<<"\n";
                break;
        }
    }
    return 0;
}

李超线段树

https://www.luogu.com.cn/problem/P4097

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> pdi;
const int N=1e5+10,mod1=39989,mod2=1e9,INF=0x3f3f3f3f;

int cnt,lastans;
double k[N],b[N];
int tag[N<<2];

inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline double calc(int i,int x){return b[i]+k[i]*x;}

void add(int x0,int y0,int x1,int y1) {
    cnt++;
    if(x0==x1){ //斜率不存在 
        k[cnt]=0;
        b[cnt]=max(y1,y0);
    }
    else{
        k[cnt]=1.0*(y1-y0)/(x1-x0);
        b[cnt]=y0-k[cnt]*x0; 
    } 
}

void update(int l,int r,int p,int pl,int pr,int x){
    int mid=(pl+pr)>>1;
    if(l<=pl&&pr<=r){
        if(pl==pr){
            if(calc(tag[p],pl)<calc(x,pl)) tag[p]=x;
            return;
        }
        if(!tag[p]){tag[p]=x;return;}
        else{
            double y1=calc(tag[p],mid),y2=calc(x,mid);
            if(k[tag[p]]<k[x]) {
                if(y1<=y2) {update(l,r,ls(p),pl,mid,tag[p]);tag[p]=x;} 
                else {update(l,r,rs(p),mid+1,pr,x);}
            }
            else if(k[tag[p]]>k[x]) {
                if(y1<=y2) {update(l,r,rs(p),mid+1,pr,tag[p]);tag[p]=x;}
                else {update(l,r,ls(p),pl,mid,x);}
            }
            else if(b[tag[p]]>b[x]){tag[p]=x;}
        } 
        return;
    }
    if(l<=mid) update(l,r,ls(p),pl,mid,x);
    if(r>mid) update(l,r,rs(p),mid+1,pr,x);
}

pdi query(int p,int l,int r,int x){
    if (r<x||x<l) return {0,0};
    if(l==r) {
        return {calc(tag[p],l),tag[p]};
    }
    double res=calc(tag[p],x);
    int ansid=tag[p];
    int mid=(l+r)>>1;
    if(x<=mid){
        auto temp=query(ls(p),l,mid,x);
        if(res<temp.first){
            res=temp.first;
            ansid=temp.second;
        }
        else if(res==temp.first) {
            ansid=min(ansid,temp.second);
        }
    }
    else {
        auto temp=query(rs(p),mid+1,r,x);
        if(res<temp.first){
            res=temp.first;
            ansid=temp.second;
        }
        else if(res==temp.first){
            ansid=min(ansid,temp.second);
        } 
    }
    return {res,ansid};
}

int main() {
    int n;cin>>n;
    while(n--){
        int op;cin>>op;
        if(op==1){
            int x0,y0,x1,y1;
            cin>>x0>>y0>>x1>>y1;
            x0=(x0+lastans-1)%mod1+1;
            x1=(x1+lastans-1)%mod1+1;
            y0=(y0+lastans-1)%mod2+1;
            y1=(y1+lastans-1)%mod2+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            add(x0,y0,x1,y1);
            update(x0,x1,1,1,mod1,cnt);
        }
        else {
            int x;cin>>x;
            x=(x+lastans-1)%mod1+1;
            lastans=query(1,1,mod1,x).second;
            cout<<lastans<<"\n";
        }
    }
    return 0;
}

扫描线

矩形面积并

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m;
int y[N<<1];

struct Segment{
    int x;
    int y1,y2;
    int state;//是左边还是右边
    bool operator< (const Segment &t)const{
        return x<t.x;
    }
}seg[N<<1];

struct node{
    int l,r;
    int cover;//当前区间覆盖次数
    ll len;//至少被覆盖1次的区间长度
}tree[N<<4];

inline void pushup(int u){
    if(tree[u].cover) tree[u].len=tree[u].r-tree[u].l;
    else tree[u].len=tree[u<<1].len+tree[u<<1|1].len;
}

void build(int u,int l,int r){
    tree[u].l=y[l],tree[u].r=y[r];
    if(r-l<=1) return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid),build(u<<1|1,mid,r);
}

void modify(int u,int l,int r,int k){
    int x=tree[u].l,y=tree[u].r;
    if(x>=l&&y<=r){
        tree[u].cover+=k;
        pushup(u);
    }
    else{
        if(l<tree[u<<1].r) modify(u<<1,l,r,k); 
        if(r>tree[u<<1|1].l) modify(u<<1|1,l,r,k);
        pushup(u);
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        y[i]=y1,y[n+i]=y2;
        seg[m++]={x1,y1,y2,1};
        seg[m++]={x2,y1,y2,-1};
    }
    sort(y+1,y+m+1);
    sort(seg,seg+m);

    build(1,1,m);

    ll ans=0;
    modify(1,seg[0].y1,seg[0].y2,seg[0].state);
    for(int i=1;i<m;i++){
        ans+=tree[1].len*(seg[i].x-seg[i-1].x);
        modify(1,seg[i].y1,seg[i].y2,seg[i].state);
    }
    cout<<ans<<"\n";
    return 0;
}

矩形周长并

#include<bits/stdc++.h>
using namespace std;
int ls(int x){ return x<<1;  }   
int rs(int x){ return x<<1|1;}  
const int MAXN = 200005;
struct ScanLine {
    int l, r, h, inout;  //inout=1 下边, inout=-1 上边
    ScanLine() {}
    ScanLine(int a, int b, int c, int d) :l(a), r(b), h(c), inout(d) {}
}line[MAXN];
bool cmp(ScanLine &a, ScanLine &b) { 
    if(a.h==b.h) return a.inout>b.inout;
    return a.h<b.h; 
}   //y坐标排序

bool lbd[MAXN << 2], rbd[MAXN << 2];//标记这个结点的左右两个端点是否被覆盖（0表示没有，1表示有）
int num[MAXN << 2];    //这个区间有多少条独立的边
int Tag[MAXN << 2];    //标记这个结点是否有效 
int length[MAXN << 2]; //这个区间的有效宽度
void pushup(int p, int pl, int pr) {
    if (Tag[p]) {                 //结点的Tag为正，这个线段对计算宽度有效  
        lbd[p] = rbd[p] = 1;
        length[p] = pr - pl + 1;
        num[p] = 1;               //每条边有两个端点
    }
    else if (pl == pr) length[p]=num[p]=lbd[p]=rbd[p]=0;//叶子结点 
    else {     
        lbd[p] = lbd[ls(p)];      // 和左儿子共左端点
        rbd[p] = rbd[rs(p)];      //和右儿子共右端点
        length[p] = length[ls(p)] + length[rs(p)];
        num[p] = num[ls(p)] + num[rs(p)];
        if (lbd[rs(p)] && rbd[ls(p)]) num[p] -= 1;   //合并边
    }
}
void update(int L, int R, int io, int p, int pl, int pr) {
    if(L<=pl && pr<=R){    //完全覆盖
        Tag[p] += io;
        pushup(p, pl, pr);
        return;
    }
    int mid  = (pl + pr) >> 1;
    if (L<= mid) update(L, R, io, ls(p), pl, mid);
    if (mid < R) update(L, R, io, rs(p), mid+1, pr);
    pushup(p, pl, pr);
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        int cnt  = 0;
        int lbd = 10000, rbd = -10000;
        for (int i = 0; i < n; i++) {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);   //输入矩形
            lbd = min(lbd, x1);                      //横线最小x坐标
            rbd = max(rbd, x2);                      //横线最大x坐标
            line[++cnt] = ScanLine(x1, x2, y1, 1);   //给入边赋值
            line[++cnt] = ScanLine(x1, x2, y2, -1);  //给出边赋值
        }
        sort(line+1, line + cnt+1, cmp);           //排序。数据小，不用离散化 
        int ans = 0, last = 0;                     //last：上一次总区间被覆盖长度
        for (int i = 1; i <= cnt ; i++){           //扫描所有入边和出边
            if (line[i].l < line[i].r) 
                update(line[i].l, line[i].r-1, line[i].inout, 1, lbd, rbd-1);
            ans += num[1]*2 * (line[i + 1].h - line[i].h);  //竖线
            ans += abs(length[1] - last);            //横线
            last = length[1];                 
        }
        printf("%d\n", ans);
    }
    return 0;
}

可持久化线段树(主席树)

//区间内的第 k 小值
#include <bits/stdc++.h>
using namespace std ;
const int N = 200010;
int cnt = 0;        //用cnt标记可以使用的新结点
int a[N], b[N], root[N];
//a[]是原数组,b[]是排序后数组,root[i]记录第i棵线段树的根节点编号

struct node {
    int L, R, sum;  //L左儿子, R右儿子，sum[i]是结点i的权值
} tree[N<<5];    //需要开 nlogn空间 

int build(int pl, int pr) {
    int rt = ++ cnt;              //cnt为当前节点编号
    tree[rt].sum = 0;
    int mid=(pl+pr)>>1;
    if (pl < pr) {
        tree[rt].L = build(pl, mid);
        tree[rt].R = build(mid+1, pr);
    }
    return rt;  //返回当前节点的编号
}
int update(int pre, int pl, int pr, int x) {  //建一棵只有logn个结点的新线段树
    int rt = ++cnt;          //新的结点，下面动态开点
    tree[rt].L = tree[pre].L;//该结点的左右儿子初始化为前一棵树相同位置结点的左右儿子
    tree[rt].R = tree[pre].R;
    tree[rt].sum = tree[pre].sum + 1;  //插了1个数，在前一棵树的相同结点加1
    int mid = (pl+pr)>>1;
    if (pl < pr) {          //从根结点往下建logn个结点
        if (x <= mid)       //x出现在左子树，修改左子树
            tree[rt].L = update(tree[pre].L, pl, mid, x);
        else                //x出现在右子树，修改右子树
            tree[rt].R = update(tree[pre].R, mid+1, pr, x);
    }
    return rt;              //返回当前分配使用的新结点的编号
}

int query(int u, int v, int pl, int pr, int k) {   //查询区间[u,v]第k小
    if (pl == pr) return pl;  //到达叶子结点，找到第k小，pl是节点编号，答案是b[pl]
    int x = tree[tree[v].L].sum - tree[tree[u].L].sum;   //线段树相减
    int mid = (pl+pr)>>1;
    if (x >= k)     //左儿子数字大于等于k时，说明第k小的数字在左子树
        return query(tree[u].L, tree[v].L, pl, mid, k);
    else            //否则在右子树找第k-x小的数字
        return query(tree[u].R, tree[v].R, mid+1, pr, k-x);
}

int main() {
    int n, m;cin>>n>>m;
    for (int i = 1; i <= n; i ++) {
        cin>>a[i];
        b[i] = a[i];
    }
    sort(b+1, b+1+n);
    int size = unique(b+1, b+1+n)-b-1;
    for (int i = 1; i <= n; i ++) {
        int x = lower_bound(b+1, b+1+size, a[i]) - b;
        root[i] = update(root[i-1], 1, size, x);
    }
    while (m--) {
        int x, y, k;cin>>x>>y>>k;
        int t = query(root[x-1], root[y], 1, size, k);
        //第y棵线段树减第x-1棵线段树，就是区间[x,y]的线段树
        cout<<b[t]<<"\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll;
const int N = 1e5+10;
int cas,cnt;
ll a[N];
int root[N];
int n,m;

struct node {
    int L, R;
    ll lazy,sum;
} tree[N<<5];    //需要开 nlogn空间 

void pushup(int u){
    tree[u].sum=tree[tree[u].L].sum+tree[tree[u].R].sum;
}

int build(int pl, int pr) {
    int rt = ++ cnt;              //cnt为当前节点编号
    tree[rt].L=tree[rt].R=tree[rt].lazy=tree[rt].sum=0;
    if(pl==pr){
        tree[rt].sum=a[pl];
        return rt;
    }
    int mid=(pl+pr)>>1;
    tree[rt].L = build(pl, mid);
    tree[rt].R = build(mid+1, pr);
    pushup(rt);
    return rt;  //返回当前节点的编号
}

int update(int pre, int pl, int pr, int l, int r, ll v) {  //建一棵只有logn个结点的新线段树
    int rt = ++cnt;
    tree[rt] = tree[pre];
    tree[rt].sum+=v*(r-l+1);
    if(l==pl&&r==pr){
        tree[rt].lazy += v;
        return rt;
    }
    int mid=(pl+pr)>>1;
    if(r<=mid) tree[rt].L = update(tree[pre].L,pl,mid,l,r,v);
    else if(l>mid) tree[rt].R = update(tree[pre].R,mid+1,pr,l,r,v);
    else{
        tree[rt].L = update(tree[pre].L,pl,mid,l,mid,v);
        tree[rt].R = update(tree[pre].R,mid+1,pr,mid+1,r,v);
    }
//    pushup(rt);
    return rt;              //返回当前分配使用的新结点的编号
}

//区间查询
ll query(int rt,int pl,int pr,int l,int r){
    if(pl>=l&&pr<=r) return tree[rt].sum;
    int mid=(pl+pr)>>1;
    ll res=tree[rt].lazy*(r-l+1);
    if(r<=mid) res+=query(tree[rt].L,pl,mid,l,r);
    else if(l>mid) res+=query(tree[rt].R,mid+1,pr,l,r);
    else{
        res+=query(tree[rt].L,pl,mid,l,mid);
        res+=query(tree[rt].R,mid+1,pr,mid+1,r);
    }
    return res;    //返回当前结点得到的信息
}

void solve(){
    if(cas++) cout<<"\n";
    cnt=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    root[0]=build(1,n);
    int time=0;
    while(m--){
        char op;cin>>op;
        if(op=='C'){
            int l,r;ll d;cin>>l>>r>>d;
            time++;
            root[time]=update(root[time-1],1,n,l,r,d);
        }
        else if(op=='Q'){
            int l,r;cin>>l>>r;
            cout<<query(root[time],1,n,l,r)<<"\n";
        }
        else if(op=='H'){
            int l,r,t;cin>>l>>r>>t;
            cout<<query(root[t],1,n,l,r)<<"\n";
        }
        else{
            int t;cin>>t;
            time=t;
        }
    }
}

int main() {
    while(cin>>n>>m)
    solve();
    return 0;
}

珂朵莉树(ODT)

推平一段区间

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;

struct node{
    int l,r;
    mutable ll v;
    node(int L,int R=-1,ll V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const{
        return l < o.l;
    }
};
set<node> s;
int n,m;
ll seed,vmax;
ll a[N];

ll fpow(ll a,ll b,ll mod){
    if(mod==1) return 0;
    ll ans=1%mod;
    a%=mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

set<node>::iterator split(int pos){
    auto it=s.lower_bound(node(pos));
    if(it!=s.end() && it->l==pos) return it;
    --it;
    int L=it->l,R=it->r;
    ll V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

//推平
void assign(int l, int r, ll val){
    auto itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}

//区间加 
void add(int l,int r,ll val){
    auto itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl) itl->v+=val;
}

//区间第k小
ll _rank(int l,int r,int k){
    vector<pair<ll,int> >vp;
    auto itr=split(r+1),itl=split(l);
    vp.clear();
    for(;itl!=itr;++itl) vp.push_back({itl->v,itl->r-itl->l+1});
    sort(vp.begin(),vp.end());
    for(auto i:vp){
        k-=i.second;
        if(k<=0) return i.first;
    }
    return -1;
}

//区间幂次和
ll sum(int l,int r,ll ex,ll mod){
    auto itr=split(r+1),itl=split(l);
    ll res=0;
    for(;itl!=itr;++itl) 
        res=(res+(ll)(itl->r - itl->l + 1)*fpow(itl->v,ex,mod))%mod;
    return res;
}

ll rnd(){
    ll ret=seed;
    seed=(seed*7+13)%1000000007;
    return ret;
}

int main(){
    cin>>n>>m>>seed>>vmax;
    for(int i=1;i<=n;i++){
        a[i]=(rnd()%vmax)+1;
        s.insert(node(i,i,a[i]));
    }
    for(int i=1;i<=m;i++){
        int op=(rnd()%4)+1;
        int l=(rnd()%n)+1;
        int r=(rnd()%n)+1;
        if(l>r) swap(l,r);
        ll x,y;
        if(op==3) x=(rnd()%(r-l+1))+1;
        else x=(rnd()%vmax)+1;
        if(op==4) y=(rnd()%vmax)+1;

        if(op==1) add(l,r,x);
        else if(op==2) assign(l,r,x);
        else if(op==3) cout<<_rank(l,r,x)<<"\n";
        else cout<<sum(l,r,x,y)<<"\n";
    }
    return 0;
}

图论模板

最近公共祖先(LCA)

https://www.luogu.com.cn/problem/P3379

#include <bits/stdc++.h>
using namespace std;
const int N=500010;

int n,m,root; 
vector<int> g[N];
int depth[N],fa[N][20],lg[N];

void init(){
    //log2(i)+1
    for(int i=1;i<=n;i++){
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
}

void dfs(int u,int father){
    depth[u]=depth[father]+1;
    fa[u][0]=father;
    // 2^i祖先为2^i-1级祖先的2^i-1级祖先
    for(int i=1;(1<<i)<=depth[u];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int v:g[u]){
        if(v==father) continue;
        dfs(v,u);
    }
}

int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    while(depth[a]>depth[b]){
        a=fa[a][lg[depth[a]-depth[b]]-1];
    }
    if(a==b) return a;
    for(int i=lg[depth[a]];i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}

int main(){
    cin>>n>>m>>root;
    init();
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(root,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<"\n";
    }
    return 0;
}

最小生成树(MST)

Borůvka (Sollin) 算法

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MaxN = 5000 + 5, MaxM = 200000 + 5;

int N, M;
int U[MaxM], V[MaxM], W[MaxM];
bool used[MaxM];
int par[MaxN], Best[MaxN];

void init() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i)
        scanf("%d %d %d", &U[i], &V[i], &W[i]);
}

void init_dsu() {
    for (int i = 1; i <= N; ++i)
        par[i] = i;
}

int get_par(int x) {
    if (x == par[x]) return x;
    else return par[x] = get_par(par[x]);
}

inline bool Better(int x, int y) {
    if (y == 0) return true;
    if (W[x] != W[y]) return W[x] < W[y];
    return x < y;
}

void Boruvka() {
    init_dsu();

    int merged = 0, sum = 0;

    bool update = true;
    while (update) {
        update = false;
        memset(Best, 0, sizeof Best);

        for (int i = 1; i <= M; ++i) {
            if (used[i] == true) continue;
            int p = get_par(U[i]), q = get_par(V[i]);
            if (p == q) continue;

            if (Better(i, Best[p]) == true) Best[p] = i;
            if (Better(i, Best[q]) == true) Best[q] = i;
        }

        for (int i = 1; i <= N; ++i)
            if (Best[i] != 0 && used[Best[i]] == false) {
                update = true;
                merged++; sum += W[Best[i]];
                used[Best[i]] = true;
                par[get_par(U[Best[i]])] = get_par(V[Best[i]]);
            }
    }

    if (merged == N - 1) printf("%d\n", sum);
    else puts("orz");
}

int main() {
    init();
    Boruvka();
    return 0;
}

字符串

Trie树(字典树)

https://www.acwing.com/problem/content/837/

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

struct Trie {
    int nex[100010][26], cnt;
    int exist[100010];  // 该结点结尾的字符串是否存在

    void insert(string s, int l) {  // 插入字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
            p = nex[p][c];
        }
        exist[p] ++;
    }
    int find(string s, int l) {  // 查找字符串
        int p = 0;
        for (int i = 0; i < l; i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
        return exist[p];
    }
} t;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    char c;
    string s;
    while(n--) {
        cin>>c>>s;
        if(c=='I') t.insert(s,s.length());
        else cout<<t.find(s,s.length())<<"\n";
    } 
    return 0;
}

01Trie

struct Trie {
    int nex[N*32][2],cnt=0;

    void insert(int x) { 
        int p = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt; 
            p = nex[p][c];
        }
    }
    int find(int x) {
        int p = 0,res = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if(nex[p][c^1]) p=nex[p][c^1],res|=(1<<i);
            else p=nex[p][c];
        }
        return res;
    }
} t;

字符串哈希

https://www.acwing.com/problem/content/description/843/

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull P = 131;
const ull N = 1e5+10;
ull powP[N],H[N];
int n,m;
char str[N];

void init(){
    powP[0]=1;
    for(int i=1;i<=n;i++){
        powP[i]=powP[i-1]*P;
    }
}

void calH(ull H[],char str[]){
    H[0]=str[0];
    for(int i=1;i<=n;i++){
        H[i]=H[i-1]*P+str[i];
    }
}

ull get(int l,int r){
    return H[r]-H[l-1]*powP[r-l+1];
}

int main(){
    cin>>n>>m;
    cin>>str+1;
    init();
    calH(H,str);
    while(m--){
        int l1,l2,r1,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

KMP算法

https://www.acwing.com/problem/content/description/833/

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int ne[N];

void getNext(string s,int len){
    int j=-1;
    ne[0]=-1;
    for(int i=1;i<len;i++){
        while(j!=-1&&s[i]!=s[j+1]){
            j=ne[j];
        }
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }
}

int KMP(string text,string pattern){
    int n=text.length(),m=pattern.length();
    getNext(pattern,m);
    int ans=0,j=-1;
    for(int i=0;i<n;i++){
        while(j!=-1&&text[i]!=pattern[j+1]){
            j=ne[j];
        }
        if(text[i]==pattern[j+1]) j++;
        if(j==m-1) ans++,j=ne[j],printf("%d ", i-m+1);
    }
    return ans;
}

int main(){
    int n,m;
    string s1,s2;
    cin>>n>>s1>>m>>s2;
    getNext(s1,n);
    getNext(s2,m);
    KMP(s2,s1);
    return 0;
}

Manacher(马拉车)算法

最长回文子串 https://www.acwing.com/problem/content/1526/

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

int Manacher(string s){
    string str="@#";
    for(int i=0;i<s.length();i++) str+=s[i],str+='#';
    vector<int> p(str.length(),0);
    /*
    mx表示某个回文串延伸在最右端半径的下标
    id表示这个回文子串最中间位置下标
    reslen表示对应在s中的最大子回文串的半径
    rescenter表示最大子回文串的中间位置
    */
    int mx=0,id=0,reslen=0,rescenter=0;
    for(int i=1;i<str.length();i++){
        p[i] = mx>i ? min(p[2*id-i],mx-i):1;
        while(str[i+p[i]]==str[i-p[i]]) p[i]++;
        if(mx<i+p[i]) mx=i+p[i],id=i;
        if(reslen<p[i]) reslen=p[i],rescenter=i;
    }
    return reslen-1;
} 

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    string s;getline(cin,s);
    cout<<Manacher(s)<<"\n"; 
    return 0;
}

后缀数组(SA)+++

https://www.luogu.com.cn/problem/P3809

https://www.acwing.com/problem/content/description/142/

后缀自动机 (SAM)+++

AC 自动机+++

动态规划

背包DP

01背包

int v,w; //v体积,w价值
int f[N];

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v,&w);
        for(int j=m;j>=v;j--){
            f[j]=max(f[j], f[j-v]+w);
        }
    }
    cout<<f[m]<<"\n";
}

完全背包

int v,w; //v体积,w价值
int f[N];

void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&v,&w);
        for(int j=v;j<=m;j++){
            f[j]=max(f[j],f[j-v]+w);
        }
    }
    cout<<f[m]<<"\n";
}

多重背包

$O(nV\sum_{i=1}^ns_i)$

int v,w,s; //v体积 w价值 s数量
int f[N];

void solve(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        for(int j=m;j>=v;j--){
            for(int k=1;k<=s&&k*v<=j;k++){
                f[j]=max(f[j],f[j-k*v]+w*k);
            }
        }
    }
    cout<<f[m]<<"\n";
}

多重背包（二进制优化）

$O(nV\sum_{i=1}^nlog_2s_i)$

int v,w,s;
int dp[N];
vector<pii> good;

void solve() {
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++){
        cin>>v>>w>>s;
        for(int k=1;k<=s;k<<=1){
            s-=k;
            good.push_back({v*k,w*k});
        }
        if(s>0) good.push_back({v*s,w*s});    
    }
    for(auto t:good) {
        for(int j=V; j>=t.X; j--) {
            dp[j]=max(dp[j],dp[j-t.X]+t.Y);
        }
    }
    cout<<dp[V]<<"\n";
}

多重背包（单调队列优化）

$O(nV)$

int v[N],w[N],s[N];//体积、价值和数量
int f[N],g[N];//g[]为f[i-1][],f[]为f[i][]

void solve(){
    int n,V;cin>>n>>V;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++) {
        memcpy(g,f,sizeof f);
        for(int j=0;j<v[i];j++){ //枚举余数 
            deque<int> q;
            for (int k=j;k<=V;k+=v[i]){
                f[k]=g[k];
                if(!q.empty()&&k-s[i]*v[i]>q.front()){
                    q.pop_front();
                }
                if(!q.empty()){
                    f[k]=max(f[k],g[q.front()]+(k-q.front())/v[i]*w[i]);
                }
                while(!q.empty()&&g[q.back()]-(q.back()-j)/v[i]*w[i]<=g[k]-(k-j)/v[i]*w[i]){
                    q.pop_back();
                }
                q.push_back(k);
            }
        }
    }
    cout<<f[V]<<"\n";
}

混合背包

$si=−1$ 表示第 $i$ 种物品只能用1次；
$si=0$ 表示第 $i$ 种物品可以用无限次；
$si>0$ 表示第 $i$ 种物品可以使用 $si$ 次；

int v[N],w[N],s[N],dp[N];
struct good{
    int kind;
    int v,w;
};
vector<good> g;

void solve() {
    int n,V;
    cin>>n>>V;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++){
        if(s[i]==-1||s[i]==0) g.push_back({s[i],v[i],w[i]});
        else{
            for(int k=1;k<=s[i];k<<=1){
                s[i]-=k;
                g.push_back({-1,v[i]*k,w[i]*k});
            }
            if(s[i]>0) g.push_back({-1,v[i]*s[i],w[i]*s[i]});
        }
    }
    for(auto t:g){
        if(t.kind==-1){
            for(int j=V;j>=t.v;j--){
                dp[j]=max(dp[j],dp[j-t.v]+t.w);
            }
        }
        else{
            for(int j=t.v;j<=V;j++){
                dp[j]=max(dp[j],dp[j-t.v]+t.w);
            }
        }    
    }
    cout<<dp[V]<<"\n";
}

二维费用的背包

int dp[N][N];

void solve(){
    int n,V,M;cin>>n>>V>>M;
    for(int i=1;i<=n;i++){
        int v,m,w;cin>>v>>m>>w;
        for(int j=V;j>=v;j--){
            for(int k=M;k>=m;k--){
                dp[j][k]=max(dp[j][k],dp[j-v][k-m]+w);
            }
        }
    }
    cout<<dp[V][M]<<"\n";
}

分组背包

int dp[N],v[N],w[N];
void solve(){
    int n,V;cin>>n>>V;
    for(int i=1;i<=n;i++){  //循环每一组
        int s;cin>>s;
        for(int j=1;j<=s;j++) cin>>v[j]>>w[j];
        for(int j=V;j>=0;j--){  //循环背包容量
            for(int k=1;k<=s;k++){  //循环该组的每一个物品
                if(j>=v[k]) dp[j]=max(dp[j],dp[j-v[k]]+w[k]); 
            }
        }
    }
    cout<<dp[V]<<"\n";
}

有依赖的背包

int n,m,root;
int v[N],w[N],dp[N][N];
vector<int> g[N];

void dfs(int u){
    for(int i=v[u];i<=m;i++) dp[u][i]=w[u];
    for(int x:g[u]){
        dfs(x);
        for(int j=m;j>=v[u];j--){
            for(int k=0;k<=j-v[u];k++){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[x][k]);
            }
        }
    }
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int fa;
        cin>>v[i]>>w[i]>>fa;
        if(~fa) g[fa].push_back(i);
        else root=i;
    }
    dfs(root);
    cout<<dp[root][m]<<"\n";
}

背包问题求最大价值的方案数

int f[N];
ll cnt[N];

void solve(){
    int n,m;cin>>n>>m;
    for(int i=0;i<=m;i++) cnt[i]=1;
    for(int i=1;i<=n;i++){
        int v,w;cin>>v>>w;
        for(int j=m;j>=v;j--){
            int value=f[j-v]+w;
            if(value>f[j]){
                f[j]=value;
                cnt[j]=cnt[j-v];
            }
            else if(value==f[j]){
                cnt[j]+=cnt[j-v];
                cnt[j]%=mod;
            }
        }
    } 
    cout<<cnt[m]<<"\n";
}

背包问题求最大价值字典序最小的具体方案

int n,m;
int v[N],w[N],f[N][N];

void print(int i,int j){
    if(i==n+1) return;
    if(j>=v[i]&&f[i][j]==f[i+1][j-v[i]]+w[i]) {
        cout<<i<<" ";
        print(i+1,j-v[i]);
    }
    else print(i+1,j);
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=n;i>=1;i--){
        for(int j=0;j<=m;j++){
            if(j>=v[i]) f[i][j]=max(f[i+1][j],f[i+1][j-v[i]]+w[i]);
            else f[i][j]=f[i+1][j];
        }
    }
    print(1,m);
}