正向表
int tot=0,h[M];
struct edge{
int nxt;
int to,cost;
}G[3*M];
void add(int a,int b,int c){
G[++tot]=(edge){h[a],b,c};
h[a]=tot;
}
LCA
跳重链
void dfs(int x,int f,int d){
dep[x]=d;
sz[x]=1;
fa[x]=f;son[x]=0;
for(int i=0;i<G[x].size();i++){
int u=G[x][i];
if(u==f)continue;
dfs(u,x,d+1);
if(sz[u]>sz[son[x]])son[x]=u;
sz[x]+=sz[u];
}
}
void dfs_top(int x,int tp){
top[x]=tp;
if(son[x])dfs_top(son[x],tp);
for(int i=0;i<G[x].size();i++){
int u=G[x][i];
if(u==fa[x]||u==son[x])continue;
dfs_top(u,u);
}
}
int LCA(int a,int b){
while(top[a]!=top[b]){
if(dep[top[a]]>dep[top[b]])a=fa[top[a]];
else b=fa[top[b]];
}
return dep[a]>dep[b]?b:a;
}
倍增
void dfs(int x,int f,int d){
dep[x]=d;
fa[x][0]=f;
for(int i=0;i<G[x].size();i++){
int u=G[x][i];
if(u==f)continue;
dfs(u,x,d+1);
}
}
int LCA(int a,int b){
if(dep[a]>dep[b])swap(a,b);
int step=dep[b]-dep[a];
for(int i=19;i>=0;i--)
if(step&1<<i)b=fa[b][i];
if(a==b)return a;
for(int i=19;i>=0;i--)
if(fa[a][i]!=fa[b][i])a=fa[a][i],b=fa[b][i];
return fa[a][0];
}
for(int j=1;j<=19;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
st表
预处理
void Init_RMQ(int n){
for(int i=1;i<=n;i++)f[i][0]=A[i];
lg2[1]=0;
for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
查询
int query(int l,int r){
int k=lg2[r-l+1];
return max(f[l][k],f[r-(1<<k)+1][k]);
}
数学
扩展欧几里得算法
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(!b){d=a;x=1;y=0;return;}
exgcd(b,a%b,d,y,x);y-=a/b*x;
}
逆元
int inv(int a){
ll x,y,d;
exgcd(a,m,d,x,y);
return (x%MOD+MOD)%MOD;
}
线性筛逆元
void Init(){
fac[0]=1;rev[1]=1;
for(int i=1;i<=n;i++)
fac[i]=(fac[i-1]*i)%MOD;
for(int i=2;i<=n;i++)//线性筛逆元
rev[i]=(MOD-MOD/i)*rev[MOD%i]%MOD;
}
高斯消元
void gauss(int n){
for(int i=1;i<=n;i++){
int r=i;
for(int j=i+1;j<=n;j++)//找到后面这一项最大的数
if(fabs(a[j][i])>fabs(a[r][i]))
r=j;
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[r][j]);
for(int j=i+1;j<=n;j++){
double f=1.0*a[j][i]/a[i][i];
for(int k=i;k<=n+1;k++)
a[j][k]-=f*a[i][k];
}
}
for(int i=n;i>=1;i--){
for(int j=i+1;j<=n;j++)
a[i][n+1]-=a[j][n+1]*a[i][j];
a[i][n+1]/=a[i][i];
}
}
中国剩余定理
for(int op=0;op<4;op++){//for需要合并的模数
LL x,y,d;
LL M=(mod-1)/md[op];//所有模数之和除以当前模数
exgcd(M,md[op],d,x,y);//求出当前模数对于这个值的逆元
x=(x%md[op]+md[op])%md[op];
po=(po+tmp[op]*x%(mod-1)*M%(mod-1))%(mod-1);//合并上去
}
Lucas定理
LL lucas(LL a,LL b){
LL res=1;
while(a&&b){
LL x=a%mod,y=b%mod;if(y>x)return 0;
res=res*C(x,y)%mod;
a/=mod;b/=mod;
}
return res;
}
树链剖分
寻找重儿子
void dfs(int x,int f,int d){
dep[x]=d;fa[x]=f;sz[x]=1;son[x]=0;
for(int i=h[x];i;i=G[i].nxt){
int u=G[i].to;
if(u==f)continue;
dfs(u,x,d+1);
if(sz[u]>sz[son[x]])son[x]=u;
sz[x]+=sz[u];
}
}
处理top
void dfs_top(int x,int tp){
top[x]=tp;ID[x]=++tt;ln[tt]=x;
if(son[x])dfs_top(son[x],tp);
for(int i=h[x];i;i=G[i].nxt){
int u=G[i].to;
if(u==son[x]||u==fa[x])continue;
dfs_top(u,u);
}
}
query
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
query(ID[top[u]],ID[u],1);
u=fa[top[u]];
}
else {
query(ID[top[v]],ID[v],1);
v=fa[top[v]];
}
}
if(dep[u]>dep[v])query(ID[v],ID[u],1);
else query(ID[u],ID[v],1);
“一起“二分
主要是利用归并的性质。
以3351为例：
#include<bits/stdc++.h>
#define M 100005
#define LL long long
#define P 131071
using namespace std;
struct erfen{
int l,r,mid,ans,id;
bool operator < (const erfen& res) const{
return mid<res.mid;
}
}F[M];
int n,A[M],m;
int X[M],Y[M],Ans[M];
LL Val[P+5];
void Add(int k){
Val[X[k]]+=Y[k];
}
LL calc(int k){
LL res=0;
for(int i=k;i<=P;i=((i+1)|k)){
res+=Val[i];
}
return 1LL*A[k]-res;
}
int main(){
// freopen("monster.in","r",stdin);
// freopen("monster.out","w",stdout);
cin>>n;
for(int i=0;i<n;i++)scanf("%d",&A[i]);
cin>>m;
for(int i=1;i<=m;i++)scanf("%d%d",&X[i],&Y[i]),X[i]&=P;
for(int i=0;i<n;i++)F[i].l=1,F[i].r=m,F[i].ans=-1,F[i].id=i;//二分当前怪兽是在哪个点死的,如果不是则ans=-1
int Time=20;
while(Time--){
for(int i=0;i<n;i++)F[i].mid=(F[i].l+F[i].r)>>1;
for(int i=0;i<=P;i++)Val[i]=0;
sort(F,F+n);
int cur=1;
for(int i=0;i<n;i++){
if(F[i].l>F[i].r)continue;
while(cur<=F[i].mid&&cur<=m){Add(cur);cur++;}
if(calc(F[i].id)<=0){
F[i].ans=F[i].mid;
F[i].r=F[i].mid-1;
}
else F[i].l=F[i].mid+1;
}
}
for(int i=0;i<n;i++){
if(F[i].ans==-1)continue;
Ans[F[i].ans]--;//当前时间少了一只
}
Ans[0]=n;
for(int i=1;i<=m;i++)Ans[i]+=Ans[i-1];
for(int i=1;i<=m;i++)printf("%d
",Ans[i]);
return 0;
}