【写在最前面】
过了三个月，终于又开始更新博客了。
因为省选成绩不堪入目，所以CCF都懒得给D类名额了，就理所当然地被赶回去学了一个月的文化课，莫名其妙地考了一场期末考。（瞬间爆炸）
首先祝贺我校的大爷取得了1金1银3铜的好成绩。（大雾）
在此期间想了很多，关于高二到底还要不要停课搞OI，以及以后想到哪个大学去，将来要做什么。
OI就是一个弱肉强食的世界，像我这种蒟蒻难逃滚粗的命运。
（请原谅我满满的负能量）
8
5
2016
5
2016
论蒟蒻的花样作死之某度之星
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);
}
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
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]);
}
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]);
}
12
23
2015
23
2015
论蒟蒻的花样作死之树状数组
问：你这个乡村学校的小学生，为什么要学劼劼劼呢？
答：因为窝一下做了太多的树状数组，懒得一篇一篇写了。
问：既然线段树可以代替树状数组，那么为什么要树状数组呢？
答：树状数组好写啊Orz。
问：那我可以不看冗长的介绍过程吗？
答：如果机房的门要关了或者你急着要泡妹子，请跳至最后一目。
【简介】
首先普通的一维树状数组就不说了，如果你不知道，戳这。
那么窝萌阔以看到：普通的树状数组支持单点修改、片段和。
显然树状数组是解决逆序对问题的最好方法。
某大神表示阔以用树状数组来维护区间最值，不明觉厉~
inline void init()
{
CLR(arr,0);
for(int i=1;i<=N;++i)
for(int j=i;j<=N&&arr[j]<num[i];j+=lowbit(j))
arr[j]=num[i];
}
inline int query(int L,int R)
{
int res=0;
for(--L;L<R;){
if(R-lowbit(R)>=L){res=max(res,arr[R]);R-=lowbit(R);}
else{res=max(res,num[R]);--R;}
}
return res;
}
inline void update(int x,int val)
{
int ori=num[x];
num[x]=val;
if(val>=ori)
for(int i=x;i<=N&&arr[i]<val;i+=lowbit(i))
arr[i]=val;
else{
for(int i=x;i<=N&&arr[i]==ori;i+=lowbit(i))
{
arr[i]=val;
for(int j=lowbit(i)>>1;j;j>>=1)
arr[i]=max(arr[i],arr[i-j]);
}
}
}
那么树状数组可不可以支持区间修改呢？
让窝萌先来解决一个子问题：维护一个序列，支持区间修改、单点求值。
那么差分，令d[i]=a[i]-a[i-1]，d[1]=a[1]，那么显然[tex]a[i] = \sum\limits_{j = 1}^n {d[j]}[/tex]
修改区间[l,r]，则可以通过前缀和得到：d[l]+=k,d[r+1]-=k。
那么要求区间和怎么办呢？
通过简单的推导可以得到：
[tex]\sum\limits_{i = 1}^x {a[i]} = \sum\limits_{i = 1}^x {d[i]*(x - i + 1) = (x + 1)*\sum\limits_{i = 1}^x {d[i]} - \sum\limits_{i = 1}^x {d[i]*i} }[/tex]
那么再开一个树状数组来维护d[i]*i就阔以辣！
接着看二维树状数组。
显然根据树状数组的定义再加一维就阔以了。
即令tree[i][j]为矩阵[i-lowbit(i)+1,j-lowbit(j)+1]~[i,j]的片段和。
对于二维树状数组的区间修改和求和，可以通过二维前缀和的性质推出。
这里的d[i]有另一个定义，表示i~n这一段的都加上d[i]。
那么扩展到二维，d[i][j]表示矩阵[i,j]~[n,m]的都加上d[i][j]。
修改矩阵[x1,y1]~[x2,y2]，那么d[x1][y1]+=k,d[x1][y2+1]-=k,d[x2+1][y1]-=k,d[x2+1][y2+1]+=k。
求[1,1]~[x,y]，就是p-q。
[tex]p = (x + 1)(y + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]} } + \sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]*i*j} }[/tex]
[tex]q = (x + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]*j + (y + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]} } } } *i[/tex]
[tex]
显然我讲的很不详细，所以戳这
（悄悄地告诉你其实窝前面也是抄的论文）
【例题】
BZOJ2789
首先看到一个贪心性质，即第一个串中第k次出现的某个字母对应的一定是第二个中第k次出现的。
那么求个逆序对就阔以了。
BZOJ2743
先求出每个元素下一个与它相同的是第几个。
显然如果[l,r]中有两个同样的元素，该元素的编号为i>=l，则next[i]<=r就阔以了。
那么对询问进行离线操作，其余的还是程序说得更清楚，所以开始看程序吧。
BZOJ1452
对于每种颜色开个二维树状数组就水过了。。。
BZOJ3132
论文题，看完了绝逼会做。
BZOJ3038
显然发现了一个神奇的性质：一个数只要开根了7次后就会变成1，然后就不变了。
那么就用并查集维护变成1的区间不用改了，然后用树状数组维护整个序列。
BZOJ1106
如果两个相同的数间有x个未消掉的数，那么就需要交换x次。
那么只要知道区间内只出现过一次的数的个数就阔以啦！
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,i;
long long ans;
char a[M],b[M];
int c[M],tree[M],now[30];
int q[27][M];
int query(int x){
int ans=0;
for (int i=x;i>0;i-=i&-i)ans+=tree[i];
return ans;
}
void update(int x){
for (int i=x;i<=n;i+=i&-i)tree[i]++;
}
int main(){
scanf("%d",&n);
scanf("%s",a+1);
scanf("%s",b+1);
for (i=1;i<=n;i++)q[a[i]-'A'][++q[a[i]-'A'][0]]=i;
for (i=1;i<=n;i++)c[i]=q[b[i]-'A'][++now[b[i]-'A']];
for (i=n;i>=1;i--){
ans+=query(c[i]);
update(c[i]);
}
printf("%lld\n",ans);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,m,p,i,l;
int a[M],now[M],next[M],ans[M],tree[M];
struct shit{int l,r,id;}q[M];
int cmp(shit a,shit b){return a.l<b.l;}
int query(int x){
int ans=0;
for (int i=x;i>0;i-=i&-i)ans+=tree[i];
return ans;
}
void update(int x,int p){
for (int i=x;i<=n;i+=i&-i)tree[i]+=p;
}
int main(){
scanf("%d%d%d",&n,&p,&m);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=n;i>0;i--)next[i]=now[a[i]],now[a[i]]=i;
for (i=1;i<=p;i++)if (next[now[i]])update(next[now[i]],1);
for (i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);
l=1;
for (i=1;i<=m;i++){
while (l<q[i].l){
if (next[l])update(next[l],-1);
if (next[next[l]])update(next[next[l]],1);
l++;
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for (i=1;i<=m;i++)printf("%d\n",ans[i]);
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,i,j,opt,q,x,y,ch,x1,x2,y1,y2;
int a[310][310];
int tree[110][310][310];
void update(int opt,int x,int y,int p){
for (int i=x;i<=n;i+=i&-i)
for (int j=y;j<=m;j+=j&-j)
tree[opt][i][j]+=p;
}
int query(int opt,int x,int y){
int ans=0;
for (int i=x;i;i-=i&-i)
for (int j=y;j;j-=j&-j)
ans+=tree[opt][i][j];
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
scanf("%d",&a[i][j]);
update(a[i][j],i,j,1);
}
scanf("%d",&q);
while (q--){
scanf("%d",&opt);
if (opt==1){
scanf("%d%d%d",&x,&y,&ch);
update(a[x][y],x,y,-1);
a[x][y]=ch;
update(a[x][y],x,y,1);
}else{
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&ch);
printf("%d\n",query(ch,x2,y2)-query(ch,x1-1,y2)-query(ch,x2,y1-1)+query(ch,x1-1,y1-1));
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[10];
int n,m,x1,x2,y1,y2,ch;
int tree[2100][2100][4];
void update(int x,int y,int p){
for (int i=x;i<=n;i+=i&-i)
for (int j=y;j<=m;j+=j&-j){
tree[i][j][0]+=p;
tree[i][j][1]+=p*x;
tree[i][j][2]+=p*y;
tree[i][j][3]+=p*x*y;
}
}
int query(int x,int y){
int ans=0;
for (int i=x;i;i-=i&-i)
for (int j=y;j;j-=j&-j)
ans=ans+tree[i][j][0]*(x+1)*(y+1)-tree[i][j][1]*(y+1)-tree[i][j][2]*(x+1)+tree[i][j][3];
return ans;
}
int main(){
scanf("%s",s);
scanf("%d%d",&n,&m);
while (scanf("%s",s)!=EOF){
if (s[0]=='L'){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&ch);
update(x1,y1,ch);
update(x2+1,y1,-ch);
update(x1,y2+1,-ch);
update(x2+1,y2+1,ch);
}else{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1));
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
int n,m,i,opt,x,y;
int f[100010];
ll a[100010],tree[100010];
int search(int x){
if (!f[x])f[x]=x;
if (f[x]!=x)f[x]=search(f[x]);
return f[x];
}
ll query(int x){
ll ans=0;
for (int i=x;i;i-=i&-i)ans+=tree[i];
return ans;
}
void update(int x,ll y){
for (int i=x;i<=n;i+=i&-i)tree[i]+=y;
}
void solve(int x,int y){
for (int i=search(x);i<=y;i=search(i+1)){
ll tmp=(ll)sqrt(a[i]);
update(i,tmp-a[i]);
a[i]=tmp;
if (a[i]<=1)f[i]=search(i+1);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%lld",&a[i]);
if (a[i]<=1)f[i]=i+1;
update(i,a[i]);
}
scanf("%d",&m);
for (i=1;i<=m;i++){
scanf("%d%d%d",&opt,&x,&y);
if (x>y)swap(x,y);
if (!opt)solve(x,y);else printf("%lld\n",query(y)-query(x-1));
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,ans;
int a[100010],tree[100010],pre[100010];
void update(int x,int y){
for (int i=x;i<=2*n;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;
}
int main(){
scanf("%d",&n);
for (i=1;i<=2*n;i++)scanf("%d",&a[i]);
for (i=1;i<=2*n;i++){
if (!pre[a[i]])pre[a[i]]=i,update(i,1);
else{
ans+=query(i)-query(pre[a[i]]);
update(pre[a[i]],-1);
}
}
printf("%d\n",ans);
}
