看到这套题，我的心情是这样的：
膜拜神犇NiroBC屠题+卖萌两不误。
2
11
2016
11
2016
论蒟蒻的花样作死之网络流
谜之声：这里的网络流包括最大流、最小割、费用流、有上下界网络流等。
好吧废话不说直接上模板。
【模板】
int bfs(){
int l=1,r=1;
memset(dis,-1,sizeof dis);
h[1]=S;dis[S]=0;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]<0){
dis[v]=dis[u]+1;
h[++r]=v;
}
}
l++;
}
if (dis[T]<0)return 0;else return 1;
}
int dfs(int u,int aug){
if (u==T)return aug;
int flow=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]==dis[u]+1){
int tmp=dfs(v,min(aug-flow,size[e]));
flow+=tmp;
size[e]-=tmp;
size[e^1]+=tmp;
if (flow==aug)return flow;
}
}
if (!flow)dis[u]=-1;
return flow;
}
int spfa(){
int l=1,r=1;
for (i=0;i<=2*n+1;i++)dis[i]=inf;
dis[S]=0;h[1]=S;rem[S]=inf;flag[S]=1;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
pre[v][0]=u;pre[v][1]=e;
rem[v]=min(rem[u],size[e]);
if (!flag[v]){
flag[v]=1;
h[++r]=v;
}
}
}
l++;
flag[u]=0;
}
if (dis[T]==inf)return 0;
ans+=dis[T]*rem[T];
int u=T;
while (u!=S){
size[pre[u][1]]-=rem[T];
size[pre[u][1]^1]+=rem[T];
u=pre[u][0];
}
return 1;
}
【例题】
BZOJ2756 给你一个n*m的矩阵，每个格子一开始有一个数值，你每次操作可以使相邻两个格子+1，问最少几次操作可以使矩阵上的数相同。
假设已经确定了最后每个格子上的数D，那么黑白染色，源连黑点，白点连汇，流量均为D-a[i][j]，跑最大流看是否满流就知道了是否可行。
那么如何确定D呢？若n*m为奇数，即黑白点个数不同，那么发现：每次操作黑白点点权各+1，即黑白点的点权之差始终相等，那么D就是黑白点权之差。
若n*m为偶数，如果D可行，那么D+1显然可行，所以可以二分。
BZOJ1927 n个点m条边的有向无环图，可以选择瞬移到某个点，代价为点权a[i]，或从某个点走到另一个点，代价为边权b[i]，要求每个点仅经过一次，问最小代价。
类似最小路径覆盖，每个点裂出两个u,u'，源连u，流量为1，费用为0；源连u'，流量为1，费用为a[i]；u连v'，流量为1，费用为b[i]，这样就满足了题目的限制条件。
跑费用流即可。
BZOJ2324 题意太长，请自行搜索。
首先要跑一遍最短路，dis[i][j]表示从i到j(i<j)经过编号小于j的点的最短路，可以用floyed解决。
那么就是k条路径最小覆盖，建图与上题类似，但是没有源到u‘的边，源连0的流量为k。
BZOJ1061 我是传送门
BZOJ1070 n辆车m个维修员，每个维修员修完一辆车的时间均不同，求顾客的平均等待时间。
考虑维修员i修编号为j的车，且该车是倒数第k辆i修的车，那么对答案的贡献就是a[i][j]*k。
那么动态加边，源连维修员，流量为1，费用为0；维修员连车，流量为1，费用为a[i][j]；车连汇，流量为1，费用为0。
如果一个维修员被流过，就新建一个点与所有车连一条边，流量为1，费用为a[i][j]*k。
（由于此题数据范围太小直接暴力加完就行。。。）
BZOJ2879 n个厨师m道菜，每个厨师做一道菜的时间均不同，每道菜要b[i]份，求总等待时间。
与上题类似，菜连汇的流量改成b[i]就可以了。
BZOJ2561 n个点m条边的无向图，给定一条边，问最少删去多少条边使得给定的边既在最小生成树上又在最大生成树上。
考虑kruscal算法，对于边权小于给定边的那些边，若全部加上后u->v仍然不连通，那么给定边一定在最小生成树上。最大生成树同理。
那么只要两次最小割就可以了。
BZOJ1412 n行m列的矩阵，每个格子是狼或羊或空地，要用栅栏将狼与羊隔开，求栅栏的最小周长。
源连狼，流量为inf；羊连汇，流量为inf；格子互相联通，流量为1，跑最小割即可。
BZOJ1497 n个产品，获利为a[i]，需要机器b[i],c[i]完成；每个机器都有一个购置代价w[i]，求最大获利。
源连机器，流量为w[i]，机器连产品，流量为inf；产品连汇，流量为a[i]。求最小割，即要么购置机器，要么放弃获利。答案为获利总和-最小割。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=100010;
const ll inf=1ll<<50;
int cas,n,m,i,j,edgenum;
ll size[M];
int head[M],vet[M],next[M],h[M],dis[M];
int a[50][50];
int u[4]={0,0,-1,1},v[4]={1,-1,0,0};
ll max(ll x,ll y){if (x>y)return x;else return y;}
ll min(ll x,ll y){if (x<y)return x;else return y;}
int point(int x,int y){
return (x-1)*m+y;
}
void addedge(int x,int y,ll ch){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=ch;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
}
void buildgraph(ll x){
int i,j,k;
edgenum=1;
memset(head,0,sizeof head);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if ((i+j)%2)addedge(point(i,j),n*m+2,x-a[i][j]);
else addedge(n*m+1,point(i,j),x-a[i][j]);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (!((i+j)%2)){
for (k=0;k<4;k++){
int x=i+u[k],y=j+v[k];
if (x&&x<=n&&y&&y<=m)addedge(point(i,j),point(x,y),inf*n*m);
}
}
}
int bfs(){
memset(dis,-1,sizeof dis);
int l=1,r=1;
h[1]=n*m+1,dis[n*m+1]=0;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]<0){
dis[v]=dis[u]+1;
h[++r]=v;
}
}
l++;
}
if (dis[n*m+2]<0)return 0;else return 1;
}
ll dfs(int u,ll aug){
if (u==n*m+2)return aug;
ll flow=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]==dis[u]+1){
ll tmp=dfs(v,min(aug-flow,size[e]));
size[e]-=tmp;
size[e^1]+=tmp;
flow+=tmp;
if (flow==aug)return flow;
}
}
if (!flow)dis[u]=-1;
return flow;
}
int main(){
scanf("%d",&cas);
while (cas--){
scanf("%d%d",&n,&m);
ll sum=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
ll D=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if ((i+j)%2)D-=a[i][j];else D+=a[i][j];
if (n%2&&m%2){
buildgraph(D);
ll ans=0;
while (bfs())ans+=dfs(n*m+1,inf*n*m);
if (ans==D*n*m-sum>>1)printf("%lld\n",ans);else puts("-1");
}else{
if (D){puts("-1");continue;}
ll l=0,r=inf;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
l=max(l,a[i][j]);
while (l<r){
ll mid=l+r>>1,ans=0;
buildgraph(mid);
while (bfs())ans+=dfs(n*m+1,inf*n*m);
if (ans==mid*n*m-sum>>1)r=mid;else l=mid+1;
}
printf("%lld\n",l*n*m-sum>>1);
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=2000000000;
int head[M],vet[M],next[M],size[M],len[M],h[M*30],flag[M],dis[M],rem[M],pre[M][2];
int n,m,i,x,y,ch,ans,edgenum;
void addedge(int x,int y,int z,int w){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=z;
len[edgenum]=w;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
len[edgenum]=-w;
}
int spfa(){
int l=1,r=1;
for (i=0;i<=2*n+1;i++)dis[i]=inf;
dis[0]=0;h[1]=0;rem[0]=inf;flag[0]=1;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
pre[v][0]=u;pre[v][1]=e;
rem[v]=min(rem[u],size[e]);
if (!flag[v]){
flag[v]=1;
h[++r]=v;
}
}
}
l++;
flag[u]=0;
}
if (dis[n*2+1]==inf)return 0;
ans+=dis[n*2+1]*rem[n*2+1];
int u=2*n+1;
while (u){
size[pre[u][1]]-=rem[n*2+1];
size[pre[u][1]^1]+=rem[n*2+1];
u=pre[u][0];
}
return 1;
}
int main(){
//freopen("1.out","w",stdout);
edgenum=1;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
scanf("%d",&x);
addedge(0,i,1,0);
addedge(0,i+n,1,x);
addedge(i+n,n*2+1,1,0);
}
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&ch);
if (x>y)swap(x,y);
addedge(x,y+n,1,ch);
}
while (spfa());
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000000;
int n,m,p,i,j,k,x,y,ch,edgenum,ans;
int a[300][300],head[M],vet[M],next[M],flag[M],len[M],size[M],h[M*30],dis[1010],pre[M][2],rem[M];
void addedge(int x,int y,int z,int w){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=z;
len[edgenum]=w;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
len[edgenum]=-w;
}
int spfa(){
int l=1,r=1;
for (i=0;i<=n*2+1;i++)dis[i]=inf;
dis[0]=0;h[1]=0;flag[0]=1;rem[0]=inf;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
pre[v][0]=u;pre[v][1]=e;
rem[v]=min(rem[u],size[e]);
if (!flag[v]){
flag[v]=1;
h[++r]=v;
}
}
}
l++;
flag[u]=0;
}
if (dis[2*n+1]==inf)return 0;
ans+=rem[2*n+1]*dis[2*n+1];
int u=2*n+1;
while (u){
size[pre[u][1]]-=rem[2*n+1];
size[pre[u][1]^1]+=rem[2*n+1];
u=pre[u][0];
}
return 1;
}
int main(){
edgenum=1;
//freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&m,&p);
n++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j]=inf;
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&ch);
x++;y++;
a[x][y]=min(a[x][y],ch);
a[y][x]=min(a[y][x],ch);
}
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=k;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
addedge(0,1,p,0);
for (i=2;i<=n;i++){
addedge(0,i,1,0);
addedge(i+n,n*2+1,1,0);
}
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
if (a[i][j]!=inf)addedge(i,j+n,1,a[i][j]);
while (spfa());
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
const int inf=1000000007;
int n,m,i,x,y,ch,ans,edgenum;
int a[M],head[M],vet[M],next[M],flag[M],size[M],len[M],dis[M],h[M],rem[M],pre[M][2];
void addedge(int x,int y,int z,int w){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=z;
len[edgenum]=w;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
len[edgenum]=-w;
}
int spfa(){
int l=1,r=1;
for (i=0;i<=n+2;i++)dis[i]=inf;
h[1]=0;dis[0]=0;rem[0]=inf;flag[0]=1;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
pre[v][0]=u;pre[v][1]=e;
rem[v]=min(rem[u],size[e]);
if (!flag[v]){
flag[v]=1;
h[++r]=v;
}
}
}
l++;
flag[u]=0;
}
if (dis[n+2]==inf)return 0;
ans+=dis[n+2]*rem[n+2];
int u=n+2;
while (u){
size[pre[u][1]]-=rem[n+2];
size[pre[u][1]^1]+=rem[n+2];
u=pre[u][0];
}
return 1;
}
int main(){
edgenum=1;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
scanf("%d",&a[i]);
addedge(i+1,i,inf,0);
}
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&ch);
addedge(x,y+1,inf,ch);
}
for (i=1;i<=n+1;i++){
int x=a[i]-a[i-1];
if (x>0)addedge(0,i,x,0);
else addedge(i,n+2,-x,0);
}
while (spfa());
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int n,m,i,j,cnt,edgenum,ans;
int a[110][110],head[M],vet[M],next[M],len[M],size[M],flag[M],rem[M],dis[M],h[M<<3],pre[M][2],orz[M],num[M];
void addedge(int x,int y,int z,int w){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=z;
len[edgenum]=w;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
len[edgenum]=-w;
}
int spfa(){
int l=1,r=1;
for (int i=0;i<=cnt;i++)dis[i]=inf;
dis[0]=0;flag[0]=1;rem[0]=inf;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
pre[v][0]=u;pre[v][1]=e;
rem[v]=min(rem[u],size[e]);
if (!flag[v]){
flag[v]=1;
h[++r]=v;
}
}
}
/*printf("%d:",u);
for (int i=0;i<=cnt;i++)printf("%d ",dis[i]);
puts("");*/
l++;
flag[u]=0;
}
if (dis[n+m+1]==inf)return 0;
ans+=dis[n+m+1]*rem[n+m+1];
int u=n+m+1;
while (u){
size[pre[u][1]]-=rem[n+m+1];
size[pre[u][1]^1]+=rem[n+m+1];
if (!pre[u][0]){
orz[++cnt]=orz[u]+1,num[cnt]=num[u];
addedge(0,cnt,1,0);
for (int i=1;i<=m;i++)
addedge(cnt,n+i,1,a[num[cnt]][i]*orz[cnt]);
}
u=pre[u][0];
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
edgenum=1,cnt=n+m+1;
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)scanf("%d",&a[i][j]);
for (i=1;i<=n;i++){
orz[i]=1,num[i]=i;
addedge(0,i,1,0);
for (j=1;j<=m;j++)addedge(i,j+n,1,a[i][j]);
}
for (i=1;i<=m;i++)addedge(n+i,n+m+1,1,0);
while (spfa());
printf("%.2lf\n",(double)ans/m);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int head[M*30],vet[M*30],next[M*30],size[M*30],len[M*30],dis[M],flag[M],rem[M],pre[M][2],a[110][110],h[M*30],orz[M],num[M];
int n,m,i,j,x,edgenum,ans,cnt;
void addedge(int x,int y,int z,int w){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=z;
len[edgenum]=w;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
len[edgenum]=-w;
}
int spfa(){
int l=1,r=1;
for (int i=0;i<=cnt;i++)dis[i]=inf;
dis[0]=0;flag[0]=1;rem[0]=inf;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]>dis[u]+len[e]){
dis[v]=dis[u]+len[e];
pre[v][0]=u;pre[v][1]=e;
rem[v]=min(rem[u],size[e]);
if (!flag[v]){
flag[v]=1;
h[++r]=v;
}
}
}
l++;
flag[u]=0;
}
if (dis[n+m+1]==inf)return 0;
ans+=dis[n+m+1]*rem[n+m+1];
int u=n+m+1;
while (u){
size[pre[u][1]]-=rem[n+m+1];
size[pre[u][1]^1]+=rem[n+m+1];
if (!pre[u][0]){
orz[++cnt]=orz[u]+1,num[cnt]=num[u];
addedge(0,cnt,1,0);
for (int i=1;i<=m;i++)addedge(cnt,i+n,1,a[num[cnt]][i]*orz[cnt]);
}
u=pre[u][0];
}
return 1;
}
int main(){
scanf("%d%d",&m,&n);
edgenum=1;cnt=n+m+1;
for (i=1;i<=m;i++){
scanf("%d",&x);
addedge(i+n,n+m+1,x,0);
}
for (j=1;j<=m;j++)
for (i=1;i<=n;i++)scanf("%d",&a[i][j]);
for (i=1;i<=n;i++){
addedge(0,i,1,0);
orz[i]=1;num[i]=i;
for (j=1;j<=m;j++)addedge(i,j+n,1,a[i][j]);
}
while (spfa());
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=400010;
const int inf=1000000007;
int n,m,i,edgenum,tmp,S,T,len,ans;
int head[M],vet[M],next[M],size[M],h[M],dis[M];
struct shit{int st,ed,len;}a[M];
bool cmp(shit x,shit y){return x.len<y.len;}
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=1;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=1;
}
int bfs(){
int l=1,r=1;
memset(dis,-1,sizeof dis);
h[1]=S;dis[S]=0;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]<0){
dis[v]=dis[u]+1;
h[++r]=v;
}
}
l++;
}
if (dis[T]<0)return 0;else return 1;
}
int dfs(int u,int aug){
if (u==T)return aug;
int flow=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]==dis[u]+1){
int tmp=dfs(v,min(aug-flow,size[e]));
flow+=tmp;
size[e]-=tmp;
size[e^1]+=tmp;
if (flow==aug)return flow;
}
}
if (!flow)dis[u]=-1;
return flow;
}
int main(){
edgenum=1;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].len);
sort(a+1,a+m+1,cmp);
scanf("%d%d%d",&S,&T,&len);
for (i=1;i<=m;i++)
if (a[i].len<len)addedge(a[i].st,a[i].ed);
else break;
while (bfs())ans+=dfs(S,inf);
memset(head,0,sizeof head);
memset(size,0,sizeof size);
edgenum=1;
for (i=m;i;i--)
if (a[i].len>len)addedge(a[i].st,a[i].ed);
else break;
while (bfs())ans+=dfs(S,inf);
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int n,m,i,j,k,edgenum,x,ans;
int u[2]={0,1},v[2]={1,0};
int head[M],vet[M],next[M],size[M],dis[M],h[M];
int point(int x,int y){return (x-1)*m+y;}
void addedge(int x,int y,int ch){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=ch;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=ch;
}
int bfs(){
int l=1,r=1;
memset(dis,-1,sizeof dis);
dis[0]=1;h[1]=0;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]<0){
dis[v]=dis[u]+1;
h[++r]=v;
}
}
l++;
}
if (dis[n*m+1]<0)return 0;else return 1;
}
int dfs(int u,int aug){
if (u==n*m+1)return aug;
int flow=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]==dis[u]+1){
int tmp=dfs(v,min(aug-flow,size[e]));
flow+=tmp;
size[e]-=tmp;
size[e^1]+=tmp;
if (flow==aug)return flow;
}
}
if (!flow)dis[u]=-1;
return flow;
}
int main(){
edgenum=1;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
for (k=0;k<2;k++){
int x=i+u[k],y=j+v[k];
if (x<=n&&y<=m)addedge(point(i,j),point(x,y),1);
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&x);
if (x==1)addedge(0,point(i,j),inf);else if (x==2)addedge(point(i,j),n*m+1,inf);
}
while (bfs())ans+=dfs(0,inf);
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
const int inf=1000000007;
int head[M],vet[M],next[M],size[M],h[M],dis[M>>3];
int n,m,i,x,y,ch,ans,edgenum;
void addedge(int x,int y,int ch){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
size[edgenum]=ch;
vet[++edgenum]=x;
next[edgenum]=head[y];
head[y]=edgenum;
size[edgenum]=0;
}
int bfs(){
int l=1,r=1;
memset(dis,-1,sizeof dis);
dis[0]=1;h[1]=0;
while (l<=r){
int u=h[l];
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]<0){
dis[v]=dis[u]+1;
h[++r]=v;
}
}
l++;
}
if (dis[n+m+1]<0)return 0;else return 1;
}
int dfs(int u,int aug){
if (u==n+m+1)return aug;
int flow=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (size[e]&&dis[v]==dis[u]+1){
int tmp=dfs(v,min(aug-flow,size[e]));
flow+=tmp;
size[e]-=tmp;
size[e^1]+=tmp;
if (flow==aug)return flow;
}
}
if (!flow)dis[u]=-1;
return flow;
}
int main(){
edgenum=1;
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
scanf("%d",&x);
addedge(0,i,x);
}
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&ch);
addedge(x,n+i,inf);
addedge(y,n+i,inf);
addedge(n+i,n+m+1,ch);
ans+=ch;
}
while (bfs())ans-=dfs(0,inf);
printf("%d\n",ans);
}
2
7
2016
7
2016
GoodBye YiWei
在剧场版新闻联播的熏陶下，我感觉我的政治水平又上了一个档次。。
这时候膜到了姚中交际花wxx的祭奠文，感到不明觉厉。
突然脑洞一开也想来写一篇。
三十个小时以前，我还在打uoj的比赛GoodBye Yiwei。
当时是听说有NOIP题才点进去的，结果发现打也打不动。（果然我还是一只蒟蒻）
暴力打打才两个半小时就弃疗了。
听说皮球张也不会做？
结果就喜闻乐见地滚粗了。
------------------------------------------------------------------------
因为有许多东西在NOIP滚粗记里写过了，那就略过吧。
从一名蒟蒻中的蒟蒻成长为NOIP1=，我学会了很多。
从对未来的迷茫到如今坚定走OI的路，我学会了很多。
从初中到高中，我学会了很多。
自己选择的路，就算跪着也要走完。
GoodBye YiWei！
2016，我们注定不平凡。
2
3
2016
3
2016
wc2016滚粗记
谜之声I：在阅读时请每隔5秒按一下F5因为可能你在读而窝正在更新。
谜之声II：请点开再看因为这篇文章实在太长了。
Day1
出发日。
在文化课脑残粉（众家长？）的建议下，窝萌订了晚上的机票来考完期末考。
然而天公不作美，期待已久的期末考推迟了。（其实我的内心是狂喜的）
于是飞机喜闻乐见地晚点了。
于是窝萌的行程就被拖到了Day2。
Day2
到2.00am的时候终于抵达了南山中学，决定先去拜访Gold_7和NiroBC。
南山中学的城门虽然十分气派，但和YYHS的完全不能比嘞。。。
然而找不到寝室，期间听到了门卫大叔的四川话TalkShow，感到不明觉厉。
最终还是滚到了寝室，一人敲开门，剩下的人集体开闪光灯拍Gold_7的睡衣照，然而质量极差，只能看到一团黑影。
8.00am去听多项式导论。
然而只听了1h就听不下去了。。。。
接下来3h只听到讲课人不断地说“好啊！”
于是偷偷从后门溜了出去，结果被生辅老师赶了出去，于是又滚了回去。
下午听形式语言与自动机。
alpq说下午的课比上午更恶心，想想自己只会AC自动机、WA自动机、TLE自动机和RE自动机，于是集体弃疗。
期间老司机YWN普及英语知识，让窝萌学会了诸如dick等单词。
由于玩积木的时候gonens过于狡猾，新称号迪克李（DickLee）GET DA☆ZE。
吃晚饭的时候窝萌被两个妹子莫名采访了，对上镜深恶痛绝的我们嫁祸条哥。然而alpq说有个妹子的颜值很高，于是作为学弟的窝萌为学长拍了许许多多的妹子照片。（听说最后alpq还是被采访了233）
晚上alpq和gonens也搬到窝萌寝室来了，于是窝萌寝室就有8个人了。
在10.30pm熄灯的时候alpq吼了一声：夜生活才刚刚开始！
于是窝萌就开始嘿嘿嘿。。。
1
20
2016
20
2016
论蒟蒻的花样作死之lct
问：快要期末考了为什么不好好学习文化课呢？
答：学习文化课太无聊了而且没有前途。。。
问：那为什么要学这个诡异的蒜法呢？
答：因为窝splay找不到模板题刷了。。
【简介】
首先lct与树链剖分有着密切的关系。
树链剖分，即把一棵su剖出轻重链，然后用数据结构维护重链。
但是当树的形态改变时，原来的重链可能就不是最优的剖分方式了。
那么就需要用数据结构来维护重链。可以用splay，关键字为深度。
lct的核心操作Access，就是把root~x的所有边都变成重链。
由此窝萌阔以兹磁如下操作：
makeroot：将x变成根，只需要Access一下然后打个翻转标记就行。
link：加一条x->y的边，那么makeroot(x)，x的父亲记为y
cut：删除x->y的边，那么makeroot(x)，再将y旋到根，把左儿子断掉。
至于维护一些路径上的东西，只要用splay记录一下就阔以了。
void pushdown(int x){
int l=son[x][0],r=son[x][1];
if (rev[x]){
rev[l]^=1;rev[r]^=1;rev[x]=0;
swap(son[x][0],son[x][1]);
}
}
int isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void rotate(int x){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (!isroot(y)){if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
}
void splay(int x){
top=0;q[++top]=x;
for (int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for (int i=top;i;i--)pushdown(q[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (son[y][0]==x^son[z][0]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
for (int t=0;x;t=x,x=fa[x]){
splay(x);
son[x][1]=t;
}
}
int find(int x){
access(x);
splay(x);
while (son[x][0])x=son[x][0];
return x;
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
son[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
【例题】
Bzoj2049 果奔lct，维护一个link和cut就行了。
Bzoj2002 建树小学难度，然后用lct来维护树的深度。
Bzoj3282 果奔lct，link和cut的时候注意一下。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int n,m,i,x,y,top;
int size[M],fa[M],son[M][2],rev[M],q[M];
void pushdown(int x){
int l=son[x][0],r=son[x][1];
if (rev[x]){
rev[l]^=1;rev[r]^=1;rev[x]=0;
swap(son[x][0],son[x][1]);
}
}
int isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void rotate(int x){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (!isroot(y)){if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
}
void splay(int x){
top=0;q[++top]=x;
for (int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for (int i=top;i;i--)pushdown(q[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (son[y][0]==x^son[z][0]==y)rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x){
for (int t=0;x;t=x,x=fa[x]){
splay(x);
son[x][1]=t;
}
}
int find(int x){
access(x);
splay(x);
while (son[x][0])x=son[x][0];
return x;
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
son[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
char s[10];
scanf("%s",s);
scanf("%d%d",&x,&y);
if (s[0]=='C')link(x,y);
else if (s[0]=='D')cut(x,y);
else {if (find(x)==find(y))puts("Yes");else puts("No");}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000000;
int n,m,i,x,y,opt;
int fa[M],son[M][2],isroot[M],size[M];
void pushup(int x){
int l=son[x][0],r=son[x][1];
size[x]=size[l]+size[r]+1;
}
void rotate(int x){
int y=fa[x],z=fa[y],w=x==son[y][0];
son[y][!w]=son[x][w];fa[son[x][w]]=y;
son[x][w]=y;fa[y]=x;fa[x]=z;
if (!isroot[y])if (y==son[z][0])son[z][0]=x;else son[z][1]=x;
isroot[x]=isroot[y];isroot[y]=0;
pushup(y);pushup(x);
}
void splay(int x){while (!isroot[x])rotate(x);}
void access(int x){
int y;
splay(x);
while (fa[x]){
y=fa[x];
splay(y);
isroot[son[y][1]]=1;
isroot[x]=0;
son[y][1]=x;
pushup(y);
splay(x);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&x);
if (i+x>n)fa[i]=n+1;else fa[i]=i+x;
}
scanf("%d",&m);
for (i=1;i<=n+1;i++)size[i]=isroot[i]=1;
for (i=1;i<=m;i++){
scanf("%d",&opt);
if (opt==1){
scanf("%d",&x);
x++;
access(x);
printf("%d\n",size[son[x][0]]);
}else{
scanf("%d%d",&x,&y);
x++;
splay(x);
fa[son[x][0]]=fa[x];
isroot[son[x][0]]=1;
son[x][0]=0;
pushup(x);
if (x+y>n)fa[x]=n+1;else fa[x]=x+y;
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=500010;
int n,m,i,opt,x,y,top;
int size[M],data[M],sum[M],rev[M],son[M][2],fa[M],q[M];
void pushdown(int x){
int l=son[x][0],r=son[x][1];
if (rev[x]){
rev[l]^=1,rev[r]^=1,rev[x]=0;
swap(son[x][0],son[x][1]);
}
}
int isroot(int x){
return son[fa[x]][0]!=x&&son[fa[x]][1]!=x;
}
void pushup(int x){
int l=son[x][0],r=son[x][1];
sum[x]=sum[l]^sum[r]^data[x];
}
void rotate(int x){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (!isroot(y)){if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x){
top=0;q[++top]=x;
for (int i=x;!isroot(i);i=fa[i])q[++top]=fa[i];
for (int i=top;i;i--)pushdown(q[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){
if (son[y][0]==x^son[z][0]==y)rotate(x);else rotate(y);
}
rotate(x);
}
}
void access(int x){
for (int t=0;x;t=x,x=fa[x]){
splay(x);
son[x][1]=t;
pushup(x);
}
}
int find(int x){
access(x);splay(x);
while (son[x][0])x=son[x][0];
return x;
}
void makeroot(int x){
access(x);splay(x);rev[x]^=1;
}
void cut(int x,int y){
makeroot(x);access(y);splay(y);
if (son[y][0]==x)son[y][0]=fa[x]=0;
}
void link(int x,int y){
makeroot(x);fa[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)scanf("%d",&data[i]),sum[i]=data[i];
for (i=1;i<=m;i++){
scanf("%d",&opt);
if (opt==0){
scanf("%d%d",&x,&y);
makeroot(x);
//printf("%d\n",sum[x]);
access(y);
//printf("%d\n",sum[x]);
splay(y);
printf("%d\n",sum[y]);
}
if (opt==1){
scanf("%d%d",&x,&y);
if (find(x)!=find(y))link(x,y);
}
if (opt==2){
scanf("%d%d",&x,&y);
if (find(x)==find(y))cut(x,y);
}
if (opt==3){
scanf("%d%d",&x,&y);
access(x);
splay(x);
data[x]=y;
pushup(x);
}
}
}
1
12
2016
12
2016
BZOJ4364【IOI2014】wall砖墙
Description
健佳正在用大小相同的砖块来砌起一面墙。这面墙由 列砖块所组成，它们从左到右的编号0至n-1。各列的高度可以不同。各列的高度就是该列砖块的数量。健佳用如下方式来建造这面墙。最开始每列都没有砖块。此后，健佳通过k个阶段的增加(adding)或移除(removing)砖块操作来砌墙。当所有k个阶段完成后，这面墙就砌好了。在每个阶段中，健佳都会被告知一个连续的砖块列的范围，以及一个高度值h，然后他就完成如下过程：在增加砖块(adding)阶段，对于给定的列范围中高度小于h的列，健佳会增加砖块使它们的高度都恰好等于h。此时他不会改变那些高度大于或等于h的列。在移除砖块(removing)阶段，对于给定的列范围中高度大于 的列，健佳会移除砖块使它们的高度都恰好等于h。此时他不会改变那些高度小于或等于h的列。你的任务就是计算出这面墙的最后形状。
Input
第1行：n, k。
第2+i 行(0≤i≤k-1)：op[i], left[i], right[i], height[i]。
n: 这面墙中的列数。
k: 阶段数。
op: 大小为k的数组；op[i]是第i个阶段的类型：1 表示增加阶段(adding) 而 2表示移除阶段(removing) ，其中0≤i≤k-1。
left 和 right: 大小为k的数组；在第i个阶段中，列的范围从第left[i] 列开始到第right[i]列结束（包括两端 left[i] 和 right[i]），其中0≤i≤k-1。这里保证满足left[i]≤right[i]。
height: 大小为k的数组；height[i] 表示在阶段i的高度参数，其中0≤i≤k-1。
Output
共n行，第i行包含一个整数表示finalHeight[i]。
finalHeight: 大小为n的数组；你需要把第i列砖块的最终数量存放到finalHeight[i]中做为返回结果，其中0≤i≤n-1。
Sample Input
输入样例1
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
输入样例2
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
输入样例2
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
Sample Output
输出样例1
0
0
0
39412
39412
39412
48623
48623
48623
48623
输出样例2
3
4
5
4
3
3
0
0
1
0
0
0
0
39412
39412
39412
48623
48623
48623
48623
输出样例2
3
4
5
4
3
3
0
0
1
0
HINT
对于100%的数据，1≤n≤2,000,000，1≤k≤500,000。
【题解】
为什么题目不带BZOJ的格式了？我也不知道。
由于只要维护最值，处理区间时，可以直接对区间最值进行修改。
接着可以用父亲的区间最值去更新儿子的区间最值，然后再用儿子的最值松弛父亲。
接下来是精彩的卡常时间。
首先窝萌阔以手写max和min。
其次窝萌阔以用位运算预处理每个节点的左右儿子。
此外窝萌阔以加inline和读入优化。
然后就水过辣！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=2000010;
int n,m,i,opt,l,r,x;
int mx1[M*4],mx2[M*4];
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void pushdown(int p){
int l=p<<1,r=p<<1^1;
if (mx2[p]>mx1[l])mx1[l]=mx2[l]=mx2[p];
else if (mx2[p]>mx2[l])mx2[l]=mx2[p];
if (mx2[p]>mx1[r])mx1[r]=mx2[r]=mx2[p];
else if (mx2[p]>mx2[r])mx2[r]=mx2[p];
if (mx1[p]<mx2[l])mx1[l]=mx2[l]=mx1[p];
else if (mx1[p]<mx1[l])mx1[l]=mx1[p];
if (mx1[p]<mx2[r])mx1[r]=mx2[r]=mx1[p];
else if (mx1[p]<mx1[r])mx1[r]=mx1[p];
}
inline void pushup(int p){
int l=p<<1,r=p<<1^1;
mx1[p]=max(mx1[l],mx1[r]);
mx2[p]=min(mx2[l],mx2[r]);
}
inline void update1(int x,int y,int l,int r,int p,int t){
if (x==l&&y==r){
mx1[p]=max(mx1[p],t);
mx2[p]=max(mx2[p],t);
return;
}
int mid=l+r>>1;
pushdown(p);
if (y<=mid)update1(x,y,l,mid,p<<1,t);
else if (x>mid)update1(x,y,mid+1,r,p<<1^1,t);
else update1(x,mid,l,mid,p<<1,t),update1(mid+1,y,mid+1,r,p<<1^1,t);
pushup(p);
}
inline void update2(int x,int y,int l,int r,int p,int t){
if (x==l&&y==r){
mx1[p]=min(mx1[p],t);
mx2[p]=min(mx2[p],t);
return;
}
int mid=l+r>>1;
pushdown(p);
if (y<=mid)update2(x,y,l,mid,p<<1,t);
else if (x>mid)update2(x,y,mid+1,r,p<<1^1,t);
else update2(x,mid,l,mid,p<<1,t),update2(mid+1,y,mid+1,r,p<<1^1,t);
pushup(p);
}
inline void build(int l,int r,int p){
if (l==r){
printf("%d\n",mx1[p]);
return;
}
int mid=l+r>>1;
pushdown(p);
build(l,mid,p<<1);
build(mid+1,r,p<<1^1);
}
int main(){
n=read(),m=read();
for (i=1;i<=m;i++){
opt=read();
if (opt==1){
l=read(),r=read(),x=read();
l++;r++;
update1(l,r,1,n,1,x);
}else{
l=read(),r=read(),x=read();
l++;r++;
update2(l,r,1,n,1,x);
}
}
build(1,n,1);
}
1
6
2016
6
2016
论蒟蒻的花样作死之后缀数组
问：既然有后缀自动机那么为什么还要后缀数组呢？
答：窝也不知道，好像是条哥要窝萌学的。
问：那学后缀数组有什么困难吗？
答：模板极其难背。。。
【简介】
然而窝懒得介绍（其实是窝不会介绍。。）
如果你想学，戳这
下面贴出模板：
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
p=0;
for (i=n-j;i<n;i++)y[p++]=i;
for (i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=1;i<=n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
【例题】
poj2774 求两个串的最长公共子串，只要把两个串连起来求出height，然后找出一个height最大并且sa分别在两个串中的就行了。
poj3216 求出现至少k次的最长子串，等价于求max(lcp(i,i+k-1))。（谜之声：字符串hash大法好）
poj1743 题意极臭~~~首先差分，然后二分答案，那么只要求连续大于mid的height的sa的最大值与最小值之差是否大于mid就阔以了。
poj3294 求n个串中出现超过n/2次的最大长度子串。那么只要把n个串连起来，二分寻找满足条件的字符串。
poj1226 求最长串，使得该串或该串的回文串为n个串的子串。只要把n个串和其回文串连起来，然后就和前一题一样了。
poj3145 求长度不小于k的公共子串个数。计算A的后缀和B的后缀的LCP，如果>k，对答案的贡献是LCP-k+1。那么把两个串连起来然后通过height分组，扫描一遍，遇到B的后缀就统计一下前面A的后缀产生的贡献。由于LCP是求height的最小值，可以通过单调栈维护。
poj3581 把数组分成三分，翻转并重排，求最小字典序。只要逆过来，搞两遍sa求最小后缀就可以了，但是第二次需要重新接一遍，否则会出现反例。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
char s1[M],s2[M];
int s[M],wa[M],wb[M],wc[M],wd[M],sa[M];
int rank[M],height[M];
int i,mx;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int j,p,*x=wa,*y=wb;
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
p=0;
for (i=n-j;i<n;i++)y[p++]=i;
for (i=0;i<n;i++)if (sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while (r[i+k]==r[j+k])k++;
}
}
int main(){
scanf("%s",s1);
scanf("%s",s2);
int n=0,len=strlen(s1);
for (i=0;i<len;i++)s[n++]=s1[i]-'a'+1;
s[n++]=28;
len=strlen(s2);
for (i=0;i<len;i++)s[n++]=s2[i]-'a'+1;
for (i=0;i<=2*n+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,n,29);
getheight(s,sa,n);
len=strlen(s1);
for (i=0;i<=n;i++)
if (height[i]>mx){
if (sa[i-1]>=0&&sa[i-1]<len&&len<sa[i]||sa[i]>=0&&sa[i]<len&&len<sa[i-1])mx=height[i];
}
printf("%d\n",mx);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
const int M=1000002;
const int inf=1000000007;
using namespace std;
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M];
int rmq[M/10][18];
int n,k,i,j,ans;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int j,p,*x=wa,*y=wb;
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
p=0;
for (i=n-j;i<n;i++)y[p++]=i;
for (i=0;i<n;i++)if (sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y);p=1;x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int main(){
scanf("%d%d",&n,&k);k--;
for (i=0;i<n;i++)scanf("%d",&s[i]),s[i]++;
for (i=0;i<2*n+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,n,M);
getheight(s,sa,n);
memset(rmq,inf,sizeof rmq);
for (i=0;i<n;i++)rmq[i][0]=height[i];
int len=log(n)/log(2)+1e-8;
for (j=1;j<=len;j++)
for (i=0;i<n;i++)
rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
len=log(k)/log(2)+1e-8;
for (i=0;i<=n-k;i++)ans=max(ans,min(rmq[i][len],rmq[i+k-(1<<len)][len]));
printf("%d\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100000;
int n,i,ans;
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
p=0;
for (i=n-j;i<n;i++)y[p++]=i;
for (i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=1;i<=n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if(k)k--;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int solve(int len){
int i=2,mx,Mx;
while (1){
while(i<=n&&height[i]<len)i++;
if (i>n)break;
mx=sa[i-1];Mx=sa[i-1];
while(i<=n&&height[i]>=len){
mx=max(mx,sa[i]);
Mx=min(Mx,sa[i]);
i++;
}
if(mx-Mx>=len)return 1;
}
return 0;
}
int main(){
scanf("%d",&n);
while (n){
for (i=0;i<n;i++)scanf("%d",&s[i]);
if (n<10){puts("0");scanf("%d",&n);continue;}
n--;
for (i=0;i<n;i++)s[i]=s[i+1]-s[i]+89;
s[n]=0;
for (i=0;i<2*n+10;i++)wa[i]=wb[i]=0;
getsa(s,sa,n+1,200);
getheight(s,sa,n);
int l=4,r=n-1>>1;
while(l+1<r){
int mid=l+r>>1;
if(solve(mid))l=mid;else r=mid;
}
if(solve(r))ans=r+1;else ans=l+1;
if(ans<5)ans=0;
printf("%d\n",ans);
scanf("%d",&n);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000100;
char a[M];
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M],ans[M],vis[105],Len[105];
int n,i,j,flag,size,N;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<N;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<N;j*=2,m=p){
p=0;
for (i=N-j;i<N;i++)y[p++]=i;
for (i=0;i<N;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<N;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<N;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<N;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<N;i++)rank[sa[i]]=i;
for (i=0;i<N;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int solve(int x,int n,int k){
int i,j,cnt=size=0;
for (i=0;i<105;i++)vis[i]=1;
for (i=1;i<=N;i++){
if(height[i]>=x){
for (j=1;j<=k;j++){
if (sa[i]>Len[j-1]&&sa[i]<Len[j])cnt+=vis[j],vis[j]=0;
if (sa[i-1]>Len[j-1]&&sa[i-1]<Len[j])cnt+=vis[j],vis[j]=0;
}
}else{
if (cnt>k/2)ans[++size]=sa[i-1];
cnt=0;
for (int p=0;p<105;p++)vis[p]=1;
}
}
if (cnt>k/2)ans[++size]=sa[N];
if (size){ans[0]=size;return 1;}else return 0;
}
int main(){
flag=0;
while(scanf("%d",&n)&&n){
N=size=0;
for (i=1;i<=n;i++){
scanf("%s",a);
int len=strlen(a);
for (j=0;j<len;j++)s[N++]=a[j];
Len[++size]=N;
s[N++]='#'+i;
}
s[N-1]=0;
for (i=0;i<N+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,N,500);
getheight(s,sa,N-1);
int l=1,r=N;
while(l<=r){
int mid=l+r>>1;
if(solve(mid,N,n))l=mid+1;else r=mid-1;
}
if (flag)puts("");
flag=1;
if(l==1)puts("?");else{
for (i=1;i<=ans[0];i++){
for (j=ans[i];j<ans[i]+l-1;j++)printf("%c",s[j]);
puts("");
}
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100100;
char a[M];
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M];
int rank[M],height[M],ans[M],vis[200],Len[200];
int n,i,j,flag,size,N;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<N;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<N;j*=2,m=p){
p=0;
for (i=N-j;i<N;i++)y[p++]=i;
for (i=0;i<N;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<N;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<N;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=N-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<N;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=0;i<N;i++)rank[sa[i]]=i;
for (i=0;i<N;height[rank[i++]]=k){
if(k)k--;
if(!rank[i])continue;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int solve(int x,int n,int k){
int i,j,cnt=size=0;
for (i=0;i<200;i++)vis[i]=1;
for (i=1;i<=N;i++){
if(height[i]>=x){
for (j=1;j<=k;j++){
if (sa[i]>Len[j-1]&&sa[i]<Len[j])cnt+=vis[j-1>>1],vis[j-1>>1]=0;
if (sa[i-1]>Len[j-1]&&sa[i-1]<Len[j])cnt+=vis[j-1>>1],vis[j-1>>1]=0;
}
}else{
if (cnt==k/2)size++;
cnt=0;
for (int p=0;p<200;p++)vis[p]=1;
}
}
if (cnt==k/2)size++;
if (size)return 1;else return 0;
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
N=size=0;
for (i=1;i<=n;i++){
scanf("%s",a);
int len=strlen(a);
for (j=0;j<len;j++)s[N++]=a[j];
Len[++size]=N;
s[N++]=200+i*2-1;
for (j=len-1;j>=0;j--)s[N++]=a[j];
Len[++size]=N;
s[N++]=200+i*2;
}
s[N-1]=0;
for (i=0;i<N+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,N,500);
getheight(s,sa,N-1);
int l=0,r=N;
while(l<r){
int mid=l+r+1>>1;
if(solve(mid,N,n*2))l=mid;else r=mid-1;
}
printf("%d\n",l);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=600100;
char s1[M],s2[M];
int s[M],sa[M],wa[M],wb[M],wc[M],wd[M],rank[M],height[M];
int st[M][2];
int n,k,i;
ll top,tot;
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
p=0;
for (i=n-j;i<n;i++)y[p++]=i;
for (i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void getheight(int *r,int *sa,int n){
int i,j,k=0;
for (i=1;i<=n;i++)rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k){
if (k)k--;
j=sa[rank[i]-1];
while(r[i+k]==r[j+k])k++;
}
}
int main(){
while(scanf("%d",&k)&&k){
scanf("%s",s1);
scanf("%s",s2);
n=0;
int l1=strlen(s1),l2=strlen(s2);
for (i=0;i<l1;i++)s[n++]=s1[i];
s[n++]=34;
for (i=0;i<l2;i++)s[n++]=s2[i];
for (i=0;i<n+10;i++)wa[i]=wb[i]=-1;
n++;
s[n-1]=0;
getsa(s,sa,n,201);
getheight(s,sa,n-1);
ll sum=0;
tot=top=0;
for (i=1;i<n;i++){
if (height[i]<k)top=tot=0;
else{
int cnt=0;
if (sa[i-1]<l1)cnt++,tot+=height[i]-k+1;
while(top>0&&height[i]<=st[top-1][0]){
top--;
tot-=st[top][1]*(st[top][0]-height[i]);
cnt+=st[top][1];
}
st[top][0]=height[i];st[top++][1]=cnt;
if(sa[i]>l1)sum+=tot;
}
}
tot=top=0;
for (i=1;i<n;i++){
if (height[i]<k)top=tot=0;
else{
int cnt=0;
if (sa[i-1]>l1)cnt++,tot+=height[i]-k+1;
while (top>0&&height[i]<=st[top-1][0]){
top--;
tot-=st[top][1]*(st[top][0]-height[i]);
cnt+=st[top][1];
}
st[top][0]=height[i];st[top++][1]=cnt;
if(sa[i]<l1)sum+=tot;
}
}
printf("%I64d\n",sum);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,i;
int a[M],b[M],s[M];
int sa[M],wa[M],wb[M],wc[M],wd[M];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void getsa(int *r,int *sa,int n,int m){
int *x=wa,*y=wb,j,p;
memset(wc,0,sizeof wc);
for (i=0;i<n;i++)wc[x[i]=r[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p){
p=0;
for (i=n-j;i<n;i++)y[p++]=i;
for (i=0;i<n;i++)if (sa[i]>=j)y[p++]=sa[i]-j;
for (i=0;i<n;i++)wd[i]=x[y[i]];
for (i=0;i<m;i++)wc[i]=0;
for (i=0;i<n;i++)wc[wd[i]]++;
for (i=1;i<m;i++)wc[i]+=wc[i-1];
for (i=n-1;i>=0;i--)sa[--wc[wd[i]]]=y[i];
swap(x,y),p=1,x[sa[0]]=0;
for (i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
int main(){
scanf("%d",&n);
for (i=0;i<n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b,b+n);
int cnt=unique(b,b+n)-b;
for (i=0;i<n;i++)s[i]=lower_bound(b,b+cnt,a[n-i-1])-b+1;
for (i=0;i<n+10;i++)wa[i]=wb[i]=-1;
getsa(s,sa,n+1,cnt+1);
//for (i=0;i<=n;i++)printf("%d\n",sa[i]);
for (i=1;i<=n&&sa[i]<=1;i++);
int tmp=sa[i];
for (i=tmp;i<n;i++)printf("%d\n",a[n-i-1]);
for (i=0;i<tmp;i++)s[i+tmp]=s[i];
tmp*=2;
s[tmp]=0;
getsa(s,sa,tmp+1,cnt+1);
for (i=1;i<tmp&&(!sa[i]||sa[i]>=tmp/2);i++);
int tmp1=sa[i];
for (i=tmp1;i<tmp/2;i++)printf("%d\n",a[n-i-1]);
for (i=0;i<tmp1;i++)printf("%d\n",a[n-i-1]);
}
1
5
2016
5
2016
BZOJ2434【NOI2011阿狸的打字机】
Description
阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。
经阿狸研究发现，这个打字机是这样工作的：
l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
l 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。
l 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。
例如，阿狸输入aPaPBbP，纸上被打印的字符如下：
a
aa
ab
我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数(x,y)（其中1≤x,y≤n），打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？
Input
输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数m，表示询问个数。
接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为(x, y)。
Output
输出m行，其中第i行包含一个整数，表示第i个询问的答案。
Sample Input
aPaPBbP
3
1 2
1 3
2 3
Sample Output
2
1
0
HINT
1<=N<=10^5
1<=M<=10^5
输入总长<=10^5
Source
【题解】
isprogrammer炸掉了一个星期真是不爽
做这道题让窝感觉没学过trie图。。。。。
首先要用黑暗的方法构出trie树，即按照读入顺序扫下来，那么有三种情况：
1、碰到字母，新建一个子节点（如果已存在就不用新建），进入该子节点。
2、碰到P，那么打个标记。
3、碰到B，回到父亲节点。
然后求出每个节点的fail，那么询问x在y中出现多少次，只要求root~y中有多少点沿fail能走到x。
那么构出fail树，问题就转化为x的子树中有多少个是root~y中的点。
考虑dfs序，那么求子树和的问题就转化为求片段和，可以用树状数组维护。
对于一个串y，将root~y的点的dfs序插入树状数组中，然后处理所有与y有关的询问就阔以辣！
最后的处理还是可以直接扫描读入的串：
1、碰到字母，将子节点的dfs序加入树状数组，进入该子节点。
2、碰到P，处理询问。
3、碰到B，回到父亲节点。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int m,cnt,u,id,i,x,y,edgenum,Edgenum,T;
char s[M];
int pos[M],fa[M],head[M],vet[M],next[M],Head[M],Vet[M],Next[M],tree[2*M],fail[M],h[M],l[M],r[M],ans[M];
int trie[M][26];
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
}
void Addedge(int x,int y){
Vet[++Edgenum]=y;
Next[Edgenum]=Head[x];
Head[x]=Edgenum;
}
void update(int x,int y){
for (int i=x;i<=T;i+=i&-i)tree[i]+=y;
}
int query(int x){
int ans=0;
for (int i=x;i;i-=i&-i)ans+=tree[i];
return ans;
}
void bfs(){
int l=1,r=1;
h[l]=1,fail[1]=0;
while (l<=r){
int u=h[l];
for (int i=0;i<26;i++)
if (trie[u][i]){
int v=trie[u][i];
if (u==1)fail[v]=1;else fail[v]=trie[fail[u]][i];
h[++r]=v;
}else trie[u][i]=trie[fail[u]][i];
l++;
}
}
void dfs(int u){
l[u]=++T;
for (int e=head[u];e;e=next[e])dfs(vet[e]);
r[u]=++T;
}
int main(){
scanf("%s",s);
scanf("%d",&m);
int n=strlen(s);
cnt=1,u=1,id=0;
for (i=0;i<26;i++)trie[0][i]=1;
for (i=0;i<n;i++){
if (s[i]-'a'>=0){
if (!trie[u][s[i]-'a'])trie[u][s[i]-'a']=++cnt,fa[cnt]=u;
u=trie[u][s[i]-'a'];
}else if (s[i]=='P')pos[++id]=u;else u=fa[u];
}
bfs();
for (i=1;i<=cnt;i++)addedge(fail[i],i);
dfs(0);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
Addedge(y,x);
}
u=1,id=0;update(l[1],1);
for (i=0;i<n;i++){
if (s[i]-'a'>=0)u=trie[u][s[i]-'a'],update(l[u],1);
else if (s[i]=='P'){
id++;
for (int e=Head[id];e;e=Next[e]){
int v=pos[Vet[e]];
ans[e]=query(r[v])-query(l[v]-1);
}
}else update(l[u],-1),u=fa[u];
}
for (i=1;i<=m;i++)printf("%d\n",ans[i]);
}
12
28
2015
28
2015
论蒟蒻的花样作死之Splay
问：Splay在时间和编程复杂度上都被碾压，为什么要学呢？
答：Splay是万金油啊，完爆各种乱七八糟的维护。（本质是懒得学新数据结构）
问：那么我阔以不看冗长的介绍吗？
答：其实窝并没有想要介绍。。。
【简介】
首先Spaly是个二叉搜索树，如果连这个都不知道，戳这
其次Splay有一个奇妙的提根操作，同时也是Splay的核心操作。
void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (y==k)k=x;
else {if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){
while (x!=k){
int y=fa[x],z=fa[y];
if (y!=k){
if (son[y][0]==x^son[z][0]==y)rotate(x,k);else rotate(y,k);
}
rotate(x,k);
}
}
通过这个可以证明所有操作的均摊复杂度为4*logn。
显然加点、删点、询问第k大、询问一个数是第几大……这些操作都是很好写的。
那么如何给区间加值、求区间最值、区间反转呢？
窝萌阔以参照线段树的tag来给平衡树打tag，然后每次操作完后pushup、pushdown。
区间反转，其实就是左右儿子交换，不过这种情况要加两个点防止爆炸。
有兴趣的同学戳这
【例题】
Bzoj1552&3506
好像是傻逼题？加个区间反转和区间最值就能A。
Bzoj3173
基于数是一个一个插入的，显然插入的数比前面的数都大。
那么只要求区间最值来暴推lis就阔以辣！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int n,i,cnt,root;
int fa[M],son[M][2],rev[M],data[M],size[M],mx[M],pos[M],s[M],ans[M];
struct node{int v,pos;}a[M];
bool operator<(node x,node y){return x.pos<y.pos;}
bool cmp(node x,node y){return x.v<y.v||(x.v==y.v&&x.pos<y.pos);}
void pushup(int p){
int l=son[p][0],r=son[p][1];
pos[p]=p;mx[p]=data[p];
if (mx[l]<mx[p]){mx[p]=mx[l];pos[p]=pos[l];}
if (mx[r]<mx[p]){mx[p]=mx[r];pos[p]=pos[r];}
size[p]=size[l]+size[r]+1;
}
void pushdown(int p){
int l=son[p][0],r=son[p][1];
if (rev[p]){
rev[p]=0;
rev[l]^=1;rev[r]^=1;
swap(son[p][0],son[p][1]);
}
}
void build(int l,int r,int p){
if (l>r)return;
if (l==r){
fa[l]=p;size[l]=1;
if (l<p)son[p][0]=l;else son[p][1]=l;
pos[l]=l;mx[l]=data[l]=a[l].v;
return;
}
int mid=l+r>>1;
build(l,mid-1,mid);
build(mid+1,r,mid);
fa[mid]=p;data[mid]=a[mid].v;pushup(mid);
if (mid<p)son[p][0]=mid;else son[p][1]=mid;
}
void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (y==k)k=x;
else {if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){
int top=0;s[++top]=x;
for (int i=x;fa[i];i=fa[i])s[++top]=fa[i];
for (int i=top;i;i--)if(rev[s[i]])pushdown(s[i]);
while (x!=k){
int y=fa[x],z=fa[y];
if (y!=k){
if (son[y][0]==x^son[z][0]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int findkth(int k,int rank){
if (rev[k])pushdown(k);
int l=son[k][0],r=son[k][1];
if (size[l]+1==rank)return k;
else if (size[l]>=rank)return findkth(l,rank);
else return findkth(r,rank-size[l]-1);
}
void reverse(int l,int r){
int x=findkth(root,l),y=findkth(root,r+2);
splay(x,root);splay(y,son[x][1]);
rev[son[y][0]]^=1;
}
int querymx(int l,int r){
int x=findkth(root,l),y=findkth(root,r+2);
splay(x,root);splay(y,son[x][1]);
return pos[son[y][0]];
}
int main(){
scanf("%d",&n);
a[1].v=a[n+2].v=inf;mx[0]=inf;
for (i=2;i<=n+1;i++)scanf("%d",&a[i].v),a[i].pos=i;
sort(a+2,a+n+2,cmp);
for (i=2;i<=n+1;i++)a[i].v=i-1;
sort(a+2,a+n+2);
build(1,n+2,0);
root=n+3>>1;cnt=n+2;
for (i=1;i<=n;i++){
splay(querymx(i,n),root);
ans[i]=size[son[root][0]];
reverse(i,ans[i]);
}
for (i=1;i<n;i++)printf("%d ",ans[i]);
printf("%d\n",ans[n]);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int n,i,x,cnt,root;
int fa[M],son[M][2],size[M],mx[M],data[M],ans[M];
void pushup(int p){
int l=son[p][0],r=son[p][1];
mx[p]=max(data[p],max(mx[l],mx[r]));
size[p]=size[l]+size[r]+1;
}
void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (y==k)k=x;
else {if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){
while (x!=k){
int y=fa[x],z=fa[y];
if (y!=k){
if (son[y][0]==x^son[z][0]==y)rotate(x,k);else rotate(y,k);
}
rotate(x,k);
}
}
int findkth(int k,int rank){
int l=son[k][0],r=son[k][1];
if (size[l]+1==rank)return k;
else if (size[l]>=rank)return findkth(l,rank);
else return findkth(r,rank-size[l]-1);
}
int main(){
mx[0]=-1000000007;
root=1;cnt=2;son[1][0]=2;fa[2]=1;size[1]=2;size[2]=1;
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d",&x);
splay(findkth(root,x+2),root);
int p=findkth(root,x+1);
splay(p,son[root][0]);
son[p][1]=++cnt;
data[cnt]=mx[cnt]=ans[i]=mx[p]+1;
fa[cnt]=p;size[cnt]=1;
pushup(p);pushup(root);
ans[i]=max(ans[i],ans[i-1]);
}
for (i=1;i<=n;i++)printf("%d\n",ans[i]);
}
