CSP复习
一、tarjan
1.有向图缩点(强连通分量)
2.割点（根节点且有至少两个孩子 或 low[v]>=dfn[u]）
if((fa==0&&son>1)||(fa!=0&&dfn[u]<=low[v]))cut[u]=true;
3.边双（两条边算一条，记一个vis标记一下有没有经过）
P2860 [USACO06JAN]冗余路径Redundant Paths
求边双通常有两种方法：记住前驱节点，或是记住前驱边 。
注意重边问题，有些题只能记住前驱节点，有些题只能记住记住前驱边，不同的题不同对待。
记住前驱节点
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
if(!dfn[v]){tarjan(v,u);low[u]=min(low[u],low[v]);}
else low[u]=min(low[u],dfn[v]);
} 记住前驱边
for(int i=head[u];i;i=edge[i].next)
if(!vis[i])
{
vis[i]=vis[i^1]=1;
int v=edge[i].too;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else low[u]=min(low[u],dfn[v]);
} 4.点双（删掉任意一个节点仍是连通图）
void tarjan(int u)
{
dfn[u]=low[u]=++deep;
zhan[++tot]=u;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u])
{
cnt++;
while(zhan[tot]!=v)
{
add2(cnt,zhan[tot]);
add2(zhan[tot],cnt);
tot--;
}
tot--;
add2(cnt,v);
add2(v,cnt);
add2(cnt,u);
add2(u,cnt);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u,int fa)
{
if(u<=n)size[u]++;
for(int i=head2[u];i;i=edge2[i].next)
{
int v=edge2[i].too;
if(v==fa)continue;
dfs(v,u);
size[u]+=size[v];
}
if(u<=n)
{
f[u]=2*(n-1);
for(int i=head2[u];i;i=edge2[i].next)
{
int v=edge2[i].too;
if(v==fa)continue;
f[u]+=size[v]*(n-1-size[v]);
}
f[u]+=(n-size[u])*(size[u]-1);
}
} 二、2-sat
1.模板【模板】2-SAT 问题
0表示不选，1表示选
1.a=0 , a->a'
2.a=1 , a'->a
3.a=1那么b=1 , a->b b'->a'(隐藏b=0那么a=0)
4.a=0那么b=0 , a'->b' b->a(隐藏b=1那么a=1)
5.a=1那么b=0 , a->b' b->a'(隐藏b=1那么a=0)
6.a=0那么b=1 , a'->b b'->a(隐藏b=0那么a=1)
7.a=0并且b=0 a=0并且b=1 a=1并且b=0 a=1并且b=1 参考3-6,进行合并
8.a^b=0 a^b!=0 参考3-6,进行合并
如果col[a]==col[a'],那么无解。
关于求一组解，由于我们知道tarjan的dfn序其实就是拓扑的反序，所以当col[a]<col[a']时，a=1。
void tarjan(int u)
{
deep++;dfn[u]=low[u]=deep;
vis[u]=true;zhan[++tot]=u;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
else if(vis[v])low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u])
{
color++;vis[u]=false;col[u]=color;
while(zhan[tot]!=u)
{
vis[zhan[tot]]=false;
col[zhan[tot]]=color;
tot--;
}
tot--;
}
}
bool TWO_SAT()
{
for(int i=1;i<=2*n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n])return false;
return true;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=m;i++)
{
int a=read(),x=read(),b=read(),y=read();
if(x==0)
{
if(y==0)//a=1那么b=0(b=1那么a=0)
{
add(a,b+n);
add(b,a+n);
}
else{//a=1那么b=1(b=0那么a=0)
add(a,b);
add(b+n,a+n);
}
}
else{
if(y==0)//a=0那么b=0(b=1那么a=1)
{
add(a+n,b+n);
add(b,a);
}
else{//a=0那么b=1(b=0那么a=1)
add(a+n,b);
add(b+n,a);
}
}
}
if(TWO_SAT())
{
puts("POSSIBLE");
for(int i=1;i<=n;i++)
printf("%d ",col[i]<col[i+n]);
}
else printf("IMPOSSIBLE");
return 0;
} 2.前缀优化建图
区间，我们看成区间
和
如果区间那么这个物品一定不选，如果
，
那么这个物品一定选
signed main()
{
np=read();n=read();m=read();mp=read();
for(int i=1;i<=np;i++)//x=0那么y=1,y=0那么x=1
{
int x=read(),y=read();
add(x+n,y);
add(y+n,x);
}
for(int i=2;i<=m;i++)//x=0那么y=0,y=1那么x=1
{
add(n+n+i+m,n+n+i-1+m);
add(n+n+i-1,n+n+i);
}
for(int i=1;i<=n;i++)
{
int x=read(),y=read();
if(x>1)
{
add(i,n+n+m+x-1);//x=1那么y=0,
add(n+n+x-1,n+i);//y=1那么x=0,
}
add(i,n+n+y);//x=1那么y=1,
add(n+n+m+y,n+i);//y=0那么x=0,
}
for(int i=1;i<=mp;i++)//x=1那么y=0,y=1那么x=0
{
int x=read(),y=read();
add(x,y+n);
add(y,x+n);
}
for(int i=1;i<=n+n+m+m;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
if(col[i]==col[i+n]){puts("-1");return 0;}
for(int i=1;i<=m;i++)
if(col[n+n+i]==col[n+n+m+i]){puts("-1");return 0;}
for(int i=1;i<=n;i++)
if(col[i]<col[i+n])ans++;
for(int i=1;i<=m;i++)
if(col[n+n+i]<col[n+n+m+i])
{
printf("%d %d\n",ans,i);
break;
}
for(int i=1;i<=n;i++)
if(col[i]<col[i+n])printf("%d ",i);
} 三、Floyd
1.两点之间的距离
for(int i=1;i<=n;i++)f[i][i]=0;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][i]); 2.判负环
if(f[i][i]<0){puts("-1");return 0;} 3.DP
表示以前k个数做中转点，i到j的最短路。
按时间顺序排列，对于时间<=T的点都可以做中转点。
now=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
x++;y++;
while(a[now]<=z&&now<=n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][now]+g[j][now]);
now++;
}
if(a[x]>z||a[y]>z)cout<<-1<<endl;
else {
if(g[x][y]==1e8)cout<<-1<<endl;
else cout<<g[x][y]<<endl;
}
} 4.传递闭包
在可以走回头路的状压DP中需要用到传递闭包。
memset(f,0x3f,sizeof(f));
memset(dp,0x3f,sizeof(dp));
f[0][1]=0;
for(int i=1;i<(1<<n);i++)
{
int gs=0;
for(int j=0;j<n;j++)
if(i&(1<<j))
{
gs++;
id[gs]=j;
}
for(int p=1;p<=gs;p++)
for(int j=1;j<=gs;j++)
A[j][p]=g[id[p]][id[j]];
for(int j=1;j<=gs;j++)A[j][j]=0;
for(int k=1;k<=gs;k++)
for(int p=1;p<=gs;p++)
for(int j=1;j<=gs;j++)
A[p][j]=min(A[p][j],A[p][k]+A[k][j]);
for(int p=1;p<=gs;p++)
for(int j=1;j<=gs;j++)f[id[p]][i]=min(f[id[p]][i],f[id[j]][i]+A[j][p]);
for(int j=0;j<n;j++)
if((i&(1<<j))&&f[j][i]!=0x3f3f3f3f)
{
for(int k=0;k<n;k++)
if(((i&(1<<k))==0)&&g[j][k]!=0x3f3f3f3f)
f[k][i+(1<<k)]=min(f[k][i+(1<<k)],f[j][i]+g[j][k]);
}
} 5.最小环
i和j两点加上中转点k，构成一个环
for(int i=1;i<=n;i++)
f[i][i]=e[i][i]=0;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
ans=min(ans,f[i][j]+e[j][k]+e[k][i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
} 四、三分和随机（模拟退火）
三分和模拟退火都是解决极值类问题。
三分用来解决函数极值。
模拟退火还可以解决一些不是函数关系，往往要选出一些东西的题目。
1.三分
double l=0.0,r=n;
while(r-l>=1e-3)
{
double mid1=l+(r-l)/3.0;
double mid2=(r)-(r-l)/3.0;
if(suan(mid1)<suan(mid2))r=mid2;
else l=mid1;
} 2.模拟退火
精度有些问题，所以退火后再前后枚举一下
为了使答案更加准确，我们可以先随机若干次，这样的话跳动会更加优秀。
for(int i=1;i<=3000;i++)
{
int X=rand()%n+1,Y=rand()%n+1;
int ret=calc(X,Y);
if(ret>ans)ans=ret,x=X,y=Y;
} void tui()
{
t=1000;
while(t>1e-12)
{
X=x+(rand()*2-RAND_MAX)*t*0.0001;
if(X<0)X=0;if(X>1000)X=1000;
now=suan(X);
double anss=now-ans2;
if(anss<0.0){ans1=X;ans2=now;x=X;}
else if(exp(-anss/t)*RAND_MAX>rand())x=X;
t=t*delta;
}
}
void solve()
{
ans1=0.0;ans2=suan(x);
tui();
double xu=ans1;
double xjh=xu;
double XJH=0.0;
for(int i=1;i<=1000;i++)
{
xjh+=0.0001;
if(xjh>1000.0)break;
XJH=suan(xjh);
if(XJH<ans2)
{
ans1=xjh;
ans2=XJH;
}
}
xjh=xu;
XJH=0.0;
for(int i=1;i<=1000;i++)
{
xjh-=0.0001;
if(xjh<0.0)break;
XJH=suan(xjh);
if(XJH<ans2)
{
ans1=xjh;
ans2=XJH;
}
}
} 3.多函数
这题是双函数，三分求函数极值的话，需要三分套三分，而且细节多。
要找多个点时，模拟退火就是一个不错的选择。因为模拟退火基本上不用修改，而三分会写自闭。
三分套三分
double sanfen(double x,double y){
double lx=cx,ly=cy,rx=dx,ry=dy;
while(dis(lx,ly,rx,ry)>eps){
double m1x=lx+(rx-lx)/3.0,m2x=rx-(rx-lx)/3.0,m1y=ly+(ry-ly)/3.0,m2y=ry-(ry-ly)/3.0;
double ans1=dis(x,y,m1x,m1y)/r+dis(m1x,m1y,dx,dy)/q;
double ans2=dis(x,y,m2x,m2y)/r+dis(m2x,m2y,dx,dy)/q;
if(ans2-ans1>eps) rx=m2x,ry=m2y;
else lx=m1x,ly=m1y;
}
return dis(x,y,lx,ly)/r+dis(lx,ly,dx,dy)/q;
}
double lx=ax,ly=ay,rx=bx,ry=by;
while(dis(lx,ly,rx,ry)>eps){
double m1x=lx+(rx-lx)/3.0,m2x=rx-(rx-lx)/3.0,m1y=ly+(ry-ly)/3.0,m2y=ry-(ry-ly)/3.0;
double ans1=dis(ax,ay,m1x,m1y)/p+sanfen(m1x,m1y);
double ans2=dis(ax,ay,m2x,m2y)/p+sanfen(m2x,m2y);
if(ans2-ans1>eps) rx=m2x,ry=m2y;
else lx=m1x,ly=m1y;
} 模拟退火
void tui()
{
t=2000;
while(t>1e-14)
{
X=x+(rand()*2-RAND_MAX)*t;
Y=y+(rand()*2-RAND_MAX)*t;
if(X<0)X=0;if(X>dis(ax,bx,ay,by))X=dis(ax,bx,ay,by);
if(Y<0)Y=0;if(Y>dis(cx,dx,cy,dy))Y=dis(cx,dx,cy,dy);
now=suan(X,Y);
anss=now-ans;
if(anss<0){ans=now;x=X;y=Y;}
else if(exp(-anss/t)*RAND_MAX>rand()){x=X;y=Y;}
t=t*delta;
}
} 4.和随机有点关系的题目
这题数据范围一看，发现会20！，但只要求最大那就可以随机。
随机的话两种思路，random_shuffle和模拟退火
怎么模拟退火，每次交换两个数，在用DP求解即可。
inline void tui()
{
nowans=ans,t=2000;
while (t>1e-6)
{
int x=0,y=0;
x=rand()%n+1;y=rand()%n+1;
if(x==y) continue;
swap(a[x],a[y]);
now=DP();
anss=now-ans;
if (anss<0) ans=nowans=now;
else if (exp(-anss/t)*RAND_MAX>rand()) nowans=now;
else swap(a[x],a[y]);
t*=delta;
}
} 可以状压，当然模拟退火一样可以。
五、容斥
容斥的一般式子：
1.简单容斥
就是加加减减，还算简单。
2.和集合有关的容斥
有题了再补
3、minmax容斥
推导详见洛谷日报或GXZlegend
公式：
应用：
常用来求“每次选一个数，使每个数被选的次数至少到达某个值的期望次数”
首先我们要知道对于一个局面（比如第一个数选1次，第二个数选2次）的期望步数就是这个局面的概率分之一。
证明：设期望为
，概率为
，那么%5Ctimes(E%2B1)&preview=true)
，化简得
为啥是这样的呢？就是有的概率一遍就行，有
的概率再来一次。
普遍情况：
个数，每个数有个权重
，那么每一次选中第
个数的概率就为
，问每个数被选的次数至少到达
的期望次数。
公式：!%7D%7B%5Csum%20c_i!%7D%20%5Cprod%20(%5Cfrac%7Ba%5Bx_i%5D%7D%7B%5Csum%20a%5Bx_i%5D%7D)%5E%7Bd_i%7D&preview=true)
解释:
是得到一个指定集合内元素的期望时间,
有重复元素的排列下,
是对于集合内每个数的概率
例题：
hdu4336]Card Collector
裸题，但也有用到一个状压技巧，和飞翔的小鸟一样。
double ans=0;
for(int i=0;i<n;i++)scanf("%lf",&a[1<<i]);
for(int i=1;i<(1<<n);i++)
{
f[i]=f[i-lowbit(i)]+a[lowbit(i)];
gs[i]=gs[i-lowbit(i)]+1;
}
for(int i=1;i<(1<<n);i++)
if(gs[i]&1)ans+=1.0/f[i];
else ans-=1.0/f[i];
printf("%lf\n",ans); E - Gachapon
题意：
个数，每个数有个权重
，那么每一次选中第
个数的概率就为
，问每个数被选的次数至少到达
的期望次数。
题解：
暴力做法就是枚举集合，然后通过上面给出的式子进行计算。
正解，考虑已经求出了一个集合的答案，现在要在这个集合
里加入一个新的数
发现只要记录一下和
即可转移
代码：
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=405;
const int mod=998244353;
int n,a[N],b[N],jc[N],inv[N],sum[N],f[N][N][N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b=b/2;
}
return res;
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();
jc[0]=jc[1]=inv[0]=inv[1]=1;
for(int i=2;i<=400;i++)jc[i]=jc[i-1]*i%mod;
for(int i=2;i<=400;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=400;i++)inv[i]=inv[i]*inv[i-1]%mod;
int s1=0,s2=0;
f[0][0][0]=mod-1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=s1;j++)
for(int k=0;k<=s2;k++)
f[i][j][k]=f[i-1][j][k];
sum[0]=1;
for(int j=1;j<b[i];j++)sum[j]=sum[j-1]*a[i]%mod;
for(int j=0;j<b[i];j++)sum[j]=sum[j]*inv[j]%mod;
for(int j=0;j<=s1;j++)
for(int k=0;k<=s2;k++)
for(int p=0;p<b[i];p++)
f[i][j+p][k+a[i]]=(f[i][j+p][k+a[i]]-f[i-1][j][k]*sum[p]%mod+mod)%mod;
s1+=b[i]-1;s2+=a[i];
}
int ans=0;
for(int i=0;i<=s1;i++)
for(int j=1;j<=s2;j++)
{
int x=f[n][i][j]*jc[i]%mod;
x=x*kuai(kuai(j,mod-2),i)%mod;
ans=(ans+x*s2%mod*kuai(j,mod-2)%mod)%mod;
}
cout<<ans;
} 六、DP
1.树形DP
背包P2014 选课
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
dfs(v);
for(int j=m;j>=1;j--)
{
for(int k=0;k<j;k++)
{
f[u][j]=max(f[u][j],f[v][k]+f[u][j-k]);
}
}
} 最大独立子集旅游
void dfs(int u,int fa)
{
f[u][1]=1;
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa)continue;
dfs(v,u);
f[u][1]+=f[v][0];
f[u][0]+=max(f[v][1],f[v][0]);
}
} 2.状压DP
for(int i=2;i<=n;i++)
{
for(int j=1;j<=cnt;j++)
if((xu[j]&S[i-1])==xu[j])
for(int k=1;k<=cnt;k++)
if(b[j][k])
if((xu[k]&S[i])==xu[k])dp[i][k]=(dp[i][k]+dp[i-1][j])%mod;
} 3.数位DP
ll dfs(int len,bool b,int sum,bool zero,int d)//b=0表示前面都是最大的
{
ll ans=0;
if(len==0)return sum;
if(f[len][b][sum][zero]!=-1)return f[len][b][sum][zero];
for(int i=0;i<=9;i++)
{
if(b==false && i>num[len]) break;
ans=ans+dfs(len-1,(b==true)||(i<num[len]),sum+(((zero!=1)||(i!=0))&&(i==d)),zero&&(i==0),d);
}
f[len][b][sum][zero]=ans;
return ans;
} 4.概率期望DP
题目：给出一个n×m的矩阵区域，一个机器人初始在第x行第y列，每一步机器人会等概率的选择停在原地，左移一步，右移一步，下移一步，如果机器人在边界则不会往区域外移动，问机器人到达最后一行的期望步数。
题解：
这题很难啊，50分的要用期望+高斯消元。
我们先设为从(i,j)到最后一行的期望步数
f[i][j]=f[i][j]/4+f[i][j-1]/4+f[i][j+1]/4+f[i+1][j]/4+1 (1<j<m) f[i][j]=f[i][j]/3+f[i+1][j]/3+f[i][j+1]/3+1 j=1 f[i][j]=f[i][j]/3+f[i+1][j]/3+f[i][j-1]/3+1 j=m
初始化是什么？
f[n][i]=0
两维的数组不好，我们可以压掉第一维（比较好高斯消元）。
然后，我们化一下式子：
f[i]=f[i]/3+f[i+1]/3+last[i]/3+1 2/3 * f[i]=f[i+1]/3+last[i]/3+1 f[i]=f[i+1]/2+last[i]/2 + 3/2 f[i]-f[i+1]/2=last[i]/2 + 3/2 (i=1)
f[i]=f[i]/3+f[i-1]/3+last[i]/3+1 2/3 * f[i]=f[i-1]/3+last[i]/3+1 f[i]=f[i-1]/2+last[i]/2 + 3/2 f[i]-f[i-1]/2=last[i]/2 + 3/2 (i=m)
f[i]=f[i]/4+f[i-1]/4+f[i+1]/4+last[i]/4+1 3/4 * f[i]=f[i-1]/4+f[i+1]/4+last[i]/4+1 f[i]=f[i-1]/3+f[i+1]/3+last[i]/3 + 4/3 f[i]-f[i-1]/3-f[i+1]/3=last[i]/3 + 4/3 (1<i<m)
这不就是高斯消元吗，对每一行做一遍高斯消元，把答案记录在last数组里。
我们发现高斯矩阵的系数很小，不需要n^3枚举，只要手动解就好。
5.子集DP
详见我牛客题解SOS-DP(子集DP)
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
if(j&(1<<i))F[j]+=F[j^(1<<i)]; 6.换根DP
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
for(int j=0;j<A[v].size();j++)
{
int x=b[v][j],y=A[v][j];
x=gcd(x,a[u]);
int z=lower_bound(b[u].begin(),b[u].end(),x)-b[u].begin();
A[u][z]-=y;
}
for(int j=0;j<A[u].size();j++)
{
int x=b[u][j],y=A[u][j];
x=gcd(x,a[v]);
int z=lower_bound(b[v].begin(),b[v].end(),x)-b[v].begin();
A[v][z]+=y;
}
dp(v,u);
A[u]=B[u];
} 7.单调队列优化DP
for(int i=1;i<=n;i++)
{
while(x[j]+L<=x[i])
{
if(f[j]>-1e8)
{
while(l<=r&&f[j]>=f[q[r]])r--;
q[++r]=j;
}
j++;
}
while(x[q[l]]+R<x[i])l++;
if(l<=r)f[i]=f[q[l]]+s[i];
} 8.数据结构优化DP
题目：定义一个长度为奇数的区间的值为其所包含的的元素的中位数。
现给出n个数的序列a，求将所有长度为奇数的区间的值排序后，第K大的值为多少。
题解：
DP转移时要求一个区间的和，可以用树状数组维护一下。
9.矩阵优化DP
node operator * (node a,node b)
{
for(int i=1;i<=k+2;i++)
for(int j=1;j<=k+2;j++)xu.m[i][j]=0;
for(int i=1;i<=k+2;i++)
for(int j=1;j<=k+2;j++)
for(int p=1;p<=k+2;p++)
xu.m[i][j]=(xu.m[i][j]+a.m[i][p]*b.m[p][j]%mod)%mod;
return xu;
} 10.斜率优化DP
写出方程； 整理式子，将只和j有关的当成y，将i，j都有关的当成kx，将只和i有关的当成b 显然，如果想让F[i]最小，那就是b最小，对于图像上的若干点，选择最下面的一个就是最优的j。
f[0]=0;
int l=1,r=1;
q[1]=0;
for(int i=1;i<=n;i++)
{
while(l<r&&(f[q[l+1]]-f[q[l]])<=(s+sumt[i])*(sumc[q[l+1]]-sumc[q[l]]))l++;
f[i]=f[q[l]]+sumt[i]*(sumc[i]-sumc[q[l]])+s*(sumc[n]-sumc[q[l]]);
while(l<r&&(f[q[r]]-f[q[r-1]])*(sumc[i]-sumc[q[r]])
>=(f[i]-f[q[r]])*(sumc[q[r]]-sumc[q[r-1]]))r--;
q[++r]=i;
} 如果斜率k不单调递增，那么我们就不能随意删点了，查询我们也需要二分找到那个左边斜率比k小，右边比k大的点。
int find(int k)
{
if(l==r)return q[l];
int L=l,R=r;
while(L<R)
{
int mid=(L+R)/2;
if(f[q[mid+1]]-f[q[mid]]<=k*(sumc[q[mid+1]]-sumc[q[mid]]))L=mid+1;
else R=mid;
}
return q[L];
} 如果斜率k和x不单调递增，我们就要用CDQ维护了。
其实也不是CDQ分治，其实就是简单的分治。
#2483. 「CEOI2017」Building Bridges
由于x不单调，就是要动态插入点，平衡树？不存在的。 我们排序就好了，按x排序。 但这样就会出现，原先j更新i，现在j在i的后面。 不过没事，我们可以分治，就是按原序列分治。 因为我们可以用左一半的凸壳来更新右一半。
void solve(int L,int R)
{
if(L==R){Y[L]+=f[L];return;}
int mid=(L+R)/2;
solve(L,mid);
for(int i=L;i<=R;i++)p[i]=i;
sort(p+L,p+R+1,cmp);
l=1,r=0;
for(int i=L;i<=R;i++)
if(p[i]<=mid)
{
while(l<r&&suan(q[r-1],q[r])>=suan(q[r],p[i]))r--;
q[++r]=p[i];
}
for(int i=L;i<=R;i++)
if(p[i]>mid)
{
while(l<r&&suan(q[l],q[l+1])<=2*h[p[i]])l++;
f[p[i]]=min(f[p[i]],f[q[l]]+(h[p[i]]-h[q[l]])*(h[p[i]]-h[q[l]])+w[p[i]-1]-w[q[l]]);
}
solve(mid+1,R);
} 11.决策单调性优化DP
简单来说就是转移方程有函数性。往往和wps二分一起。
有两种解决方法，二分栈和分治。
对于每个，把
看成关于
的函数
。我们要做的就是在所有
的函数中找到最值。
sqrt的增速是递减的，因此可能存在一个j比较小的函数，在某一时刻被j比较大的函数反超。我们大概需要维护这样的若干个函数：
二分栈：
int erfen(int x,int y)
{
int l=y,r=k[x]?k[x]:n,mid,ret=r+1;
while(l<=r)
{
mid=(l+r)/2;
if(suan(mid,x)<=suan(mid,y)){ret=mid,r=mid-1;}
else l=mid+1;
}
return ret;
}
void work()
{
int l=1,r=0;
for(int i=1;i<=n;i++)
{
while(l<r&&suan(k[r-1],q[r])<suan(k[r-1],i))r--;
k[r]=erfen(q[r],i);
q[++r]=i;
while(l<r&&k[l]<=i)l++;
p[i]=max(p[i],suan(i,q[l]));
}
} 分治：
因为f[i]的最优决策点g[i]是单调递增的 solve(l,r,L,R)表示f[l]~f[r]的最优决策点在L~R 令mid=（l+r）/2 O（n）扫一遍取到k[mid] 继续分治 solve（l,mid-1,L,k[mid]) solve (mid+1,r,k[mid],R)
void solve1(int l,int r,int L,int R)
{
if(l>r)return;
int mid=(l+r)/2,g=0;
double tmp=0.0;
f1[mid]=a[mid];
for(int i=L;i<=min(R,mid);i++)
{
tmp=a[i]+sqrt(double(mid-i));
if(tmp>f1[mid])
{
f1[mid]=tmp;
g=i;
}
}
if(g==0)g=mid;
f1[mid]-=a[mid];
solve1(l,mid-1,L,g);
solve1(mid+1,r,g,R);
} 看另一种方程：
往往有函数性。
可以是前缀和，
但
所以就好像是一些斜向上的函数线（增速递增，由于对于一个固定的,
每大1,函数值就大很多）
inline int suan(int x,int y)
{
int l=y+1,r=n,res=n+1;
while(l<=r)
{
int mid=(l+r)/2;
if(dp[x][k-1]+gao(x,mid)>=dp[y][k-1]+gao(y,mid))
{
res=mid;
r=mid-1;
}
else l=mid+1;
}
return res;
}
for(k=1;k<=K;k++)
{
int L=1,R=1;q[L]=0;
for(int i=1,j;i<=n;i++)
{
while(L<R&&suan(q[L],q[L+1])<=i)L++;
j=q[L];
dp[i][k]=dp[j][k-1]+gao(j,i);
while(L<R&&suan(q[R-1],q[R])>=suan(q[R],i))R--;
q[++R]=i;
}
} 12.插头DP(轮廓线DP)
由于要维护连通性，所以不能用0/1来表示一个位置是否有插头，我们要用0（没有），1（起点插头），2（终点插头），来表示。
1.这个点不能填。
2.没有左，上插头，填成右下插头，下是起点，右是终点。
3.有上没左，向下延续或向右拐弯，插头种类不变。
4.有左没上，向右延续或向下拐弯，插头种类不变。
5.左终点上起点，直接相连。
6.左起点上起点，相连并将向右的和上匹配的终点插头改成起点插头。
7.左终点上终点，相连并将向左的和左匹配的起点插头改成终点插头。
8.左起点上终点，只有可能是最后一个格子，判一下即可。
void solve()
{
add(0,1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
last=now;
now^=1;
cnt[now]=0;
memset(head,0,sizeof(head));
for(int k=1;k<=cnt[last];k++)
{
node st=unpack(s[k].st[last]);
int num=s[k].num[last];
int zuo=st.s[0],shang=st.s[j];
if(!mp[i][j])
{
if((!zuo)&&(!shang))add(make(st),num);//不填
goto xjh;
}
if((!zuo)&&(!shang))//左和上都没，那么一定填右和下
{
if(mp[i+1][j]&&mp[i][j+1])
{
st.s[0]=2;
st.s[j]=1;
add(make(st),num);
}
goto xjh;
}
if((!zuo)&&shang)//上有左没有
{
if(mp[i+1][j])add(make(st),num);//往下延续
if(mp[i][j+1])//向右转弯
{
st.s[0]=shang;
st.s[j]=0;
add(make(st),num);
}
goto xjh;
}
if(zuo&&(!shang))//左有上没有
{
if(mp[i][j+1])add(make(st),num);//往右延续
if(mp[i+1][j])//向下转弯
{
st.s[0]=0;
st.s[j]=zuo;
add(make(st),num);
}
goto xjh;
}
if(zuo==2&&shang==1)//左终点上起点，直接相连，相当于去掉这两个点
{
st.s[0]=st.s[j]=0;
add(make(st),num);
goto xjh;
}
if(zuo==1&&shang==1)//左起点上起点，找到右边的终点，让它变成起点，去掉这两个点
{
int gs=1,pos;
for(pos=j+1;pos<=m;pos++)
{
if(st.s[pos]==1)gs++;
else if(st.s[pos]==2)gs--;
if(!gs)break;
}
st.s[pos]=1;
st.s[0]=st.s[j]=0;
add(make(st),num);
goto xjh;
}
if(zuo==2&&shang==2)//左终点上终点，找到左边的起点，让它变成终点，去掉这两个点
{
int gs=-1,pos;
for(pos=j-1;pos;pos--)
{
if(st.s[pos]==1)gs++;
else if(st.s[pos]==2)gs--;
if(!gs)break;
}
st.s[pos]=2;
st.s[0]=st.s[j]=0;
add(make(st),num);
goto xjh;
}
if(zuo==1&&shang==2)//只有一种情况成立，即是最后一个要填的格子
{
st.s[0]=st.s[j]=0;
bool flag=0;
for(int pos=1;pos<=m;pos++)
{
if(st.s[pos])
{
flag=1;
break;
}
}
if(!flag&&i==edx&&j==edy)
ans+=num;
}
xjh:;
}
}
}
} 13.动态DP
树剖好理解，每个节点都只维护轻儿子的信息，重儿子可以用树剖维护。
写出状态转移后，把转移搞成矩阵的形式（好转移），每次修改就修改每条重链顶端的父亲。
讲一下流程，每个点记录这个点的轻儿子们的所有F[0/1] 然后树剖维护每个点的值，每个点真实的值就是每个点的 点权+所在重链上的其他点的点权 修改一个点，会对上面log个点的点权发生变化，一个个修改过去即可。 答案就 是根节点所在的重链的权值之和，相当于乘上[0,0]
struct node{
int g[2][2];
}c,val[N],tree[N*4];
node operator + (node a,node b)
{
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)c.g[i][j]=0;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)c.g[i][j]=max(c.g[i][j],a.g[i][k]+b.g[k][j]);
return c;
}
void dfs(int u,int fat)
{
fa[u]=fat;size[u]=1;f[u][0]=0;f[u][1]=a[u];
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fat)continue;
dfs(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
f[u][0]+=max(f[v][0],f[v][1]);
f[u][1]+=f[v][0];
}
}
void dfs2(int u,int fat)
{
if(son[u])
{
rev[++seg[0]]=son[u];
seg[son[u]]=seg[0];
top[son[u]]=top[u];
dfs2(son[u],u);
}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(!top[v])
{
rev[++seg[0]]=v;
seg[v]=seg[0];
top[v]=v;
dfs2(v,u);
}
}
}
void build(int nod,int l,int r)
{
if(l==r)
{
int u=rev[l],g0=0,g1=a[u];
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa[u]||v==son[u])continue;
g0+=max(f[v][0],f[v][1]);
g1+=f[v][0];
}
val[u].g[0][0]=val[u].g[0][1]=g0;
val[u].g[1][0]=g1;
tree[nod]=val[u];
return;
}
int mid=(l+r)/2;
build(nod*2,l,mid);
build(nod*2+1,mid+1,r);
tree[nod]=tree[nod*2]+tree[nod*2+1];
}
node query(int nod,int l,int r,int L,int R)
{
if(l==L&&r==R)return tree[nod];
int mid=(l+r)/2;
if(R<=mid)return query(nod*2,l,mid,L,R);
else if(L>mid)return query(nod*2+1,mid+1,r,L,R);
else return query(nod*2,l,mid,L,mid)+query(nod*2+1,mid+1,r,mid+1,R);
}
node find(int x)
{
return query(1,1,n,L[top[x]],R[top[x]]);
}
void change(int nod,int l,int r,int x)
{
if(l==r)
{
tree[nod]=val[rev[l]];
return;
}
int mid=(l+r)/2;
if(x<=mid)change(nod*2,l,mid,x);
else change(nod*2+1,mid+1,r,x);
tree[nod]=tree[nod*2]+tree[nod*2+1];
}
void update(int x)
{
while(x)
{
node od=find(x);
change(1,1,n,seg[x]);
node nw=find(x);
int u=fa[top[x]];
val[u].g[0][0]=val[u].g[0][0]-max(od.g[0][0],od.g[1][0])+max(nw.g[0][0],nw.g[1][0]);
val[u].g[1][0]=val[u].g[1][0]-od.g[0][0]+nw.g[0][0];
val[u].g[0][1]=val[u].g[0][0];
x=u;
}
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs(1,0);
top[1]=rev[1]=seg[0]=seg[1]=1;
dfs2(1,0);
for(int i=1;i<=n;i++)L[top[i]]=n;
for(int i=1;i<=n;i++)
{
L[top[i]]=min(L[top[i]],seg[i]);
R[top[i]]=max(R[top[i]],seg[i]);
}
build(1,1,n);
while(m--)
{
int x=read(),y=read();
val[x].g[1][0]=val[x].g[1][0]-a[x]+y;
a[x]=y;
update(x);
node u=find(1);
printf("%d\n",max(u.g[0][0],u.g[1][0]));
}
return 0;
} 7.数据结构
1.树状数组
树状数组二分：二进制一位一位考虑过去，不需要真的一半。
2.线段树
线段树上二分：先判一边，行就去，不行，去另一边。
权值线段树：下标为权值
动态开点线段树：权值线段树的一种，有些权值（太大）没出现就用动态开点
李超线段树：
对整个横坐标建线段树，每个节点的值存的是一条直线的编号。
要求这条直线在横坐标为mid的时候纵坐标最大。
插入：
如果是叶子节点，我们直接保留最大的。
先比较斜率，再比较横坐标为mid时的纵坐标。
如果新线段的斜率大，并且横坐标为mid时的纵坐标大，那么把原线段下放左区间，节点值改为x
如果新线段的斜率大，但是横坐标为mid时的纵坐标小，那么把新线段下放右区间，不更改节点值
如果新线段的斜率小，但是横坐标为mid时的纵坐标大，那么把原线段下放右区间，节点值改为x
如果新线段的斜率小，并且横坐标为mid时的纵坐标小，那么把新线段下放左区间，不更改节点值
double f(int w,int x)
{
return k[w]*(x-1)+b[w];
}
void change(int nod,int l,int r,int x)
{
if(l==r)
{
if(f(x,l)>f(tree[nod],l))tree[nod]=x;
return;
}
int mid=(l+r)/2;
if(k[tree[nod]]<k[x])
{
if(f(x,mid)>f(tree[nod],mid))
{
change(nod*2,l,mid,tree[nod]);
tree[nod]=x;
}
else change(nod*2+1,mid+1,r,x);
}
if(k[tree[nod]]>k[x])
{
if(f(x,mid)>f(tree[nod],mid))
{
change(nod*2+1,mid+1,r,tree[nod]);
tree[nod]=x ;
}
else change(nod*2,l,mid,x) ;
}
} 查询：
如果是叶子节点直接返回横坐标的值。
如果查询区间在左区间，返回当前的节点的横坐标的值 和 左区间的值 的最大值
如果查询区间在右区间，返回当前的节点的横坐标的值 和 右区间的值 的最大值
double query(int nod,int l,int r,int x)
{
if(l==r)return f(tree[nod],x);
int mid=(l+r)/2;
if(x<=mid)return max(f(tree[nod],x),query(nod*2,l,mid,x));
else return max(f(tree[nod],x),query(nod*2+1,mid+1,r,x));
} P4254 [JSOI2008]Blue Mary开公司(直线)
3.字典树
可持久化字典树：
4.平衡树
普通平衡树：P3369 【模板】普通平衡树
bool chk(int x)
{
return ch[fa[x]][1]==x;
}
void Zhuan(int x)
{
int y=fa[x],z=fa[y],k=chk(x),w=ch[x][k^1];
ch[y][k]=w;fa[w]=y;
ch[z][chk(y)]=x;fa[x]=z;
ch[x][k^1]=y;fa[y]=x;
pushup(y);pushup(x);
}
void splay(int x,int gen=0)
{
while(fa[x]!=gen)
{
int y=fa[x],z=fa[y];
if(z!=gen)
{
if(chk(x)==chk(y))Zhuan(y);
else Zhuan(x);
}
Zhuan(x);
}
if(!gen)root=x;
} 文艺平衡树：就是把下标当成值，注意要多插入0和n+1。维护的值和平衡树的值没有任何关系。
https://www.luogu.org/record/17135871 用文艺平衡树代替线段树。
维护区间加，对于，我们把l-1转成根，把r+1转成根的右儿子，现在的区间
就在根的右儿子的左儿子。
ETT：树，支持将一个节点换一个父亲，子树加，求一个点到根路径的和。
考虑欧拉序，换父亲就是一段括号集体换个位置，我们可以用文艺平衡树来实现。
展示没用自己的写法实现过，先贴别人的吧。
void pushup(int x)
{
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
size[x]=size[ch[x][0]]+size[ch[x][1]]+mark[x];
}
void pushdown(int x){
if(x&&fa[x])pushdown(fa[x]);
if(!x||!lazy[x])return ;
lazy[ch[x][0]]+=lazy[x],lazy[ch[x][1]]+=lazy[x];
val[ch[x][0]]+=lazy[x]*mark[ch[x][0]],val[ch[x][1]]+=lazy[x]*mark[ch[x][1]];
sum[ch[x][0]]+=(long long)size[ch[x][0]]*lazy[x],sum[ch[x][1]]+=(long long)size[ch[x][1]]*lazy[x];
lazy[x]=0;
}
int chk(int x)
{
return ch[fa[x]][1]==x;
}
void Zhuan(int x,int d)
{
int y=ch[x][d^1];
ch[x][d^1]=ch[y][d];
if(ch[x][d^1])fa[ch[x][d^1]]=x;
fa[y]=fa[x];
if(fa[x])ch[fa[x]][chk(x)]=y;
fa[x]=y;ch[y][d]=x;
pushup(x),pushup(y);
}
void splay(int x,int gen=0)
{
pushdown(x);
while(fa[x]!=gen)
{
int y=fa[x],z=fa[y];
if(z!=gen)
{
if(chk(y)==chk(x))Zhuan(z,chk(x)^1);
}
Zhuan(y,chk(x)^1);
}
}
int findl(int x)
{
splay(x);
x=ch[x][0];
while(ch[x][1])x=ch[x][1];
return x;
}
int findr(int x)
{
splay(x);
x=ch[x][1];
while(ch[x][0])x=ch[x][0];
return x;
}
int build(int l,int r)
{
if(l>r)return 0;
int mid=(l+r)/2;
if(l<mid)fa[ch[mid][0]=build(l,mid-1)]=mid;
if(mid<r)fa[ch[mid][1]=build(mid+1,r)]=mid;
val[mid]=(dfn[mid]>0)?a[dfn[mid]]:-a[-dfn[mid]];
mark[mid]=(dfn[mid]>0)?1:-1;
pushup(mid);
return mid;
}
void dfs(int x)
{
dfn[l[x]=++tot]=x;
for(int i=head[x];i;i=e[i].next)
dfs(e[i].to);
dfn[r[x]=++tot]=-x;
} 5.树套树
三维偏序：
矩形修改：
6.kd-tree
个人感觉，kd-tree有两个作用，一个是和树套树一样的矩形修改（空间优秀），一个是求平面点对（感觉就是加剪枝的暴力）。
求平面最第K远/近点对距离。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid (l+r)/2
const int N=1e6+5;
int n,k,cmpd,root;
struct node{
int l,r,d[2],mx[2],mn[2];
}t[N];
struct node2{
int dis;
}tmp;
bool operator < (node2 a,node2 b)
{
return a.dis>b.dis;
}
priority_queue<node2>Q;
int sqr(int x)
{
return x*x;
}
bool cmp(node a,node b)
{
if (a.d[cmpd]!=b.d[cmpd])return a.d[cmpd]<b.d[cmpd];
else return a.d[cmpd^1]<b.d[cmpd^1];
}
void pushup(int x)
{
if(t[x].l)
for(int i=0;i<2;i++)
{
t[x].mx[i]=max(t[x].mx[i],t[t[x].l].mx[i]);
t[x].mn[i]=min(t[x].mn[i],t[t[x].l].mn[i]);
}
if(t[x].r)
for(int i=0;i<2;i++)
{
t[x].mx[i]=max(t[x].mx[i],t[t[x].r].mx[i]);
t[x].mn[i]=min(t[x].mn[i],t[t[x].r].mn[i]);
}
}
int build(int l,int r,int D)
{
cmpd=D;
nth_element(t+l+1,t+mid,t+r+1,cmp);
if(l<mid)t[mid].l=build(l,mid-1,D^1);
if(r>mid)t[mid].r=build(mid+1,r,D^1);
t[mid].mn[0]=t[mid].mx[0]=t[mid].d[0];
t[mid].mn[1]=t[mid].mx[1]=t[mid].d[1];
pushup(mid);
return mid;
}
int dis(int x,int y)
{
return max(sqr((t[x].d[0]-t[y].mn[0])),sqr(t[x].d[0]-t[y].mx[0]))+
max(sqr(t[x].d[1]-t[y].mn[1]),sqr(t[x].d[1]-t[y].mx[1]));
}
int getdis(int x,int y)
{
return sqr(t[x].d[0]-t[y].d[0])+sqr(t[x].d[1]-t[y].d[1]);
}
void query(int u)
{
int dl=0,dr=0,dd=getdis(0,u);
if(dd>Q.top().dis)
{
Q.pop();
tmp.dis=dd;
Q.push(tmp);
}
if(t[u].l)dl=dis(0,t[u].l);
if(t[u].r)dr=dis(0,t[u].r);
tmp=Q.top();
if(dl>dr)
{
if(dl>tmp.dis)query(t[u].l);
tmp=Q.top();
if(dr>tmp.dis)query(t[u].r);
}
else{
if(dr>tmp.dis)query(t[u].r);
tmp=Q.top();
if(dl>tmp.dis)query(t[u].l);
}
}
signed main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)scanf("%lld%lld",&t[i].d[0],&t[i].d[1]);
root=build(1,n,0);
tmp.dis=0;
for(int i=1;i<=k*2;i++)Q.push(tmp);
for(int i=1;i<=n;i++)
{
t[0].d[0]=t[i].d[0];
t[0].d[1]=t[i].d[1];
query(root);
}
printf("%lld",Q.top().dis);
return 0;
} 这是矩形修改（我还不会，抄了发孔爷的代码）
bool cmp(int a,int b)
{
return val[a][K]<val[b][K];
}
void pushup(int u)
{
add[u]=0;mul[u]=1;
for(int i=0;i<=1;i++)
{
L[u][i]=min(val[u][i],min(L[ls][i],L[rs][i]));
R[u][i]=max(val[u][i],max(R[ls][i],R[rs][i]));
}
}
void build(int &u,int l,int r,int k)
{
if(l>r)return;
int mid=(l+r)/2;
K=k;
sort(t+l,t+r+1,cmp);
u=t[mid];
build(ls,l,mid-1,k^1);
build(rs,mid+1,r,k^1);
pushup(u);
}
void pushdown(int u)
{
if(mul[u]!=1)
{
(sum[ls]*=mul[u])%=mod;
(sum[rs]*=mul[u])%=mod;
(mul[ls]*=mul[u])%=mod;
(mul[rs]*=mul[u])%=mod;
(add[ls]*=mul[u])%=mod;
(add[rs]*=mul[u])%=mod;
mul[u]=1;
}
if(add[u]!=0)
{
(sum[ls]+=add[u])%=mod;
(sum[rs]+=add[u])%=mod;
(add[ls]+=add[u])%=mod;
(add[rs]+=add[u])%=mod;
add[u]=0;
}
}
bool xu,jia,hao;
void check(int u)
{
xu=jia=hao=true;
for(int i=0;i<=1;i++)
if(x[i]>L[u][i]||R[u][i]>y[i])
{
xu=false;
if(x[i]>val[u][i]||val[u][i]>y[i])
{
jia=false;
if(x[i]>R[u][i]||y[i]<L[u][i])hao=false;
}
}
}
void Add(int u)
{
if(!u)return;
check(u);
if(!hao)return;
if(jia)
{
if(opt==1)(sum[u]+=tmp)%=mod;
else(sum[u]*=tmp)%=mod;
}
if(xu)
{
if(opt==1)(add[u]+=tmp)%=mod;
else{
(add[u]*=tmp)%=mod;
(mul[u]*=tmp)%=mod;
}
return ;
}
pushdown(u);
Add(ls);
Add(rs);
}
void find(int u,int v)
{
if(!u)return;
if(val[v][0]<L[u][0]||val[v][0]>R[u][0]||val[v][1]<L[u][1]||val[v][1]>R[u][1])return;//不在这个区间
if(u==v)
{
printf("%lld\n",sum[u]);
return ;
}
pushdown(u);
find(ls,v);
find(rs,v);
} 8.线性做法
1.单调队列
2.尺取法
3.单调栈
求最大全0/1矩阵面积
我们维护每个点向左，向右，向上最多能扩展到哪。
求面积的时候，我们只有在上面顶住的时候才算面积（很好理解的）
for(int i=1;i<=n;i++)
for(int j=2;j<=m;j++)
if(a[i][j]==1&&a[i][j-1]==1)l[i][j]=l[i][j-1];
for(int i=1;i<=n;i++)
for(int j=m-1;j>0;j--)
if(a[i][j]==1&&a[i][j+1]==1)r[i][j]=r[i][j+1];
for(int i=2;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==1&&a[i-1][j]==1)
{
h[i][j]=h[i-1][j]+1;
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(a[i][j]==1)
ans=max(ans,h[i][j]*(r[i][j]-l[i][j]+1)); 根据障碍格来求的最大矩阵
维护每个点向右的矩阵，当然向左也要。
然后还有一种特殊情况就是，按y排序后相邻两个的矩形。
for(int i=1;i<=n;i++)a[i]=(node){read(),read()};
a[++n]=(node){0,0};
a[++n]=(node){0,w};
a[++n]=(node){l,0};
a[++n]=(node){l,w};
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
{
int U=w,D=0,L=a[i].x;
for(int j=i+1;j<=n;j++)
{
ans=max(ans,(a[j].x-L)*(U-D));
if(a[j].y>=a[i].y)U=min(U,a[j].y);
else D=max(D,a[j].y);
}
}
for(int i=n;i;i--)
{
int U=w,D=0,R=a[i].x;
for(int j=i-1;j;j--)
{
ans=max(ans,(R-a[j].x)*(U-D));
if(a[j].y>=a[i].y)U=min(U,a[j].y);
else D=max(D,a[j].y);
}
}
sort(a+1,a+n+1,cmp2);
for(int i=1;i<n;i++)
ans=max(ans,l*(a[i+1].y-a[i].y)); 4.长链剖分
用于维护长度的题目。比如：求一个最大的连通块大小，联通块直径不超过
题目：
一颗个点的树，要给每个点染一个颜色，要求任意两个距离小于等于
的点颜色不同，问最少的颜色数。
众所周知 树上距离小于等于k的点连成的图是一张弦图（所以可以直接用完美消除序列(bfs序)+点分树）
众所周知 弦图最小染色数等于最大团
于是问题变成，求一个连通块，直径不超过。
表示
的子树内，强制选
，深度为
的最大值
根据套路，考虑长链剖分。
我们把取前缀max，维护深度不超过
的最大值。
因为取过前缀max，所以在可行的情况下，另一边长度越长越好，
也就是最长的位置要么就是卡到长度为，要么就是卡到那条链的底端，要么就是不能超过当前更新的长度
记的最长深度为
,三种情况分类:
1.，
可能会小于
2.且
，那么转移肯定从
处转
3.且
，那么转移肯定从
处转
发现中间部分相当于一个区间加，只需要打一个全局的即可
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
#define int long long
const int N=1e6+5;
int n,m,ans,son[N],dis[N],tag[N];
int dp[N],*id=dp,*f[N];
vector<int>g[N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return-ret;return ret;
}
void dfs(int u,int fa)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(v==fa)continue;
dfs(v,u);
if(dis[v]+1>dis[u])
{
dis[u]=dis[v]+1;
son[u]=v;
}
}
}
void solve(int u,int fa)
{
f[u]=id++;
if(son[u])
{
solve(son[u],u);
tag[u]=tag[son[u]];
}
f[u][0]=-tag[u];
tag[u]++;//多了点u
int len=min(dis[u],m);
for(int j=0;j<g[u].size();j++)
{
int v=g[u][j];
if(v==fa||v==son[u])continue;
solve(v,u);
int d=min(dis[v],m);
for(int i=0;i<=d;i++)
f[v][i]+=tag[v];
tag[v]=0;
for(int i=d;i>=0;i--)//注意k<=i
{
int k=min(i,m-i);
int x=f[u][i]+(k>0?f[v][k-1]:0);
int y=f[u][k]+(i>0?f[v][i-1]:0);
f[u][i]=max(x,y);
}
//x<=d，x可能会小于y+1
int lim=max(d,m-d-1);
tag[u]+=f[v][d];
//x>d且x+d<=m，那么转移肯定从d处转
for(int i=0;i<=d;i++)f[u][i]-=f[v][d];
for(int i=lim+1;i<=len;i++)f[u][i]-=f[v][d];
for(int i=lim+1;i<=len;i++)
if(m-i-1>=0)f[u][i]+=f[v][m-i-1];
//x>d且x+d>m，那么转移肯定从m-x-1处转
for(int i=1;i<=d;i++)f[u][i]=max(f[u][i-1],f[u][i]);
for(int i=lim+1;i<=len;i++)f[u][i]=max(f[u][i-1],f[u][i]);
//为啥[d+1,m-d-1]不用取max呢
//因为都是加了f[v][d]，还是递增的
}
ans=max(ans,f[u][len]+tag[u]);
}
signed main()
{
freopen("rs.in","r",stdin);
freopen("rs.out","w",stdout);
n=read();m=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0);
solve(1,0);
cout<<ans;
return 0;
}
5.单调性
6.并查集
9.字符串
1.hash
2.kmp
求最长的前缀等于后缀。
void pre()
{
int j=0;
p[1]=0;
for(int i=1;i<m;i++)
{
while(j>0&&b[j+1]!=b[i+1]) j=p[j];
if(b[j+1]==b[i+1]) j++;
p[i+1]=j;
}
}
void kmp()
{
int j=0;
for(int i=0;i<n;i++)
{
while(j>0&&b[j+1]!=a[i+1]) j=p[j];
if(b[j+1]==a[i+1]) j++;
if(j==m)
{
printf("%d\n",i+1-m+1);
j=p[j];
}
}
} 3.ac自动机
多模式串匹配
void make(string s,int k)
{
int u=1,len=s.size();
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
if(!ch[u][c])
{
ch[u][c]=++cnt;
memset(ch[cnt],0,sizeof(ch[cnt]));
}
u=ch[u][c];
}
bo[u]=k;
}
void bfs()
{
int l=1,r=1;
q[1]=1;nxt[1]=0;
while(l<=r)
{
int u=q[l++];
for(int i=0;i<26;i++)
{
if(!ch[u][i])ch[u][i]=ch[nxt[u]][i];
else{
q[++r]=ch[u][i];
nxt[ch[u][i]]=ch[nxt[u]][i];
}
}
}
}
void find(string s)
{
int u=1,len=s.size(),c,k;
for(int i=0;i<len;i++)
{
c=s[i]-'a';
k=ch[u][c];
while(k>1)
{
ans[bo[k]]++;
k=nxt[k];
}
u=ch[u][c];
}
} 有重复模式串的多重匹配 。
每次跳nxt，然后把结尾的所有串加一，妥妥的T。
转化一下建出一颗nxt树，链加，子树求和，直接树上差分。
void dfs(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
dfs(v);
size[u]+=size[v];
}
}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
{
scanf("%s",s);
int m=strlen(s);
int u=1;
for(int j=0;j<m;j++)
{
int c=s[j]-'a';
if(!ch[u][c])ch[u][c]=++cnt;
u=ch[u][c];
}
match[i]=u;
}
for(int i=0;i<26;i++)ch[0][i]=1;
queue<int>q;
q.push(1);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=0;i<26;i++)
{
if(ch[u][i])
{
nxt[ch[u][i]]=ch[nxt[u]][i];
q.push(ch[u][i]);
}
else ch[u][i]=ch[nxt[u]][i];
}
}
scanf("%s",s);
int m=strlen(s);
int u=1;
for(int i=0;i<m;i++)
{
u=ch[u][s[i]-'a'];
size[u]++;
}
for(int i=2;i<=cnt;i++)g[nxt[i]].push_back(i);
dfs(1);
for(int i=1;i<=n;i++)printf("%d\n",size[match[i]]);
return 0;
} 4.sam(sa)
个人感觉sam虽然裸，但不好学，不是有深入了解的话建议别写。
sa就比较好懂了（扩展），往往要和线段树或主席树一起用。
void SA(int n,int m)
{
int p=0;
for(int i=1;i<=m;i++)c[i]=0;
for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
for(int i=1;i<=m;i++)c[i]+=c[i-1];
for(int i=n;i;i--)sa[c[x[i]]--]=i;
for(int i=1;i;i=i*2)
{
p=0;
for(int j=n-i+1;j<=n;j++)y[++p]=j;
for(int j=1;j<=n;j++)
if(sa[j]>i)y[++p]=sa[j]-i;
for(int j=1;j<=m;j++)c[j]=0;
for(int j=1;j<=n;j++)c[x[y[j]]]++;
for(int j=1;j<=m;j++)c[j]+=c[j-1];
for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
swap(x,y);
x[sa[1]]=1;
p=2;
for(int j=2;j<=n;j++)
if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i])x[sa[j]]=p-1;
else x[sa[j]]=p++;
if(p>n)return;
m=p;
}
}
void Height()
{
int k=0;
for(int i=1;i<=n;i++)rk[sa[i]]=i;
for(int i=1;i<=n;i++)
{
if(rk[i]==1)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;
height[rk[i]]=k;
}
}
void ST()
{
memset(st,0x3f,sizeof(st));
for(int i=1;i<=n;i++)st[i][0]=height[i];
for(int i=1;i<=18;i++)
for(int j=1;j<=n;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
int L=l,R=r;
l=min(rk[L],rk[R])+1;
r=max(rk[L],rk[R]);
int k=Log[r-l+1];
return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main()
{
scanf("%s",a+1);
n=strlen(a+1);
Log[0]=-1;
for(int i=1;i<=n;i++)Log[i]=Log[i/2]+1;
SA(n,233);
Height();
ST();
m=read();
while(m--)
{
int l=read(),r=read();
printf("%d\n",query(l,r));
}
return 0;
} 10.数学
1.质数
2.gcd
关于的不定方程
有整数解的充要条件是
scanf("%d",&n);
int ans;
scanf("%d",&ans);
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
ans=__gcd(ans,x);
}
cout<<abs(ans); 3.exgcd
从可以推出
由于都可以除
，所以最小的
就是
，最小
同理
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(b==0){d=a;x=1;y=0;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
} 4.bsgs
把x换一下，
移项得:
取
int kuai(int a,int b)
{
int res=1;
while(b)
{
if(b%2==1)res=res*a%mod;
a=a*a%mod;
b=b/2;
}
return res;
}
int bsgs(int a,int b,int p)
{
a%=p;b%=p;
if(!a&&!b)return 1;
if(!a||!b)return 0;
int m=ceil(sqrt(p)),tmp=1;
mp[b]=0;
for(int i=1;i<=m;i++)
{
tmp=tmp*a%p;
if(!mp[tmp*b%p])mp[tmp*b%p]=i;
}
int t=1;
for(int i=1;i<=m;i++)
{
t=t*tmp%p;
if(mp[t])
{
int ans=i*m-mp[t];
return(ans%p+p)%p;
}
}
} 5.crt
参考题解:中国剩余定理 && 扩展中国剩余定理
注意：快速乘
假设已经求出前k-1个方程组成的同余方程组的一个解为x。
且有
则前k-1个方程的通解为
那么加入第k个方程后,我们就是要求一个正整数t，使得
转化一下式子
对于这个式子我们就可以通过扩欧求解t
若该同余式无解，则整个方程组无解
若有，则前k个同余式组成的方程组的一个解为
int kuai(int a,int b,int mod)
{
if(b==0)return 0;
if(b==1)return a;
int x=kuai(a,b/2,mod);
if(b%2==0)return(x+x)%mod;
else return(x+x+a)%mod;
}
void exgcd(int a,int b,int &d,int &x,int &y)
{
if(b==0){d=a;x=1;y=0;}
else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int excrt()
{
int M=m[1],ans=a[1];
for(int i=2;i<=n;i++)
{
int A=M,B=m[i],C=a[i]-ans;
exgcd(A,B,d,X,Y);
ans+=M*kuai(X,(C%B+B)%B/d,B/d);
M=M/d*m[i];
ans=(ans%M+M)%M;
}
return ans;
} 6.lucas
注意：
int kuai(int a,int b)
{
int res=1;
while(b)
{
if(b%2==1)res=res*a%mod;
a=a*a%mod;
b=b/2;
}
return res;
}
int C(int n,int m)
{
if(m>n)return 0;
return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int lucas(int n,int m)
{
if(m==0)return 1;
return C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;
} 7.二次剩余
求： 其中p是一个奇质数。
如果是p=2的话就把0,1带入求解即可。
有二次剩余的条件：
题目：方程的解
while(T--)
{
a=read(),b=read(),p=read();
if(p<=2)
{
if(b%p==0||(a+b+1)%p==0)puts("Yes");
else puts("No");
continue;
}
if(a&1)a+=p;
n=((a*a/4%p-b)%p+p)%p;
if(n==0||kuai(n,(p-1)/2)==1)puts("Yes");
else puts("No");
} 11.分治
1.普通分治(求方案数)
void solve(int l,int r)
{
if(l==r)return;
int mid=(l+r)/2;
solve(l,mid);//左区间自己
solve(mid+1,r);//右区间自己
for(int i=l;i<=mid;i++)//枚举左边
//往往是双指针或数据结构，时间复杂度1/2只log
} 区间异或和异或区间最大值异或区间最小值 （分治+双指针（线段树上二分）+可持久化trie）
void solve(int l,int r)
{
if(l>r)return;
if(l==r)
{
ans=max(a[l],ans);
return;
}
int mid=(l+r)>>1;
int suml=0,maxl=-INF,minl=INF,maxr=-INF,minr=INF,sumr=0;
int pin1,pin2;
for(int i=mid;i>=l;i--)
{
suml^=a[i];
maxl=max(maxl,a[i]);
minl=min(minl,a[i]);
sumarray[i]=suml;
minarray[i]=minl;
maxarray[i]=maxl;
}
for(int i=mid+1;i<=r;i++)
{
sumr^=a[i];
maxr=max(maxr,a[i]);
minr=min(minr,a[i]);
sumarray[i]=sumr;
minarray[i]=minr;
maxarray[i]=maxr;
}
//1.max left min left
trie.clear();
root[mid]=0;
for(int i=mid+1;i<=r;i++)
trie.insert(root[i],root[i-1],sumarray[i],30);
pin1=mid+1;
for(int i=mid;i>=l;i--)
{
while(pin1<=r&&minarray[pin1]>=minarray[i]&&maxarray[pin1]<=maxarray[i])pin1++;
//¸æ·Ç£¬Ã»Ïëµ½£¬Ð´ÁËÏ߶ÎÊ÷É϶þ·Ö£¬×Ô±Õ
int temp=minarray[i]^maxarray[i]^sumarray[i];
ans=max(ans,temp);
if(pin1>mid+1)ans=max(ans,trie.que(root[mid],root[pin1-1],temp));
}
//2.max right min right
trie.clear();
root[mid+1]=0;
for(int i=mid;i>=l;i--)
trie.insert(root[i],root[i+1],sumarray[i],30);
pin1=mid;
for(int i=mid+1;i<=r;i++)
{
while(pin1>=l&&minarray[pin1]>=minarray[i]&&maxarray[pin1]<=maxarray[i])pin1--;
int temp=minarray[i]^maxarray[i]^sumarray[i];
ans=max(ans,temp);
if(pin1<mid)ans=max(ans,trie.que(root[mid+1],root[pin1+1],temp));
}
//3.max left min right
trie.clear();
root[mid]=0;
for(int i=mid+1;i<=r;i++)
trie.insert(root[i],root[i-1],sumarray[i]^minarray[i],30);
pin1=pin2=mid+1;
for(int i=mid;i>=l;i--)
{
while(pin1<=r&&minarray[i]<minarray[pin1])++pin1;
while(pin2<=r&&maxarray[i]>=maxarray[pin2])++pin2;
if(pin1<pin2)
{
int temp=sumarray[i]^maxarray[i];
ans=max(ans,trie.que(root[pin1-1],root[pin2-1],temp));
}
}
//4.max right min left
trie.clear();
root[mid+1]=0;
for(int i=mid;i>=l;i--)
trie.insert(root[i],root[i+1],sumarray[i]^minarray[i],30);
pin1=pin2=mid;
for(int i=mid+1;i<=r;i++)
{
while(pin1>=l&&minarray[i]<minarray[pin1])--pin1;
while(pin2>=l&&maxarray[i]>=maxarray[pin2])--pin2;
if(pin1>pin2)
{
int temp=sumarray[i]^maxarray[i];
ans=max(ans,trie.que(root[pin1+1],root[pin2+1],temp));
}
}
solve(l,mid);
solve(mid+1,r);
return;
} 2.CDQ分治
三维偏序问题。【模板】三维偏序（陌上花开） 数据结构板子题
void solve(int l,int r)//CDQ分治的思想就是算左边对右边的贡献
{
if(l==r)return;
int mid=(l+r)/2;
solve(l,mid);solve(mid+1,r);
int L=l,R=mid+1,tot=l;
while(L<=mid&&R<=r)
{
if(p[L].b<=p[R].b)//将第二维小于的都放到树状数组中
{
add(p[L].c,1);
Q[tot++]=p[L++];
}
else{
Ans[p[R].id]=find(p[R].c);
Q[tot++]=p[R++];
}
}
while(L<=mid)
{
add(p[L].c,1);
Q[tot++]=p[L++];
}
while(R<=r)
{
Ans[p[R].id]=find(p[R].c);
Q[tot++]=p[R++];
}
for(int i=l;i<=mid;i++)add(p[i].c,-1);
for(int i=l;i<=r;i++)p[i]=Q[i];//把第二维也排好序
}
sort(p+1,p+n+1);//排第一维
solve(1,n);//CDQ分治 3.分治FFT
void CDQ_FFT(int *F,int *G,int l,int r)
{
if(l==r)return;
int mid=(l+r)/2;
CDQ_FFT(F,G,l,mid);
for(int i=l;i<=mid;i++)A[i-l]=F[i];
for(int i=0;i<=r-l;i++)B[i]=G[i];
int len=1,bit=0;
while(len<=r-l+1)
{
len=len*2;
bit++;
}
bit--;
work(len,bit);
for(int i=mid-l+1;i<=len;i++)A[i]=0;
for(int i=r-l+1;i<=len;i++)B[i]=0;
ntt(A,len,1);
ntt(B,len,1);
for(int i=0;i<len;i++)A[i]=1ll*A[i]*B[i]%mod;
ntt(A,len,-1);
for(int i=mid+1;i<=r;i++)F[i]=(F[i]+A[i-l])%mod;
CDQ_FFT(F,G,mid+1,r);
} 式子推导就不写了（我也不会）
这部分是每次在
的时候加上就好。
对于后面的自己卷自己，我们需要特别处理。
板子，我们是考虑
对
的贡献。
贡献就是。
如今自己卷自己，发现如果当时，原先的卷法完全可以（因为
）
但当时，由于
还没算出，无法卷。
解决方案：
当做已经算出，先卷进去。然后对于每一个
的区间，由于如今是
都算出了，我们在把之前没算的贡献加回去。
之前没算的贡献就是和
中各任选一个的和（仔细想想为啥是
呢？，注意：递归），
和
的总贡献是
和
，两项加起来是
。把这两段做一个卷积即可。
注意：DP转移式子中是从
开始的，前面写的一些
，其实是
。
void CDQ(int l,int r)
{
if(l==r)
{
f[l]=add(f[l],mul(f[l-1],l-1));
return;
}
int mid=(l+r)/2;
CDQ(l,mid);
if(l>2)
{
int lp=2,rp=min(l-1,r-l),len=1;
while(len<=rp+mid-l)len=len*2;
fill(A,A+len,0);
fill(B,B+len,0);
for(int i=lp;i<=rp;i++)A[i]=f[i];
for(int i=l;i<=mid;i++)B[i-l]=f[i];
NTT(A,len,1);NTT(B,len,1);
for(int i=0;i<len;i++)C[i]=mul(A[i],B[i]);
NTT(C,len,-1);
for(int i=mid+1;i<=r;i++)
f[i]=add(f[i],mul(C[i-l],i-2));
}
int len=1;
while(len<=mid-l+mid-l)len=len*2;
fill(A,A+len,0);
fill(B,B+len,0);
for(int i=l;i<=mid;i++)A[i-l]=f[i];
for(int i=l;i<=mid;i++)B[i-l]=mul(i-1,f[i]);
NTT(A,len,1);NTT(B,len,1);
for(int i=0;i<len;i++)C[i]=mul(A[i],B[i]);
NTT(C,len,-1);
for(int i=mid+1;i<=r;i++)
f[i]=add(f[i],C[i-l-l]);
CDQ(mid+1,r);
} 4.整体二分
整体二分可以和很多东西配，比如并查集。
int find(int x)
{
if(fa[x]==x)return x;
return find(fa[x]);
}
void merge(int x,int y)
{
x=find(x),y=find(y);
if(x==y)return;
if(size[x]>size[y])swap(x,y);
zhan[++tot]=x;
fa[x]=y;
size[y]+=size[x];
}
void Delete()
{
while(tot)
{
int x=zhan[tot];
size[fa[x]]-=size[x];
fa[x]=x;
tot--;
}
}
void solve(int l,int r,int L,int R)
{
// cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
if(L==R)
{
for(int i=l;i<=r;i++)Ans[Q[i].id]=L;
merge(e[L].x,e[L].y);
return;
}
int mid=(L+R)/2;
int LL=l-1,RR=r+1;
tot=0;
for(int i=L;i<=mid;i++)
merge(e[i].x,e[i].y);
for(int i=l;i<=r;i++)
{
int x=find(Q[i].x),y=find(Q[i].y);
if(x==y)
{
if(size[x]>=Q[i].z)xu[++LL]=Q[i];
else xu[--RR]=Q[i];
}
else{
if(size[x]+size[y]>=Q[i].z)xu[++LL]=Q[i];
else xu[--RR]=Q[i];
}
}
for(int i=l;i<=r;i++)Q[i]=xu[i];
Delete();
solve(l,LL,L,mid);
solve(RR,r,mid+1,R);
} 12.矩阵
1.矩阵乘法
2.矩阵乘法优化DP
3.循环矩阵
初始矩阵就是原先矩阵的第一列。
node operator * (node a,node b)
{
for(int i=0;i<k;i++)c.m[i]=0;
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
c.m[(i+j)%k]=(c.m[(i+j)%k]+a.m[i]*b.m[j])%mod;
return c;
}
node kuai(node a,int b)
{
node res;
for(int i=0;i<k;i++)res.m[i]=0;
res.m[0]=1;
while(b)
{
if(b&1)res=res*a;
b=b/2;
a=a*a;
}
return res;
} 题目：
有一个长度为 的环，执行
次操作，在一次操作中，
对于每一个数，它变为它左边的数乘上 以及它本身以及它右边的数乘上
的和。
求最后每一个位置上的数是多少。(计算时左边和右边的数都是上一次的数)
13.点分治
1.统计边
2.点分树
点分树有一个性质：点分树上的两点的LCA，在原树两点的路径上。
所以我们把x-y的路径分成x-点分树上的LCA和点分树上的LCA-y的两条路径。
3.动态点分治
点分树上树高log，由于是二叉树，那么只要和点u在不同儿子那么就能计算答案。
每个节点都维护向下能到哪些点和距离，然后就可以二分了。
void dfs1(int u,int fa)//求出每个点的size
{
size[u]=1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
if(vis[v])continue;
dfs1(v,u);
size[u]+=size[v];
}
}
void dfs2(int u,int fa)//找到重心
{
int mx=sum-size[u];
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
if(vis[v])continue;
dfs2(v,u);
mx=max(mx,size[v]);
}
if(mx<ma){ma=mx,rt=u;}
}
void dfs3(int u,int fat,int g,int t)//维护fa和ans
{
fa[u].push_back((node){g,dep[u],t});
ans[g][t].push_back((Node){a[u],1,dep[u]});
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fat)continue;
if(vis[v])continue;
dep[v]=dep[u]+edge[i].zh;
dfs3(v,u,g,t);
}
}
void solve(int u)
{
dfs1(u,0);
if(size[u]==1)
{
vis[u]=1;
fa[u].push_back((node){u,0,-1});
return;
}
sum=size[u];
ma=0x3f3f3f3f;
dfs2(u,0);
vis[rt]=1;
fa[rt].push_back((node){rt,0,-1});
for(int i=head[rt],t=0;i;i=edge[i].next)
{
int v=edge[i].too;
if(vis[v])continue;
dep[v]=edge[i].zh;
dfs3(v,0,rt,t);
ans[rt][t].push_back((Node){0x3f3f3f3f,0,0});
sort(ans[rt][t].begin(),ans[rt][t].end());
for(int j=ans[rt][t].size()-2;j>=0;j--)
{
ans[rt][t][j].gs+=ans[rt][t][j+1].gs;
ans[rt][t][j].dis+=ans[rt][t][j+1].dis;
}
t++;
}
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].too;
if(vis[v])continue;
solve(v);
}
}
void query(int l,int r,int u)
{
res=0;
vector<Node>::iterator L,R;
for(int i=0;i<fa[u].size();i++)
{
int f=fa[u][i].f;
for(int j=0;j<=2;j++)//由于每个点的度<=3
{
if(j==fa[u][i].id||ans[f][j].empty())continue;
L=lower_bound(ans[f][j].begin(),ans[f][j].end(),(Node){l,0,0});
R=upper_bound(ans[f][j].begin(),ans[f][j].end(),(Node){r,0,0});
res+=fa[u][i].dis*(L->gs-R->gs)+L->dis-R->dis;
}
if(l<=a[f]&&a[f]<=r)res+=fa[u][i].dis;
}
} 动态修改点权，求带权重心。
void Addedge(int u,int v,int w)
{
G[++tot].u=u;G[tot].v=v;G[tot].w=w;G[tot].next=head[u];head[u]=tot;
}
struct node{
int head[N],cnt,tot;
int st[N<<2][21],dis[N],id[N<<1];
struct edge{int u,v,next,w;}E[2*N];
inline void addedge(int u,int v,int w)
{
E[++tot].u=u;E[tot].v=v;E[tot].w=w;E[tot].next=head[u];head[u]=tot;
E[++tot].u=v;E[tot].v=u;E[tot].w=w;E[tot].next=head[v];head[v]=tot;
}
int getdis(int u,int v)
{
if(id[u]>id[v])swap(u,v);
int k=Log[id[v]-id[u]+1];
return dis[u]+dis[v]-2*min(st[id[u]][k],st[id[v]-(1ll<<k)+1][k]);
}
void dfs(int u,int fa)
{
st[++cnt][0]=dis[u];
id[u]=cnt;
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].v;
if(v==fa)continue;
dis[v]=dis[u]+E[i].w;
dfs(v,u);
st[++cnt][0]=dis[u];
}
}
void initrmq()
{
memset(id,0,sizeof(id));
cnt=0;tot=0;dis[1]=0;
dfs(1,0);
for(int j=1;(1ll<<j)<=cnt;j++)
for(int i=1;i+(1ll<<j)-1<=cnt&&i<=cnt;i++)
st[i][j]=min(st[i][j-1],st[i+(1ll<<(j-1))][j-1]);
}
}T;
void getroot(int u,int fa)
{
size[u]=1;
f[u]=0;
for(int i=T.head[u];i;i=T.E[i].next)
{
int v=T.E[i].v;
if(vis[v]||v==fa)continue;
getroot(v,u);
size[u]+=size[v];
f[u]=max(f[u],size[v]);
}
f[u]=max(f[u],sum-size[u]);
if(f[u]<f[rt])rt=u;
}
void work(int u,int fa)
{
vis[u]=1;par[u]=fa;
for(int i=T.head[u];i;i=T.E[i].next)
{
int v=T.E[i].v;
if(vis[v])continue;
sum=size[v];
f[0]=size[v];
rt=0;
getroot(v,0);
Addedge(u,rt,v);
work(rt,u);
}
}
void change(int u,int val)
{
sumv[u]+=val;
for(int i=u;par[i];i=par[i])
{
int dist=T.getdis(par[i],u);
dis1[par[i]]+=dist*val;
dis2[i]+=dist*val;
sumv[par[i]]+=val;
}
}
int calc(int u)
{
int ans=dis1[u];
for(int i=u;par[i];i=par[i])
{
int dist=T.getdis(par[i],u);
ans+=dis1[par[i]]-dis2[i];
ans+=dist*(sumv[par[i]]-sumv[i]);
}
return ans;
}
int query(int u)
{
int ans=calc(u);
for(int i=head[u];i;i=G[i].next)
{
int tmp=calc(G[i].w);
if(tmp<ans)return query(G[i].v);
}
return ans;
} P6329 【模板】点分树 | 震波
点分树最简单的写法就是维护两个数据结构（一般是vector）
一个记录点分树上以点u为根的子树与u的信息（到u的距离）
一个记录点分树上以点u为根的子树与fa[u]的信息（到法fa[u]的距离）
然后就可以通过容斥（减一减），求出在fa[u]的子树中且不在u的子树中的信息（到某某点的距离）
除了这种写法，就要重构树（使度数<=3）了
这题还有一个难点就是这两个数据结构是树状数组
那么就要动态开点（vector），有点麻烦
距离为0的点（本身），树状数组不好处理，我们就先不加入，到要用的时候直接加
#include<bits/stdc++.h>
using namespace std;
#define next Next
//#define gc getchar
//#define int long long
const int N=2e6+5;
int n,m,top,t,sum,rt,lastans,sz[N],fa[N],vis[N],ru[N],id[N],dep[N],a[N];
int head[N],ma[N],Log[N],size[N],st[N][21];
struct node{
int too,next;
}edge[N*2];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
int ret=0,f=0;char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){ret=ret*10+c-48;c=gc();}
if(f)return -ret;return ret;
}
void write(int x)
{
if(x<10){putchar(x+'0');return;}
write(x/10);
putchar(x%10+'0');
}
int lowbit(int x)
{
return x&-x;
}
struct Tree{
vector<int>c;
void init(int n)
{
for(int i=0;i<=n;i++)
c.push_back(0);
}
void change(int x,int y)
{
int n=c.size()-1;
while(x<=n)
{
c[x]+=y;
x+=lowbit(x);
}
}
int find(int x)
{
int res=0;
if(x>c.size()-1)x=c.size()-1;//注意
while(x>0)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
}T1[N],T2[N];
void add(int a,int b)
{
edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void dfs(int u,int fa,int d)
{
ru[u]=++t;
id[t]=u;
dep[t]=d;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa)continue;
dfs(v,u,d+1);
id[++t]=u;
dep[t]=d;
}
}
int LCA(int x,int y)
{
int l=ru[x],r=ru[y];
if(l>r)swap(l,r);
int k=Log[r-l+1];
x=st[l][k];y=st[r-(1<<k)+1][k];
if(dep[x]<=dep[y])return id[x];
return id[y];
//注意LCA是要转化为id的
}
int dis(int x,int y)
{
int lca=LCA(x,y);
return dep[ru[x]]+dep[ru[y]]-2*dep[ru[lca]];
//注意这里的dep[x]是编号为x的点的深度，不是点x的深度
}
void getrt(int u,int fa)
{
ma[u]=0;size[u]=1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(v==fa||vis[v])continue;
getrt(v,u);
size[u]+=size[v];
ma[u]=max(ma[u],size[v]);
}
ma[u]=max(ma[u],sum-size[u]);
if(ma[u]<ma[rt])rt=u;
}
void solve(int u)
{
vis[u]=1;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too;
if(vis[v])continue;
ma[rt=0]=sum=size[v];
getrt(v,0);
fa[rt]=u;
sz[rt]=size[v];//注意rt的大小是size[v]
T1[rt].init(size[v]);//注意不能全开n，否则变n^2
T2[rt].init(size[v]);
solve(rt);
}
}
void work(int x,int y)
{
for(int i=fa[x];i;i=fa[i])
{
int len=dis(x,i);
if(len<=sz[i])T1[i].change(len,y);
}
for(int i=x;i;i=fa[i])
{
if(fa[i]==0)break;
int len=dis(x,fa[i]);
if(len<=sz[i])T2[i].change(len,y);
}
}
signed main()
{
Log[0]=-1;
for(int i=1;i<=200000;i++)Log[i]=Log[i/2]+1;
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs(1,0,0);
for(int i=1;i<=t;i++)st[i][0]=i;
for(int i=1;i<=Log[t];i++)
for(int j=1;j<=t-(1<<i)+1;j++)
{
int x=st[j][i-1],y=st[j+(1<<(i-1))][i-1];
if(dep[x]<=dep[y])st[j][i]=x;
else st[j][i]=y;
}
ma[rt=0]=sum=n;
getrt(1,0);
sz[rt]=n;
T1[rt].init(n);
T2[rt].init(n);
solve(rt);
for(int i=1;i<=n;i++)
work(i,a[i]);
while(m--)
{
int opt=read(),x=read()^lastans,y=read()^lastans;
if(opt==0)
{
int res=T1[x].find(y)+a[x];
//注意为了方便树状数组，没有把距离为0的点放进去
for(int i=x;i;i=fa[i])
{
if(fa[i]==0)break;
int len=dis(x,fa[i]);
if(y-len>=0)
{
res+=T1[fa[i]].find(y-len)+a[fa[i]];
res-=T2[i].find(y-len);
}
}
write(lastans=res);
putchar('\n');
}
else{
work(x,y-a[x]);
a[x]=y;
}
}
return 0;
}
/*
5 1
1 3 5 7 9
1 2
2 3
3 4
3 5
0 2 1
*/
/*
点分树最简单的写法就是维护两个数据结构（一般是vector）
一个记录点分树上以点u为根的子树与u的信息（到u的距离）
一个记录点分树上以点u为根的子树与fa[u]的信息（到法fa[u]的距离）
然后就可以通过容斥（减一减），求出在fa[u]的子树中且不在u的子树中的信息（到某某点的距离）
除了这种写法，就要重构树（使度数<=3）了
这题还有一个难点就是这两个数据结构是树状数组
那么就要动态开点（vector），有点麻烦
*/ 14.图论
1.最短路
2.最小生成树
3.拓扑排序
4.差分约束
条件形如：，我们可以看成
向
连了一条长度为
的有向边，若存在正环则无解。
有源点，就从源点spfa。
void spfa()
{
while(l<=r)
{
int u=q[l++];
vis[u]=false;
cnt[u]++;
if(cnt[u]==n){cout<<-1;exit(0);}
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].too,w=edge[i].zh;
if(dis[v]<dis[u]+w)
{
dis[v]=dis[u]+w;
if(!vis[v])
{
q[++r]=v;
vis[v]=true;
}
}
}
}
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&a,&b);
if(x==1){add(a,b,0);add(b,a,0);}
else if(x==2)add(a,b,1);
else if(x==3)add(b,a,0);
else if(x==4)add(b,a,1);
else if(x==5)add(a,b,0);
if(x%2==0&&a==b)
{
cout<<-1;
return 0;
}
}
l=1;
for(int i=1;i<=n;i++)
{
dis[i]=1;
vis[i]=true;
q[++r]=i;
}
spfa(); 这题没源点，那就每个联通块spfa一次
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
add(x-1,y,z);
add(y,x-1,-z);
}
for(int i=0;i<=n;i++)
if(gs[i]==0)
{
if(!spfa(i))
{
puts("false");
goto xjh;
}
}
puts("true");
xjh:; 5.欧拉回路
只要在dfs时加一个走过的边不走的优化，时间复杂度就是
void dfs(int x)
{
for(int &i=head[x];i;i=edge[i].next)
{
int v=edge[i].too;
if(vis[x][v])continue;
vis[x][v]=vis[v][x]=1;
dfs(v);
}
c[t--]=x;
}
int find(int x)
{
if(fa[x]==x)return x;
fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
scanf("%d",&n);
for(int i=0;i<=500;i++)fa[i]=i;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
g[a][b]=g[b][a]=1;
int xx=find(a),yy=find(b);
fa[xx]=yy;
du[a]++;
du[b]++;
}
for(int i=0;i<=500;i++)
for(int j=500;j>=0;j--)
if(g[i][j])add(i,j);
for(int i=0;i<=500;i++)
if(fa[i]==i&&du[i])k++;
if(k!=1){puts("No Solution");return 0;}
k=0;
for(int i=0;i<=500;i++)
if(du[i]%2==1)
{
k++;
if(!S)S=i;
}
if(S==0)
for(int i=0;i<500;i++)
if(du[i]){S=i;break;}
if(k!=0&&k!=2){puts("No Solution");return 0;}
t=n;
dfs(S);
printf("%c",S);
for(int i=1;i<=n;i++)printf("%c",c[i]);
return 0;
} 6.二分图
P1894 [USACO4.2]完美的牛栏The Perfect Stall
bool find(int x)
{
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].too;
if(!b[v])
{
b[v]=true;
if(!a[v]||find(a[v]))
{
a[v]=x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%d",&x);
add(i,x+n);
}
}
for(int i=1;i<=n;i++)
{
memset(b,false,sizeof(b));
if(find(i))ans++;
}
cout<<ans;
return 0;
} 7.网络流
xuxuxuxuxu 文章被收录于专栏
信息学竞赛
