优化

取消同步流

```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;
}```

```inline char getcha(){
static char buf[100000],*p1=buf,*p2=buf;
}
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;
}```

扩展欧几里得算法

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);
}

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]);
}

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));
}
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);
}

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];
}
for(int i=0;i<m;i++){
int op,x,y,k;
cin>>op;
if(op==1) {
cin>>x>>y>>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;
lazy[u]=0;
}
}

//区间修改
inline void update(ll l,ll r,ll u,ll ul,ll ur,ll v){
if(l<=ul&&ur<=r){
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表示这个节点表示的线段和
}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].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].mullazy=1;
}

//一个节点为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;
return;
}
pushdown(u);
int mid=(tree[u].l+tree[u].r)>>1;
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;
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);
}
else if(t==3){
scanf("%d%d",&x,&y);
printf("%lld\n",query(1,x,y));
}
}
return 0;
}```

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

• `1 l r k`：对于所有的 ，将 加上 可以为负数）。
• `2 l r v`：对于所有的 ，将 变成
• `3 l r`：求
• `4 l r`：对于所有的 ，求 的最大值。
• `5 l r`：对于所有的 ，求 的最大值。

```#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;
} 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_);
if (tr[o].se!=-INF) tr[o].se+=k2;
}
void pushdown(int o){
int tmp=max(tr[lc].mx, tr[rc].mx);
if (tr[lc].mx==tmp)
if (tr[rc].mx==tmp)
}
void build(int o, int l, int r, int* a){
tr[o].l=l, tr[o].r=r;
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);
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));
}

//区间加
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;

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(马拉车)算法

```#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/

动态规划

背包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";
}```

多重背包

```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";
}```

多重背包（二进制优化）

```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";
}```

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

```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";
}```

混合背包

• 表示第 种物品只能用1次；
• 表示第 种物品可以用无限次；
• 表示第 种物品可以使用 次；
```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);
}```

2022-12-11 20:35

2022-12-28 17:14

2022-12-26 18:53

2022-12-29 13:09
Durham University_2022

2022-12-19 15:48

2022-12-28 10:01

2022-12-23 17:45

02-02 11:38

2022-12-26 18:01

2022-12-28 02:13

2 收藏 评论