sys_failure's 板子

[TOC]

动态规划

背包DP

二维费用背包

c++

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
int n,M,T;
int f[205][205];

void slv(){
	cin>>n>>M>>T;
	for(int i=1;i<=n;i++){
		int mi,ti;
		cin>>mi>>ti;
		for(int j=M;j>=mi;j--){
			for(int k=T;k>=ti;k--){
				f[j][k]=max(f[j][k],f[j-mi][k-ti]+1);
			}
		}
	}
	cout<<f[M][T]<<"\n";
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	slv();

	return 0;
}

有依赖的背包

c++

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=35000,M=65;
int n,m;
int v[M][3],p[M][3];
int f[N];

void slv(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int _v,_p,_q;
		cin>>_v>>_p>>_q;
		if(!_q){
			v[i][0]=_v;
			p[i][0]=_p;
		}else{
			if(v[_q][1]==0){
				v[_q][1]=_v;
				p[_q][1]=_p;
			}else{
				v[_q][2]=_v;
				p[_q][2]=_p;
			}
		}
	}		
	for(int i=1;i<=m;i++){
		if(!v[i][0])continue;
		for(int j=n;j>=0;j--){
			auto vpp=[v,p,i](int x){return v[i][x]*p[i][x];};
			auto cost2=[v,p,i](int x,int y){return v[i][x]+v[i][y];};
			auto cost3=[v,p,i](int x,int y,int z){return v[i][x]+v[i][y]+v[i][z];};
			if(j>=v[i][0]){
				f[j]=max(f[j],f[j-v[i][0]]+vpp(0));
			}
			if(j>=cost2(0,1)){
				f[j]=max(f[j],f[j-cost2(0,1)]+vpp(0)+vpp(1));
			}
			if(j>=cost2(0,2)){
				f[j]=max(f[j],f[j-cost2(0,2)]+vpp(0)+vpp(2));
			}
			if(j>=cost3(0,1,2)){
				f[j]=max(f[j],f[j-cost3(0,1,2)]+vpp(0)+vpp(1)+vpp(2));
			}
		}
	}
	cout<<f[n]<<"\n";
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	slv();

	return 0;
}

区间DP

字符串

数学

快速幂

模意义下大整数乘法

c++

ll binmul(ll a,ll b,ll m){
	ull c=(ull)a*b-(ull)((long double)a/m*b+0.5L)*m;
	if(c<m)return c;
	return c+m;
}

组合数学

分拆数

k部分拆数

p (n, k) = p (n - 1, k - 1) + p (n - k, k)

拆成含1和不含1即可。

第一类：掰出来的块里，至少有一个是 1。

第二类：掰出来的块里，没有 1（也就是说，所有块都大于等于 2）。

数据结构

树状数组

第k小

c++

int find_kth(int k){
	int ps=0,x=0;
	for(int i=log2(n);i>=0;i--){
		x+=1<<i;
		if(x>=n||ps+su[x]>=k){
			x-=1<<i;
		}else{
			ps+=su[x];
		}
	} // end with x = k-1
	return x+1;
}

维护区间最值

c++

int getmax(int l,int r){
	int ans=0;
	while(r>=l){
		ans=max(ans,a[r]);
		r--；
		for(;r-lowbit(r)>=l;r-=lowbit(r)){
			ans=max(ans,bit[r]);
		}
	}
	return ans;
}

void upd(int x,int v){
	a[x]=v;
	for(int i=x;i<=n;i+=lowbit(i)){
		c[i]=a[i];
		for(int j=1;j<lowbit(i);j<<=1){
			c[i]=max(c[i],c[i-j]);
		}
	}
}

BIT求逆序对

c++

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
const int N=5e5+5;
ll tree[N],a[N],tmp[N];
int n;

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

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

ll qry(int x){
	ll res=0;
	for(int i=x;i;i-=lowbit(i)){
		res+=tree[i];
	}
	return res;
}

void slv(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		tmp[i]=a[i];
	}
	sort(tmp+1,tmp+n+1);
	ll len=unique(tmp+1,tmp+n+1)-(tmp+1);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(tmp+1,tmp+len+1,a[i])-tmp;
	}
	ll ans=0;
	for(int i=n;i>=1;i--){
		ans+=qry(a[i]-1);
		add(a[i],1);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	slv();
	
	return 0;
}

线段树

区间加

c++

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int long long
const int N=1e5+5;
ll a[N];
ll tree[4*N],lazy[4*N]={0};

void build(int p,int l,int r){
	if(l==r){
		tree[p]=a[l];
		return;
	}
	int mid=l+(r-l)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	tree[p]=tree[2*p]+tree[2*p+1];
}

void update(int p,int l,int r,int ul,int ur,int val){
	if(ul<=l&&r<=ur){
		tree[p]+=val*(r-l+1);
		lazy[p]+=val;
		return;
	}
	int mid=l+(r-l)/2;
	if(lazy[p]){
		tree[2*p]+=lazy[p]*(mid-l+1),tree[2*p+1]+=lazy[p]*(r-mid);
		lazy[2*p]+=lazy[p],lazy[2*p+1]+=lazy[p];
		lazy[p]=0;
	}
	if(ul<=mid)update(p*2,l,mid,ul,ur,val);
	if(ur>mid)update(p*2+1,mid+1,r,ul,ur,val);
	tree[p]=tree[2*p]+tree[2*p+1];
}

ll qry(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		return tree[p];
	}
	ll sum=0;
	int mid=l+(r-l)/2;
	if(lazy[p]){
		tree[2*p]+=lazy[p]*(mid-l+1),tree[2*p+1]+=lazy[p]*(r-mid);
		lazy[2*p]+=lazy[p],lazy[2*p+1]+=lazy[p];
		lazy[p]=0;
	}
	if(ql<=mid)sum+=qry(2*p,l,mid,ql,qr);
	if(qr>mid)sum+=qry(2*p+1,mid+1,r,ql,qr);
	return sum;
}

void slv(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}	
	build(1,1,n);
	while(m--){
		int op;
		cin>>op;
		if(op==1){
			int x,y,k;
			cin>>x>>y>>k;
			update(1,1,n,x,y,k);
		}else{
			int x,y;
			cin>>x>>y;
			cout<<qry(1,1,n,x,y)<<"\n";
		}
	}
	
}

signed main()
{
	slv();

	return 0;
}

区间乘

c++

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int long long
const int N=1e5+5;

ll a[N];
int n,q,m;

struct segtree{
	ll sum,add,mul;
}s[N*4];

ll safeMod(ll x){
	return ((x%m)+m)%m;
}
void pushup(int p){
	s[p].sum=safeMod(s[p*2].sum+s[p*2+1].sum);	
}

void build(int p,int l,int r){
	s[p].mul=1;
	
	if(l==r){
		s[p].sum=a[l]%m;
		return;
	}
	int mid=l+(r-l)/2;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pushup(p);
}

void pushdown(int p,int l,int r){
	int mid=l+(r-l)/2;
	s[p<<1].sum=safeMod(s[p].mul*s[p<<1].sum+s[p].add*(mid-l+1));
	s[p<<1|1].sum=safeMod(s[p].mul*s[p<<1|1].sum+s[p].add*(r-mid));
	
	s[p<<1].mul=safeMod(s[p].mul*s[p<<1].mul);
	s[p<<1|1].mul=safeMod(s[p].mul*s[p<<1|1].mul);
	
	s[p<<1].add=safeMod(s[p].mul*s[p<<1].add+s[p].add);
	s[p<<1|1].add=safeMod(s[p<<1|1].add*s[p].mul+s[p].add);
	
	s[p].add=0,s[p].mul=1;
}

void rangeAdd(int p,int l,int r,int ul,int ur,int val){
	if(ul<=l&&r<=ur){
		s[p].sum=safeMod(s[p].sum+val*(r-l+1));
		s[p].add=safeMod(s[p].add+val);
		return;
	}
	if(s[p].add!=0||s[p].mul!=1)pushdown(p,l,r);
	int mid=l+(r-l)/2;
	if(ul<=mid)rangeAdd(p*2,l,mid,ul,ur,val);
	if(ur>mid)rangeAdd(p*2+1,mid+1,r,ul,ur,val);
	pushup(p);
}

void rangeMul(int p,int l,int r,int ul,int ur,int k){
	if(ul<=l&&r<=ur){
		s[p].sum=(s[p].sum*k)%m;
		s[p].mul=(s[p].mul*k)%m;
		s[p].add=(s[p].add*k)%m;
		return;
	}
	if(s[p].add!=0||s[p].mul!=1)pushdown(p,l,r);
	int mid=l+(r-l)/2;
	if(ul<=mid)rangeMul(2*p,l,mid,ul,ur,k);
	if(ur>mid)rangeMul(2*p+1,mid+1,r,ul,ur,k);
	pushup(p);
}

int qry(int p,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr){
		return s[p].sum;
	}
	if(s[p].add!=0||s[p].mul!=1)pushdown(p,l,r);
	int sum=0;
	int mid=l+(r-l)/2;
	if(ql<=mid)sum=safeMod(sum+qry(p<<1,l,mid,ql,qr));
	if(qr>mid)sum=safeMod(sum+qry(p<<1|1,mid+1,r,ql,qr));
	return sum;
}

void slv(){
	cin>>n>>q>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(q--){
		int op;
		cin>>op;
		int x,y,k;
		if(op==1){
			cin>>x>>y>>k;
			rangeMul(1,1,n,x,y,k);
		}else if(op==2){
			cin>>x>>y>>k;
			rangeAdd(1,1,n,x,y,k);
		}else{
			cin>>x>>y;
			cout<<qry(1,1,n,x,y)<<"\n";
		}
	}
		
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	slv();

	return 0;
}

可持久化线段树

c++

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int N,M;
const int C=1e6+5;
int num,a[C],rt[C];
struct Node{
	int l,r,val;
}tree[C*25];

int build(int l,int r){
	int p=++num;
	if(l==r){
		tree[p].val=a[l];
		return p;
	}
	int mid=l+(r-l)/2;
	tree[p].l=build(l,mid);
	tree[p].r=build(mid+1,r);
	return p;
}

int update(int p,int l,int r,int x,int val){
	int q=++num;
	tree[q]=tree[p];
	if(l==r){
		tree[q].val=val;
		return q;
	}
	int mid=l+(r-l)/2;
	if(x<=mid){
		tree[q].l=update(tree[q].l,l,mid,x,val);
	}else{
		tree[q].r=update(tree[q].r,mid+1,r,x,val);
	}
	return q;
}

int qry(int p,int l,int r,int x){
	if(l==r){
		return tree[p].val;
	}
	int mid=l+(r-l)/2;
	if(x<=mid){
		return qry(tree[p].l,l,mid,x);
	}
	else{
		return qry(tree[p].r,mid+1,r,x);
	}
}

void slv(){
	cin>>N>>M;
	for(int i=1;i<=N;i++)cin>>a[i];
	rt[0]=build(1,N);
	for(int i=1;i<=M;i++){
		int ver,op;
		cin>>ver>>op;
		if(op==1){
			int pos,c;
			cin>>pos>>c;
			rt[i]=update(rt[ver],1,N,pos,c);
		}else{
			int pos;
			cin>>pos;
			cout<<qry(rt[ver],1,N,pos)<<"\n";
			rt[i]=rt[ver];
		}
		
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	slv();
	
	return 0;
}

算法

LIS

$O (n l o g n)$

c++

tails.push_back(a[1]);
	for(int i=2;i<=n;i++){
		if(a[i]>tails.back()){
			tails.push_back(a[i]);
		}else{
			auto it=lower_bound(tails.begin(),tails.end(),a[i]);
			*it=a[i];
		}
	}
	cout<<tails.size()<<"\n";

归并排序

求逆序对

c++

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
const int N=5e5+5;
ll a[N],tmp[N];
ll ans;
int n;

void msort(int l,int r){
	if(l==r)return;
	int mid=l+(r-l)/2;
	msort(l,mid);
	msort(mid+1,r);
	int i=l,j=mid+1,p=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]){
			tmp[p++]=a[i++];
		}else{
			tmp[p++]=a[j++];
			ans+=(mid-i+1);
		}
	}
	while(i<=mid){
		tmp[p++]=a[i++];
	}
	while(j<=r){
		tmp[p++]=a[j++];
	}
	for(int i=l;i<=r;i++){
		a[i]=tmp[i];
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	msort(1,n);
	cout<<ans<<"\n";
	
	return 0;
}

图论

计算几何

杂项

离散化

c++

for(int i=1;i<=n;i++){
		cin>>a[i];
		tmp[i]=a[i];
	}
	sort(tmp+1,tmp+n+1);
	ll len=unique(tmp+1,tmp+n+1)-(tmp+1);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(tmp+1,tmp+len+1,a[i])-tmp;
	}

离线算法

CDQ分治

点对

c++

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
const int N=1e5+5,K=2e5+5;
int n,k;
int c[K],f[N],ans[N];

struct Elem{
	int a,b,c;
	int cnt;
	int val; // val denote multiple number
}a[N],init[N],tmp[N];

bool cmp(Elem &a,Elem &b){
	if(a.a!=b.a)return a.a<b.a;
	if(a.b!=b.b)return a.b<b.b;
	return a.c<b.c;
}

void add(int x,int val){
	for(int i=x;i<=k;i+=i&-i){
		c[i]+=val;
	}
}

int qry(int x){
	int sum=0;
	for(int i=x;i;i-=i&-i){
		sum+=c[i];
	}
	return sum;
}

void cdq(int l,int r){
	if(l==r)return;
	int mid=l+(r-l)/2;
	cdq(l,mid),cdq(mid+1,r);
	int i=l,p=l,j=mid+1;
	while(i<=mid && j<=r){
		if(a[i].b<=a[j].b){
			add(a[i].c,a[i].val);
			tmp[p++]=a[i++];
		}else{
			a[j].cnt+=qry(a[j].c);
			tmp[p++]=a[j++];
		}
	}
	while(j<=r){
		a[j].cnt+=qry(a[j].c);
		tmp[p++]=a[j++];
	}
	for(int k=l;k<i;k++){
		add(a[k].c,-a[k].val);
	}
	while(i<=mid){
		tmp[p++]=a[i++];
	}
	for(int k=l;k<=r;k++){
		a[k]=tmp[k];
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>init[i].a>>init[i].b>>init[i].c;
	}
	sort(init+1,init+n+1,cmp);
	int unicnt=1;
	a[1]=init[1];
	a[1].cnt=0,a[1].val=1;
	for(int i=2;i<=n;i++){
		if(a[unicnt].a==init[i].a && a[unicnt].b==init[i].b && a[unicnt].c==init[i].c){
			a[unicnt].val++;
		}else{
			a[++unicnt]=init[i];
			a[unicnt].val=1;
			a[unicnt].cnt=0;
		}
	}
	cdq(1,unicnt);
	for(int i=1;i<=unicnt;i++){
		f[i]=a[i].cnt+a[i].val-1;
	}
	for(int i=1;i<=unicnt;i++){
		ans[f[i]]+=a[i].val;
	}
	for(int i=0;i<n;i++){
		cout<<ans[i]<<"\n";
	}
	
	
	return 0;
}

sys_failure's 板子 ​

动态规划 ​

背包DP ​

二维费用背包 ​

有依赖的背包 ​

区间DP ​

字符串 ​

数学 ​

快速幂 ​

模意义下大整数乘法 ​

组合数学 ​

分拆数 ​

k部分拆数 ​

数据结构 ​

树状数组 ​

第k小 ​

维护区间最值 ​

BIT求逆序对 ​

线段树 ​

区间加 ​

区间乘 ​

可持久化线段树 ​

算法 ​

LIS ​

归并排序 ​

求逆序对 ​

图论 ​

计算几何 ​

杂项 ​

离散化 ​

离线算法 ​

CDQ分治 ​

点对 ​

sys_failure's 板子

动态规划

背包DP

二维费用背包

有依赖的背包

区间DP

字符串

数学

快速幂

模意义下大整数乘法

组合数学

分拆数

k部分拆数

数据结构

树状数组

第k小

维护区间最值

BIT求逆序对

线段树

区间加

区间乘

可持久化线段树

算法

LIS

归并排序

求逆序对

图论

计算几何

杂项

离散化

离线算法

CDQ分治

点对