基础算法
离散化
int lisa[maxn];int tail = 0;void init(){sort(lisa+1,lisa+tail+1);tail = unique(lisa+1,lisa+tail+1)-lisa-1;}int ind(int x){return lower_bound(lisa+1,lisa+tail+1,x) - lisa;}
初始化模板
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define deubg_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int main(){
debug_in;
return 0;
}
__int128
void read(__int128 &x) {
x = 0;
char ch;
int flag = 1;
while (ch = getchar()) {
if (ch == '-') flag = -1;
if (ch >= '0' && ch <= '9') break;
}
x = ch-'0';
while ((ch = getchar()) >= '0' && ch <= '9') {
x = x*10 + ch-'0';
}
x *= flag;
}
void out(__int128 x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x >= 10) out(x / 10);
putchar(x % 10 +'0');
}
f(x) = a*x*x + b *x + c 二元一次方程顶点公式：（-b/2a,(4ac-b2)/4a)
树相关
Cayley公式：对于n个不同的节点，能够组成的无根树（原来是无向连通图或者是有标志节点的树）的种数是n^(n-1)种
有根树：n^(n-1)
调和级数相关
求n/1 + n/2 + n/3 + … + n/k
ll solve(ll n,ll k){
ll m=sqrt(n);
ll ans=0;
for(ll i=1;i<=k&&i<=m;i++){
ans=(ans+n/i);
}
if(k<=m){
return ans;
}
else{
for(ll i=n/min(n,k);i<=m;i++){
ans =(ans+ (n/i - n/(i+1)) * i);
}
if(k<n){
ans-=(n/(n/k)-k)*(n/k);
}
if( n / m == m)
ans -= m;
}
return ans;
}
求卡特兰数 (递推方式)
int N;
ll f[maxn];
f[0] = 1;f[1] = 1;
for(int i = 2;i<=N;i++){
for(int j = 0;j<=i-1;j++){
f[i] += f[j] * f[i-1-j];
}
}
求卡特兰数 (公式方式 C(2n,n)/(n+1))
ll f[maxn];
f[0]=f[1]=1;
for(int i=2;i<=n;i++) f[i]+=f[i-1]*(4*i-2)/(i+1);
分数计算
struct node
{
public:
ll son,mu;
ll gcd(ll a,ll b){
return !b? a : gcd(b,a%b);
}
void init(){
ll g = gcd(son,mu);
son/=g,mu/=g;
}
bool operator < (const node &o){
return son * o.mu < o.son * mu;
}
friend node operator + (node &a,node &b){
node ans;
if(a.son == 0) return b;
if(b.son == 0) return a;
ans.mu = a.mu * b.mu;
ans.son = a.son * b.mu + a.mu * b.son;
ans.init();
return ans;
}
friend node operator /(node a,ll x){
node ans = a;
ans.mu *= x;
ans.init();
return ans;
}
};
组合数大礼包
struct AC
{
static const int maxn = 1e6+10;
ll f[maxn];
void init(int mod){ //预处理阶乘
f[0] = 1;
for(int i = 1;i<maxn;i++) f[i] = f[i-1]*i%mod;
}
ll ksm(ll a,ll b,ll mod){
ll ans = 1;
while(b){
if(b&1) ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
ll C_mod(ll n,ll m,ll mod){//组合数%mod
return f[n] * ksm(f[m] * f[n-m]%mod,mod-2,mod)%mod;
}
ll lucas_mod(ll n,ll m,ll mod){
return m? C_mod(n%mod,m%mod,mod) * lucas_mod(n/mod,m/mod,mod)%mod : 1;
}
ll A(ll n, ll r)//排列数
{
ll sum = 1;
for (int i = 0; i < r; i++)
sum *= n-i;
return sum;
}
ll C(ll n,ll K){ //组合数
if(K>n) return 0;
if(K > n-K) K = n-K;
ll m = 1,s = 1;
for(int i = 0;i<K;i++){
m = m*(n-i);
s = s*(i+1);
}
return m/s;
}
}ac;
计算几何
struct Point
{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;y = _y;
}
Point operator -(const Point &b)const{
return Point(x - b.x,y - b.y);
}
double operator *(const Point &b)const{
return x*b.x + y*b.y;
}
};
//两点之间的距离
double dist(Point a,Point b){
return sqrt((a-b)*(a-b));
}
//两个圆相交的面积
double Area_of_overlap(Point c1,double r1,Point c2,double r2)
{
double d = dist(c1,c2);
if(r1 + r2 < d + eps)return 0;
if(d < fabs(r1 - r2) + eps)
{
double r = min(r1,r2);
return PI*r*r;
}
double x = (d*d + r1*r1 - r2*r2)/(2*d);
double t1 = acos(x / r1);
double t2 = acos((d - x)/r2);
return r1*r1*t1 + r2*r2*t2 - d*r1*sin(t1);
}
矩阵快速幂
struct Mat
{
int mat[33][33];
Mat(){
memset(mat,0,sizeof mat);
}
Mat operator *(const Mat &b)const {
Mat res;
memset(&res,0,sizeof res);
for(int i = 0;i<=N;i++){
for(int j = 0;j<=N;j++){
for(int k = 0;k<=N;k++){
res.mat[i][j] += mat[i][k] * b.mat[k][j] % mod; res.mat[i][j]%=mod;
}
}
}
return res;
}
};
Mat ksm(Mat M,int b){
Mat res;
memset(&res,0,sizeof res);
for(int i = 0;i<=N;i++) res.mat[i][i] = 1;
while(b){
if(b&1) res = res * M;
M = M*M;
b>>=1;
}
return res;
}
高精度
struct bign{
int d[50], len;
void clean() { while(len > 1 && !d[len-1]) len--; }
bign() { memset(d, 0, sizeof(d)); len = 1; }
bign(int num) { *this = num; }
bign(char* num) { *this = num; }
bign operator = (const char* num){
memset(d, 0, sizeof(d)); len = strlen(num);
for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';
clean();
return *this;
}
bign operator = (int num){
char s[20]; sprintf(s, "%d", num);
*this = s;
return *this;
}
bign operator + (const bign& b){
bign c = *this; int i;
for (i = 0; i < b.len; i++){
c.d[i] += b.d[i];
if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;
}
while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;
c.len = max(len, b.len);
if (c.d[i] && c.len <= i) c.len = i+1;
return c;
}
bign operator - (const bign& b){
bign c = *this; int i;
for (i = 0; i < b.len; i++){
c.d[i] -= b.d[i];
if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;
}
while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;
c.clean();
return c;
}
bign operator * (const bign& b)const{
int i, j; bign c; c.len = len + b.len;
for(j = 0; j < b.len; j++) for(i = 0; i < len; i++)
c.d[i+j] += d[i] * b.d[j];
for(i = 0; i < c.len-1; i++)
c.d[i+1] += c.d[i]/10, c.d[i] %= 10;
c.clean();
return c;
}
bign operator / (const bign& b){
int i, j;
bign c = *this, a = 0;
for (i = len - 1; i >= 0; i--)
{
a = a*10 + d[i];
for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
c.d[i] = j;
a = a - b*j;
}
c.clean();
return c;
}
bign operator % (const bign& b){
int i, j;
bign a = 0;
for (i = len - 1; i >= 0; i--)
{
a = a*10 + d[i];
for (j = 0; j < 10; j++) if (a < b*(j+1)) break;
a = a - b*j;
}
return a;
}
bign operator += (const bign& b){
*this = *this + b;
return *this;
}
bool operator <(const bign& b) const{
if(len != b.len) return len < b.len;
for(int i = len-1; i >= 0; i--)
if(d[i] != b.d[i]) return d[i] < b.d[i];
return false;
}
bool operator >(const bign& b) const{return b < *this;}
bool operator<=(const bign& b) const{return !(b < *this);}
bool operator>=(const bign& b) const{return !(*this < b);}
bool operator!=(const bign& b) const{return b < *this || *this < b;}
bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}
string str() const{
char s[maxn]={};
for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';
return s;
}
};
istream& operator >> (istream& in, bign& x)
{
string s;
in >> s;
x = s.c_str();
return in;
}
ostream& operator << (ostream& out, const bign& x)
{
out << x.str();
return out;
}
熟链剖分
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1e5+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
int N,M,R,mod;
int w[maxn];
vector<int> adj[maxn];
struct segtree{
struct node{
int l,r;
ll sum,lazy;
}tr[maxn*4];
void pushup(node &cur,node &L,node &R){
cur.sum = L.sum + R.sum;
cur.sum %= mod;
}
void pushdown(node &cur,node &L,node &R){
if(cur.lazy == 0) return ;
L.lazy += cur.lazy; L.lazy %= mod;
R.lazy += cur.lazy; R.lazy %= mod;
L.sum += (ll)(L.r - L.l + 1) * cur.lazy; L.sum %= mod;
R.sum += (ll)(R.r - R.l + 1) * cur.lazy; R.sum %= mod;
cur.lazy = 0;
}
void build(int l,int r,int u = 1){
tr[u] = {l,r};
if(l != r){
int mid = (l+r)>>1;
build(l,mid,u*2);
build(mid+1,r,u*2+1);
}
}
void modify(int l,int r,int v,int u = 1){
if(l <= tr[u].l && tr[u].r <= r){
tr[u].lazy += v; tr[u].lazy %= mod;
tr[u].sum += (tr[u].r - tr[u].l +1) * v; tr[u].sum %= mod;
}else{
pushdown(tr[u],tr[u*2],tr[u*2+1]);
int mid = (tr[u].l + tr[u].r) >>1;
if(l<=mid) modify(l,r,v,u*2);
if(r>mid) modify(l,r,v,u*2+1);
pushup(tr[u],tr[u*2],tr[u*2+1]);
}
}
ll query(int l,int r,int u = 1){
if(l <= tr[u].l && tr[u].r <= r){
return tr[u].sum;
}else{
pushdown(tr[u],tr[u*2],tr[u*2+1]);
int mid = (tr[u].l + tr[u].r)>>1;
ll sum = 0;
if(l<=mid) sum += query(l,r,u*2), sum%=mod;
if(r > mid) sum += query(l,r,u*2+1),sum%=mod;
return sum;
}
}
}tree;
struct treepou{
int tt = 0;
int tim[maxn],id[maxn],sz[maxn],hson[maxn],fa[maxn],top[maxn],dep[maxn];
void init(){
dep[1] = 1;
}
void dfs1(int u){ //子树大小，每个节点的重孩子，每个孩子的父亲，节点的深度
sz[u] = 1;
for(auto v:adj[u]){
if(v == fa[u]) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v);
sz[u] += sz[v];
if(sz[v] > sz[hson[u]]){
hson[u] = v;
}
}
}
void dfs2(int u,int t){//弄出dfs序，每个节点的链头
tim[u] = ++tt;
id[tt] = u;
top[u] = t;
if(!hson[u]) return ;
dfs2(hson[u],t);
for(auto v:adj[u]){
if(v == fa[u] || v == hson[u]) continue;
dfs2(v,v);
}
}
void modify_tree(int x,int v){ //给根节点为x的子树的所有节点加v
tree.modify(tim[x],tim[x]+sz[x]-1,v);
}
ll query_tree(int x){ //计算根节点为x的子树的点权和
return tree.query(tim[x],tim[x]+sz[x]-1);
}
void modify_line(int x,int y,int v){//修改x到y的链上的点权，统一加1
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x,y);
tree.modify(tim[top[x]],tim[x],v);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
tree.modify(tim[x],tim[y],v);
}
ll query_line(int x,int y){ //查询x到y的链上的点权和
ll ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x,y);
ans += tree.query(tim[top[x]],tim[x]); ans %= mod;
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
ans += tree.query(tim[x],tim[y]); ans%=mod;
return ans;
}
}T;
void solve(){
tree.build(1,N);
T.init();
T.dfs1(R);
T.dfs2(R,R);
for(int i =1;i<=N;i++) tree.modify(T.tim[i],T.tim[i],w[i]%mod);
while(M--){
int op,x,y,z;
cin>>op;
if(op == 1){
cin>>x>>y>>z;
T.modify_line(x,y,z);
}else if(op == 2){
cin>>x>>y;
cout<<T.query_line(x,y)<<'\n';
}else if(op == 3){
cin>>x>>z;
T.modify_tree(x,z);
}else{
cin>>x;
cout<<T.query_tree(x)<<'\n';
}
}
}
int main(){
// debug;
ios;
cin>>N>>M>>R>>mod;
for(int i =1;i<=N;i++) cin>>w[i];
for(int i = 1;i<=N-1;i++){
int x,y;cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
}
solve();
return 0;
}
带权并查集
ll fa[maxn],dis[maxn];
ll find(ll x){
if(fa[x] != x){
ll f = fa[x];
fa[x] = find(fa[x]);
dis[x] += dis[f];
}
return fa[x];
}
bool join(ll x,ll y,ll v){
ll fx = find(x),fy = find(y);
if(fx != fy){
fa[fy] = fx;
dis[fy] = dis[x] + v - dis[y];
}else if(dis[y] - dis[x] != v){ //权值冲突
return false;
}
return true;
}
强连通分量SCC
struct SCC
{
static const int maxn = 1e5+10;
int dfn[maxn],low[maxn],scc_id[maxn],scc_sz[maxn],scc,tim;
int sk[maxn],top;bool in_sk[maxn];
void do_scc(){
for(int i = 1;i<=N;i++){ // N是节点个数
if(!dfn[i]){
tarjan(i);
}
}
}
void tarjan(int u){
dfn[u] = low[u] = ++tim;
sk[++top] = u,in_sk[u] = true;
for(int i = h[u];i;i = ne[i]){ // 遍历原来的图
int v = e[i];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u],low[v]);
}else if(in_sk[v]){
low[u] = min(low[u],dfn[v]);
}
}
if(low[u] == dfn[u]){
++scc;
int v;
do{
v = sk[top--],in_sk[v] = false;
scc_sz[scc]++;
scc_id[v] = scc;
}while(v != u);
}
}
void init_dag(){ //构建DAG图
for(int u = 1;u<=N;u++){
for(int i = h[u];i;i = ne[i]){
int v = e[i],ww = w[i];
int idu = scc_id[u],idv = scc_id[v];
if(idu != idv){
dag[idu].pb({idv,ww});
in[idv]++;
}
}
}
}
}tar;
二分图最大匹配
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
inline void read(int &x){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
int N,M,E;
vector<int> adj[maxn];
int match[maxn];
bool st[555];
bool find(int u){
for(auto v:adj[u]){
if(!st[v]){
st[v] = true;
if(match[v] == 0 || find(match[v])){
match[v] = u;
return true;
}
}
}
return false;
}
void solve(){
int ans = 0;
for(int i =1;i<=N;i++){
memset(st,0,M+10);
if(find(i)) ans++;
}
cout<<ans<<'\n';
}
int main(){
// debug;
ios;
cin>>N>>M>>E;
for(int i =1;i<=E;i++){
int x,y;cin>>x>>y;
adj[x].pb(y);
}
solve();
return 0;
}
平衡树
struct Treap{
int root,idx;
struct node{
int l,r;
int key,val;
int cnt,size;
}tr[100010];
void pushup(int p){
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key){
tr[++idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;
return idx;
}
void zig(int &p){
int q = tr[p].l;
tr[p].l = tr[q].r,tr[q].r = p,p = q;
pushup(tr[p].r),pushup(p);
}
void zag(int &p){
int q = tr[p].r;
tr[p].r = tr[q].l,tr[q].l = p,p = q;
pushup(tr[p].l),pushup(p);
}
void build(){
get_node(-inf);get_node(inf);
root = 1,tr[1].r = 2;
pushup(root);
if(tr[1].val < tr[2].val) zag(root);
}
void insert(int &p,int key){
if(!p) p = get_node(key);
else if(tr[p].key == key) tr[p].cnt++;
else if(key < tr[p].key){
insert(tr[p].l,key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}else{
insert(tr[p].r,key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}
void remove(int &p,int key){
if(!p) return ;
if(tr[p].key == key){
if(tr[p].cnt > 1) tr[p].cnt--;
else if(tr[p].l || tr[p].r){
if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val){
zig(p);
remove(tr[p].r,key);
}else{
zag(p);
remove(tr[p].l,key);
}
}else p = 0;
}else if(key < tr[p].key) remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
int get_rank_by_key(int p,int key){
if(!p) return 0;
if(key < tr[p].key) return get_rank_by_key(tr[p].l,key);
else if(key == tr[p].key) return tr[tr[p].l].size + 1;
else return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank){
if(!p) return inf;
if(rank <= tr[tr[p].l].size) return get_key_by_rank(tr[p].l,rank);
else if(rank <= tr[tr[p].l].size + tr[p].cnt) return tr[p].key;
else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p,int key){
if(!p) return -inf;
if(key <= tr[p].key) return get_prev(tr[p].l,key);
else return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key){
if(!p) return inf;
if(key >= tr[p].key) return get_next(tr[p].r,key);
else return min(tr[p].key,get_next(tr[p].l,key));
}
}trp;
使用方法
trp.build()
操作复杂度均为log
trp.insert(trp.root,v); //插入v
trp.remove(trp.root,v); //删除v
printf("%d\n",trp.get_rank_by_key(trp.root,v)-1);//因为最开始放了一个-inf，和inf，这里排名会比实际的排名-1
printf("%d\n",trp.get_key_by_rank(trp.root,v+1));//查询的时候，要查询比实际排名+1
printf("%d\n",trp.get_prev(trp.root,v));//获取前驱节点key
printf("%d\n",trp.get_next(trp.root,v));//获取后继节点key
线段树
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 1e5+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
int N,M;
int a[maxn];
struct segtree{
struct node{
int l,r;
ll sum,lazy;
}tr[maxn*4];
void pushup(node &cur,node &L,node &R){
cur.sum = L.sum + R.sum;
}
void pushdown(node &cur,node &L,node &R){
if(cur.lazy == 0) return ;
L.lazy += cur.lazy;
R.lazy += cur.lazy;
L.sum += (ll)(L.r - L.l + 1) * cur.lazy;
R.sum += (ll)(R.r - R.l + 1) * cur.lazy;
cur.lazy = 0;
}
void build(int l,int r,int u = 1){
tr[u] = {l,r};
if(l != r){
int mid = (l+r)>>1;
build(l,mid,u*2);
build(mid+1,r,u*2+1);
}
}
void modify(int l,int r,int v,int u = 1){
if(l <= tr[u].l && tr[u].r <= r){
tr[u].lazy += v;
tr[u].sum += (tr[u].r - tr[u].l +1) * v;
}else{
pushdown(tr[u],tr[u*2],tr[u*2+1]);
int mid = (tr[u].l + tr[u].r) >>1;
if(l<=mid) modify(l,r,v,u*2);
if(r>mid) modify(l,r,v,u*2+1);
pushup(tr[u],tr[u*2],tr[u*2+1]);
}
}
ll query(int l,int r,int u = 1){
if(l <= tr[u].l && tr[u].r <= r){
return tr[u].sum;
}else{
pushdown(tr[u],tr[u*2],tr[u*2+1]);
int mid = (tr[u].l + tr[u].r)>>1;
ll sum = 0;
if(l<=mid) sum += query(l,r,u*2);
if(r > mid) sum += query(l,r,u*2+1);
return sum;
}
}
}tree;
int main(){
// debug;
ios;
cin>>N>>M;
tree.build(1,N);
for(int i =1;i<=N;i++) {
int cur;cin>>cur;
tree.modify(i,i,cur); //在区间[i,i]的元素加一个cur，相当于单点修改
}
for(int i =1 ;i<=M;i++){
int op,x,y,k;cin>>op>>x>>y;
if(op == 1){
cin>>k;
tree.modify(x,y,k);//在区间[x,y] 加k
}else{
cout<<tree.query(x,y)<<'\n'; // 查询区间[x,y]的和
}
}
return 0;
}
多重背包
对于物品而言最多能够选择从s[i]个,同样也可不选
dp[j] : 体积为j能获得的最大价值
int N,V;
int w[maxn],v[maxn],s[maxn]; // 权值，价值，数量
ll dp[maxn];
int main(){
cin>>N>>V;
for(int i = 1;i<=N;i++) scanf("%d %d %d",&w[i],&v[i],&s[i]);
for(int i = 1;i<=N;i++){
for(int j = V;j>=w[i];j--){
for(int k = 1;k<=s[i] && k*w[i]<=j;k++){
dp[j] = max(dp[j],dp[j - k*w[i]] + k*v[i]);
}
}
}
}
多重背包，二进制拆分优化
将多重背包转换成01背包
int N,V;
int w[maxn],v[maxn],tail;//tail是二进制拆分后的物品数
ll dp[maxn];
int main(){
cin>>N>>V;
for(int i = 1;i<=N;i++){
int ww,vv,ss;scanf("%d %d %d",&ww,&vv,&ss);
for(int k = 1; k <= ss; k*=2){
ss -=k;
w[++tail] = k * ww;
v[tail] = k * vv;
}
if(ss) w[++tail] = ss*ww,v[tail] = ss*vv;
}
for(int i = 1;i<=tail;i++){
for(int j = V;j>=w[i];j--){
dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
}
}
分组背包
每一组物品中只能选择其中的一个物品
dp[j] : 体积为j能获得的最大价值
int T,N,V;
int G[110][1010],cnt[110];
int w[maxn],v[maxn];
ll dp[maxn];
cin>>V>>N;
for(int i = 1;i<=N;i++){
int t;
scanf("%d %d %d",&w[i],&v[i],&t);
T = max(T,t);//记录最大组数
G[t][++cnt[t]] = i; //记录每组每个物品的编号
}
for(int i = 1;i<=T;i++){ //组数
for(int j = V;j>=0;j--){ //体积 ： 因为是倒着循环的，故只会从一组中选一次
for(int k = 1;k<=cnt[T];k++){//物品
if(j - w[G[i][k]]>=0) dp[j] = max(dp[j],dp[j - w[G[i][k]]] + v[G[i][k]]);
}
}
}
ST表
静态求区间最大值，基于倍增的思想
int N,M;
int arr[maxn],Log2[maxn];//原始数组，log2(x)数组
int f[maxn][20];//F[i][j]: arr[i~i+2^j-1]的最大值
void ST_init(){ //初始化所有长度为2^x的区间最大值
for(int i = 1;i<=N;i++) Log2[i] = log(i)/log(2); //初始化log求值，之后O(1)取值
for(int i = 1;i<=N;i++) f[i][0] = arr[i];
int len = log(N)/log(2) +1;
for(int j = 1;j<len;j++){
for(int i = 1;i<=N-(1<<j)+1;i++){
f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r){ //查询arr[l~r]区间的最值
int k = Log2[r-l+1];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
奇奇怪挂的数据结构
马拉车算法
string s;
int ans[maxn],str[maxn],lef[maxn];
//ans：每一点的回文半径，str：插#字符后的字符串 lef：以某个为左边界的最长回文子串长度
int build(const string &s){
int n = s.length(), m = (n + 1)*2, ret = 0;
str[0] = '$'; str[m] = '@'; str[1] = '#'; ans[1] = 1;
for (int i = 1; i <= n; i++)
str[i*2] = s[i - 1], str[i*2+1] = '#';
ans[1] = 1;
for (int r = 0, p = 0, i = 2; i < m; ++i){
if (r > i) ans[i] = min(r - i, ans[p * 2 - i]);
else ans[i] = 1;
while(str[i - ans[i]] == str[i + ans[i]]) ++ans[i];
if (i + ans[i] > r) r = i + ans[i], p = i;
ret = max(ret, ans[i] - 1);
}
// 计算维护以每个位置为起点的最长回文串
for (int i = 0; i <= m; i++) lef[i] = 0;
for (int i = 2; i < m; i++) if (lef[i - ans[i] + 1] < i + 1) lef[i - ans[i] + 1] = i + 1;
for (int i = 1; i <= m; i++) if (lef[i] < lef[i - 1]) lef[i] = lef[i - 1];
return ret;//最长回文串的长度
}
int mid(int x, bool odd){
//求以x为中心的最长回文子串长度，若是求偶回文串，这里中心认为是中间靠左
if (odd) return ans[(x + 1) << 1] - 1;
return ans[(x + 1) << 1 | 1] - 1;
}
int left(int x){
//求以x为左端点的最长回文串的长度
return lef[(x + 1) << 1] - ((x+1) << 1);
}
树状数组
二维树状数组 [单点修改、区间查询]
int N,M;//N*M的矩阵
int tr[1111][1111];
int lowbit(int x){
return x&-x;
}
void add(int x,int y,int v){
for(int i = x;i<=N;i += lowbit(i)){
for(int j = y;j<=M;j += lowbit(j)){
tr[i][j] += v;
}
}
}
ll pre_sum(int x,int y){ //查询(1,1)到(x,y)矩阵和
ll sum = 0;
for(int i = x;i>=1;i -= lowbit(i)){
for(int j = y;j>=1;j -= lowbit(j)){
sum += tr[i][j];
}
}
return sum;
}
ll query(int x1,int y1,int x2,int y2){ //查询(x1,y2)到(x2,y2)的矩阵和
return pre_sum(x2,y2) - pre_sum(x1-1,y2) - pre_sum(x2,y1-1) + pre_sum(x1-1,y1-1);
}
二维树状数组 [区间修改，单点查询]
int tr[1010][1010];//NxN的矩阵
int lowbit(int x){
return x&-x;
}
void add(int x,int y,int v){
for(int i = x;i<=N;i += lowbit(i))
for(int j = y;j<=N;j += lowbit(j))
tr[i][j] += v;
}
int query(int x,int y){
int sum = 0;
for(int i = x;i>=1;i -= lowbit(i))
for(int j = y;j>=1;j -= lowbit(j))
sum += tr[i][j];
return sum;
}
//给左上角(x1,y1) ，右下角(x2,y2)的矩阵+v
add(x1,y1,+v);
add(x1,y2+1,-v);
add(x2+1,y1,-v);
add(x2+1,y2+1,+v);
求树的中心
基于树形dp
请你在树中找到一个点，使得该点到树中其他结点的最远距离最近，找到的这个点就是树的中心
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e4+10;
const int inf = 0x3f3f3f3f;
int N;
int h[maxn],e[maxn*2],w[maxn*2],ne[maxn*2],idx = 1;
int up[maxn],down1[maxn],down2[maxn],tag1[maxn];
//某个点，往上走的最远距离，往下走的最长距离，往下走的次长距离，往下走最长距离会经过的儿子结点编号
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dfs_down(int u,int fa = -1){ //求每个结点往下走的最长和次长距离，以及最长经过的儿子编号
int p1 = 0,p2 = 0;
for(int i = h[u];i;i = ne[i]){
int v = e[i],wei = w[i];
if(v == fa) continue;
int curp = dfs_down(v,u)+wei;
if(curp > p1){
p2 = p1,p1 = curp;
tag1[u] = v;
}else if(curp > p2){
p2 = curp;
}
}
down1[u] = p1,down2[u] = p2;//记录一下
return p1;
}
void dfs_up(int u,int fa = -1){ //父结点更新子结点，找子结点向上的最大距离
for(int i = h[u];i;i = ne[i]){
int v = e[i],wei = w[i];
if(v == fa) continue;
if(tag1[u] == v){
up[v] = wei + max(up[u],down2[u]);
}else{
up[v] = wei + max(up[u],down1[u]);
}
dfs_up(v,u);
}
}
int main(){
cin>>N;
for(int i = 1;i<=N-1;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs_down(1);
dfs_up(1);
int res = inf,H = -1;
for(int i = 1;i<=N;i++) {
int d = max(up[i], down1[i]); //向上、向下距离取最大值
if (d < res) {
res = d; //中心能移动的最大距离
H = i;//树的中心
}
}
return 0;
}
倍增法求LCA
int h[maxn],ne[maxn*2],e[maxn*2],idx = 1;
int q[maxn],fa[maxn][21],dep[maxn];
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
void bfs(int root){
int hh = 0,tt = -1;
q[++tt] = root;
dep[0] = 0,dep[root] = 1;
while(hh<=tt){
int u = q[hh++];
for(int i = h[u];i;i = ne[i]){
int v = e[i];
if(dep[v]) continue;
dep[v] = dep[u]+1;
q[++tt] = v;
fa[v][0] = u;
for(int k = 1;k<=20;k++){
fa[v][k] = fa[fa[v][k-1]][k-1];
}
}
}
}
int LCA(int x,int y){
if(dep[x] < dep[y]) swap(x,y);
for(int k = 20;k>=0;k--){
if(dep[fa[x][k]] >= dep[y])
x = fa[x][k];
}
if(x == y) return x;
for(int k = 20;k>=0;k--){
if(fa[x][k] != fa[y][x]){
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][0];
}
若有收获，就点个赞吧
0 人点赞
