下载文档原格式
线段树及其应用场景一、引言线段树（Segment Tree）是一种基于树状数组（Binary Indexed Tree）的数据结构，用于高效地处理区间查询问题。
它在许多算法和数据结构问题中都有广泛应用，如区间最值查询、区间修改和区间统计等。
二、线段树的定义和构建线段树是一种二叉树结构，每个节点代表一个区间。
叶子节点表示原始数据的单个元素，而非叶子节点则表示区间的合并结果。
线段树的构建过程可以通过递归或迭代的方式完成。
3、线段树的应用场景3.1 区间最值查询线段树的一个常见应用是区间最值查询。
给定一个数组，我们希望能够快速找到指定区间内的最大或最小值。
线段树能够在O(log n)的时间复杂度内完成单次查询，并且支持O(log n)的时间复杂度的区间修改操作。
3.2 区间修改线段树还可以用于区间修改问题。
例如，给定一个数组，我们需要对指定区间内的元素进行加法或乘法操作。
线段树可以在O(log n)的时间复杂度内完成单次修改，并且支持O(log n)的时间复杂度的区间查询操作。
3.3 区间统计线段树还可以用于区间统计问题。
例如，给定一个数组，我们需要统计指定区间内满足某种条件的元素个数。
线段树可以在O(log n)的时间复杂度内完成单次统计，并且支持O(log n)的时间复杂度的区间修改操作。
4、线段树的实现和优化4.1 线段树的存储结构线段树可以使用数组或链表来实现。
数组实现简单高效，但需要额外的空间；链表实现节省空间，但查询和修改操作的时间复杂度会增加。
4.2 线段树的查询和修改算法线段树的查询和修改算法可以通过递归或迭代的方式来实现。
递归实现简洁直观，但可能会导致函数调用过多；迭代实现效率较高，但代码复杂度较高。
4.3 线段树的优化技巧线段树的性能可以通过一些优化技巧来提升。
例如，使用延迟标记（Lazy T ag）来延迟区间修改操作的执行，减少递归或迭代次数；使用预处理技巧来提前计算一些中间结果，减少查询或修改的时间复杂度。
1000#include<stdio.h>int main(){int a,b,c;while(scanf("%d%d",&a,&b)!=EOF){c=a+b;printf("%d\n",c);}}1067#include<stdio.h>#include<math.h>#include<stdlib.h>int main(){int a,b;while(scanf("%d%d",&a,&b)!=EOF){if(a>b){int t=a;a=b;b=t;}int k=b-a;int a0=(int)(k*(1+sqrt(5.0))/2);if(a0==a) printf("0\n");else printf("1\n");}}1080#include<stdio.h>#include<stdlib.h>int a[5][5]={5,-1,-2,-1,-3,-1,5,-3,-2,-4,-2,-3,5,-2,-2,-1,-2,-2,5,-1,-3,-4,-2,-1,0};int main(){int ca;scanf("%d",&ca);while(ca--){int n,m,i,j,max[105][105],b[105],d[105];char s[105],c[105];scanf("%d%s",&n,s);scanf("%d%s",&m,c);for(i=1;i<=n;i++){if(s[i-1]=='A') b[i]=0;if(s[i-1]=='C') b[i]=1;if(s[i-1]=='G') b[i]=2;if(s[i-1]=='T') b[i]=3;}for(i=1;i<=m;i++){if(c[i-1]=='A') d[i]=0;if(c[i-1]=='C') d[i]=1;if(c[i-1]=='G') d[i]=2;if(c[i-1]=='T') d[i]=3;}max[0][0]=0;for(i=1;i<=n;i++)max[i][0]=max[i-1][0]+a[b[i]][4];for(i=1;i<=m;i++)max[0][i]=max[0][i-1]+a[4][d[i]];for(i=1;i<=n;i++)for(j=1;j<=m;j++){max[i][j]=max[i-1][j-1]+a[b[i]][d[j]];if(max[i-1][j]+a[b[i]][4]>max[i][j])max[i][j]=max[i-1][j]+a[b[i]][4];if(max[i][j-1]+a[4][d[j]]>max[i][j])max[i][j]=max[i][j-1]+a[4][d[j]];}printf("%d\n",max[n][m]);}}1013#include<stdio.h>#include<algorithm>#include<math.h>#include<stdlib.h>#define PI 3.141592653using namespace std;struct point{double x;double y;}p[30005],res[30005];int cmp(point p1,point p2){return p1.y<p2.y||(p1.y==p2.y&&p1.x<p2.x);}bool ral(point p1,point p2,point p3){if((p2.x-p1.x)*(p3.y-p1.y)<=(p2.y-p1.y)*(p3.x-p1.x)) return true;return false;}double dis(point p1,point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){int i,j;for(i=0;i<n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);sort(p,p+n,cmp);res[0]=p[0];res[1]=p[1];int top=1;for(i=2;i<n;i++){while(top&&ral(res[top-1],res[top],p[i]))top--;res[++top]=p[i];}int len=top;res[++top]=p[n-2];for(i=n-3;i>=0;i--){while(top!=len&&ral(res[top-1],res[top],p[i]))top--;res[++top]=p[i];}double t=0;for(i=0;i<top;i++)t=t+dis(res[i],res[i+1]);printf("%.lf\n",t+2*PI*m);}}1149#include<iostream>#include<cstring>using namespace std;#define inf 0x5fffffffint a[105][105],f[1005],ct[1005],pre[205],n,m,q[105]; int bfs(){int flow=inf,qh=0,qe=1,i;memset(pre,-1,sizeof(pre));q[1]=0;pre[0]=-1;while(qh<qe){int t=q[++qh];for(i=1;i<=n+1;i++)if(pre[i]==-1&&a[t][i]>0){pre[i]=t;if(a[t][i]<flow) flow=a[t][i];if(i==n+1) return flow;q[++qe]=i;}}return -1;}void maxflow(){int res=0,ans,t;while((ans=bfs())!=-1){res=res+ans;t=n+1;while(t)a[pre[t]][t]-=ans;a[t][pre[t]]+=ans;t=pre[t];}}printf("%d\n",res);}int main(){while(scanf("%d%d",&m,&n)!=EOF){memset(f,-1,sizeof(f));memset(a,0,sizeof(a));int i,j,k,t;for(i=1;i<=m;i++)scanf("%d",&ct[i]);for(i=1;i<=n;i++){scanf("%d",&k);for(j=1;j<=k;j++){scanf("%d",&t);if(f[t]!=-1) a[f[t]][i]=inf;else a[0][i]=a[0][i]+ct[t];f[t]=i;}scanf("%d",&k);a[i][n+1]=k;}maxflow();}}1157#include<stdio.h>#include<stdlib.h>int a[105][105],b[105][105];int main(){int max(int x,int y);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;i++)for(j=1;j<=m;j++)scanf("%d",&a[i][j]);b[1][1]=a[1][1];for(i=2;i<=m-n+1;i++){if(a[1][i]<b[1][i-1]) b[1][i]=b[1][i-1];else b[1][i]=a[1][i];}for(i=2;i<=n;i++)for(j=i;j<=i+m-n;j++){a[i][j]=a[i][j]+b[i-1][j-1];if(i==j) b[i][j]=a[i][j];else{if(a[i][j]>b[i][j-1]) b[i][j]=a[i][j];else b[i][j]=b[i][j-1];}}printf("%d\n",b[n][m]);}}1200#include<stdio.h>#include<string.h>bool flag[20000000];int a[300];char s[20000000];int main(){int n,m;while(scanf("%d%d",&n,&m)!=EOF){memset(flag,0,sizeof(flag));scanf("%s",s);int i,j=0,len=strlen(s);memset(a,0,sizeof(a));for(i=0;i<len;i++)a[s[i]]=1;for(i=0;i<256;i++)if(a[i]==1) a[i]=j++;int mod=1,res=0;for(i=0;i<n-1;i++)mod=mod*m;for(i=0;i<n;i++)res=res*m+a[s[i]];flag[res]=1;for(i=n;i<len;i++){res=res%mod*m+a[s[i]];flag[res]=1;}int count=0;mod=mod*m;for(i=0;i<=mod;i++)if(flag[i]==1) count++;printf("%d\n",count);}}1207#include<stdio.h>#include<stdlib.h>int main(){int b,c,i,j,max=0,k,t,r;while(scanf("%d%d",&b,&c)!=EOF){if(b>c){t=b;r=c;}else{t=c;r=b;}max=0;for(i=r;i<=t;i++){j=1;k=i;while(k!=1){j++;if(k%2==0) k=k/2;else k=3*k+1;}if(j>max) max=j;}printf("%d %d %d\n",b,c,max);}//system("pause");}1273#include<iostream>#include<cstring>#include<queue>using namespace std;#define inf INT_MAXint n,m,a[205][205],pre[205],lev[205],num[205]; void bfs(){queue<int>Q;memset(lev,-1,sizeof(lev));memset(num,0,sizeof(num));Q.push(n);lev[n]=0;num[0]=1;while(!Q.empty()){int t=Q.front(),i;Q.pop();for(i=1;i<=n;i++)if(lev[i]==-1&&a[i][t]>0){lev[i]=lev[t]+1;num[lev[i]]++;Q.push(i);}}}int maxflow(){int flow=0,i,ans,cur=1;bfs();while(lev[cur]<n){if(cur==n){ans=inf;while(cur!=1){if(a[pre[cur]][cur]<ans) ans=a[pre[cur]][cur];cur=pre[cur];}cur=n;while(cur!=1){a[pre[cur]][cur]-=ans;a[cur][pre[cur]]+=ans;cur=pre[cur];}flow=flow+ans;}for(i=1;i<=n;i++)if(a[cur][i]>0&&lev[cur]==lev[i]+1){pre[i]=cur;cur=i;break;}if(i>n){lev[cur]=n+1;num[lev[cur]]--;if(num[lev[cur]]==0) break;for(i=1;i<=n;i++)if(a[cur][i]>0&&lev[i]+1<lev[cur]) lev[cur]=lev[i]+1;num[lev[cur]]++;if(cur!=1) cur=pre[cur];}}return flow;}int main(){while(scanf("%d%d",&m,&n)!=EOF){int i,j;memset(a,0,sizeof(a));for(i=0;i<m;i++){int b,c,d;scanf("%d%d%d",&b,&c,&d);a[b][c]+=d;}printf("%d\n",maxflow());}}1285#include<stdio.h>#include<string.h>int num[55];unsigned __int64 f[55][55];int main(){int n,m,ct=0;while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;int i,j,a,k;memset(num,0,sizeof(num));for(i=0;i<n;i++){scanf("%d",&a);num[a]++;}memset(f,0,sizeof(f));f[0][0]=1;for(i=0;i<50;i++)for(j=0;j<=50;j++)for(k=0;k<=num[i+1];k++)f[i+1][j+k]=f[i+1][j+k]+f[i][j];printf("Case %d:\n",++ct);for(i=0;i<m;i++){scanf("%d",&a);printf("%I64d\n",f[50][a]);}}}1364#include <iostream>#include <queue>#include <cstring>using namespace std;int v[105],pre[105],w[105],h[105],flag[105],ct[105],d[105],n,m,num; void add(int a,int b,int c){v[num]=b;pre[num]=h[a];w[num]=c;h[a]=num++;}bool spfa(){int i;queue<int> Q;for(i=0;i<=n;i++){Q.push(i);flag[i]=1;d[i]=0;}while(!Q.empty()){int t=Q.front();Q.pop();flag[t]=0;for(i=h[t];i>=0;i=pre[i]){int p=v[i];if(d[t]+w[i]<d[p]){d[p]=d[t]+w[i];ct[p]++;if(flag[p]==0){Q.push(p);flag[p]=1;}}if(ct[p]>n) return false;}}return true;}int main(){while(cin>>n){if(n==0) break;cin>>m;int a,b,c;char s[3];num=0;memset(flag,0,sizeof(flag));memset(ct,0,sizeof(ct));memset(h,-1,sizeof(h));for(int i=1;i<=m;i++){cin>>a>>b>>s>>c;if(strcmp(s,"gt")==0) add(a-1,a+b,-1-c);else add(a+b,a-1,c-1);}if(spfa()) cout<<"lamentable kingdom"<<endl;else cout<<"successful conspiracy"<<endl;}return 0;}1384#include<stdio.h>#include<stdlib.h>int b[10005],a[600][2];int main(){int ca;scanf("%d",&ca);while(ca--){int M1,M2,M,n,i,j,value;scanf("%d%d",&M1,&M2);M=M2-M1;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d",&a[i][0],&a[i][1]);for(i=0;i<=M;i++)b[i]=-1;b[0]=0;for(i=0;i<n;i++)for(j=0;j+a[i][1]<=M;j++)if(b[j]!=-1){value=b[j]+a[i][0];if(value<b[j+a[i][1]]||b[j+a[i][1]]==-1)b[a[i][1]+j]=value;}if(b[M]==-1) printf("This is impossible.\n");elseprintf("The minimum amount of money in the piggy-bank is %d.\n",b[M]);}}1473#include<stdio.h>#include<math.h>#include<stdlib.h>#include<string.h>int main(){char S[300],c[300][100];int count1=0;while(scanf("%s",S)!=EOF){if(strcmp(S,"END")==0) break;int len=strlen(S),i,count=0,j=0,d;for(i=0;i<len;i++){if(S[i]!=','&&S[i]!='.'){c[count][j]=S[i];j++;}else{c[count][j]='\0';j=0;count++;}}int nw=0,ne=0,sw=0,se=0,n=0,s=0,e=0,w=0;for(i=0;i<count;i++){char cc[10];sscanf(c[i],"%[0-9]",cc);sscanf(cc,"%d",&d);if(strlen(c[i])==strlen(cc)+1){if(c[i][strlen(cc)]=='N') n+=d;if(c[i][strlen(cc)]=='S') s+=d;if(c[i][strlen(cc)]=='E') e+=d;if(c[i][strlen(cc)]=='W') w+=d;}if(strlen(c[i])==strlen(cc)+2){if(c[i][strlen(cc)]=='N'&&c[i][strlen(cc)+1]=='W')nw+=d;if(c[i][strlen(cc)]=='N'&&c[i][strlen(cc)+1]=='E') ne+=d;if(c[i][strlen(cc)]=='S'&&c[i][strlen(cc)+1]=='W') sw+=d;if(c[i][strlen(cc)]=='S'&&c[i][strlen(cc)+1]=='E') se+=d;}}double x=e-w+((ne+se-nw-sw)*sqrt(2))/2;double y=n-s+((nw+ne-sw-se)*sqrt(2))/2;double ss=sqrt(x*x+y*y);count1++;printf("Map #%d\n",count1);printf("The treasure is located at (%.3lf,%.3lf).\n",x,y);printf("The distance to the treasure is %.3lf.\n",ss);printf("\n");}}1505#include<stdio.h>#include<string.h>#include<stdlib.h>int a[510],s[510],t[505][505],num[505],flag[505];int ma(int x,int y){if(x<y) return y;return x;}int main(){int ca;scanf("%d",&ca);while(ca--){int n,m,i,j,k,res;scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);s[0]=0;for(i=1;i<=n;i++)s[i]=s[i-1]+a[i];for(i=1;i<n;i++)t[1][i]=s[i];memset(flag,0,sizeof(flag));for(i=2;i<m;i++)for(j=i;j<n;j++){res=1000000000;for(k=i-1;k<=j-1;k++)if(res>ma(t[i-1][k],s[j]-s[k])) res=ma(t[i-1][k],s[j]-s[k]);t[i][j]=res;}res=s[n];for(i=m-1;i<n;i++)if(ma(t[m-1][i],s[n]-s[i])<res) res=ma(t[m-1][i],s[n]-s[i]);num[0]=n;for(i=1;i<m;i++){int ti=0;for(j=num[i-1];j>m-i;j--){ti=ti+a[j];if(ti>res) break;}num[i]=j;flag[j]=1;}for(i=1;i<n;i++){if(flag[i]==0) printf("%d ",a[i]);else printf("%d / ",a[i]);}printf("%d\n",a[i]);}}1511#include<iostream>#include<cstring>#include<cstdio>#include<queue>#define inf 2000000000using namespace std;int ct,pre[1000005],len[1000005],v[1000005],h[1000005],n,m,vis[1000005],l[1000005]; int a[1000005],b[1000005],c[1000005];queue<int> Q;void add(int a,int b,int c){pre[ct]=h[a];len[ct]=c;v[ct]=b;h[a]=ct++;}void spfa(){int i;memset(vis,0,sizeof(vis));Q.push(1);vis[1]=1;for(i=1;i<=n;i++)l[i]=inf;l[1]=0;while(!Q.empty()){int t=Q.front();for(i=h[t];i!=-1;i=pre[i])if(l[t]+len[i]<l[v[i]]){l[v[i]]=l[t]+len[i];if(vis[v[i]]==0){vis[v[i]]=1;Q.push(v[i]);}}Q.pop();vis[t]=0;}}int main(){int ca;scanf("%d",&ca);while(ca--){scanf("%d%d",&n,&m);int i,j;__int64 res=0;ct=0;memset(h,-1,sizeof(h));for(i=0;i<m;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);add(a[i],b[i],c[i]);}spfa();for(i=2;i<=n;i++)res=res+l[i];ct=0;memset(h,-1,sizeof(h));for(i=0;i<m;i++)add(b[i],a[i],c[i]);spfa();for(i=2;i<=n;i++)res=res+l[i];printf("%I64d\n",res);}}1609#include<stdio.h>#include<stdlib.h>int a[105][105];int main(){int n;while(scanf("%d",&n)!=EOF){if(n==0){printf("*\n");break;}int i,j;for(i=0;i<101;i++)for(j=0;j<101;j++)a[i][j]=0;for(i=0;i<n;i++){int m,k;scanf("%d%d",&m,&k);a[m][k]=a[m][k]+1;}for(i=1;i<101;i++)for(j=1;j<101;j++)if(i*j!=1){if(a[i][j-1]>=a[i-1][j])a[i][j]=a[i][j]+a[i][j-1];elsea[i][j]=a[i][j]+a[i-1][j];}printf("%d\n",a[100][100]);}}1611#include<iostream>using namespace std;int f[30005],cont[30005];int findf(int a){if(f[a]!=a) f[a]=findf(f[a]);return f[a];}void com(int a,int b){int x=findf(a);int y=findf(b);if(x==y) return;if(cont[x]<=cont[y]){f[x]=y;cont[y]=cont[x]+cont[y];}else{f[y]=x;cont[x]=cont[x]+cont[y];}}int main(){int m,n;while(scanf("%d%d",&n,&m)!=EOF&&n){int num,st,i,j,ed;for(i=0;i<n;i++){f[i]=i;cont[i]=1;}for(i=0;i<m;i++){scanf("%d%d",&num,&st);for(j=1;j<num;j++){scanf("%d",&ed);com(st,ed);}}printf("%d\n",cont[findf(0)]);}}1651#include<stdio.h>#include<stdlib.h>long a[105],i,s[105][105],j,t,k;int main(){int n;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%ld",&a[i]);for(i=0;i<n-1;i++)s[i][i+1]=0;for(j=2;j<n;j++)for(i=0;i+j<n;i++){t=100000000;for(k=i+1;k<i+j;k++)if(s[i][k]+s[k][i+j]+a[i]*a[k]*a[i+j]<t)t=s[i][k]+s[k][i+j]+a[i]*a[k]*a[i+j];s[i][i+j]=t;}printf("%ld\n",s[0][n-1]);}}1753#include<iostream>using namespace std;int t[]={19,39,78,140,305,626,1252,2248,4880,10016,20032,35968,12544,29184,58368,51200}; #define SIZE 65535int BFS(int state){int visited[SIZE],d[SIZE],u,v,i;int Qu[SIZE],rear,front;memset(visited,0,sizeof(visited));visited[state]=1;d[state]=0;rear=front=0;Qu[++rear]=state;while(rear!=front){u=Qu[++front];for(i=0;i<16;++i) {v=u^t[i];if(v==0 || v==65535) return d[u]+1;if(visited[v]==0){visited[v]=1;d[v]=d[u]+1;Qu[++rear]=v;}visited[u]=-1;}return -1;}int main(){char ch[5][5];int i,j,start;start=0;for(i=0;i<4;++i)scanf("%s",ch[i]);for(i=0;i<4;++i)for(j=0;j<4;++j)if(ch[i][j]=='b') start^=(1<<((3-i)*4+(3-j)));if(start==0||start==65535) printf("0\n");else{int result=BFS(start);if(result==-1) printf("Impossible\n");else printf("%d\n",result);}}1797#include<stdio.h>#include<string.h>int a[1005][1005],vis[1005],len[1005];int mm(int a,int b){return a<b?a:b;}int main(){int ca,ct=0;scanf("%d",&ca);while(ca--){int n,m;scanf("%d%d",&n,&m);int i,j;memset(a,0,sizeof(a));for(i=1;i<=m;i++)int r,t,l;scanf("%d%d%d",&r,&t,&l);a[r][t]=l;a[t][r]=l;}memset(vis,0,sizeof(vis));for(i=2;i<=n;i++)len[i]=a[1][i];vis[1]=1;for(i=1;i<n;i++){int mmax=0,k;for(j=2;j<=n;j++)if(vis[j]==0&&len[j]>mmax){mmax=len[j];k=j;}vis[k]=1;if(k==n) break;for(j=2;j<=n;j++)if(vis[j]==0){int length=mm(len[k],a[k][j]);if(length>len[j]) len[j]=length;}}printf("Scenario #%d:\n%d\n\n",++ct,len[n]);}}1845#include<iostream>#include<cstring>using namespace std;#define mod 9901__int64 pri[7505],a[100],num[100];void prime(){memset(pri,0,sizeof(pri));int i,j;for(i=2;i<=90;i++)for(j=2;i*j<=7500;j++)j=0;for(i=2;i<=7500;i++)if(pri[i]==0) pri[j++]=i;}__int64 yu(__int64 a,__int64 b){__int64 res=1,c=mod;while(b){if(b%2==0){a=(a%c)*(a%c)%c;b=b/2;}else{res=res*a%c;b--;}}return res;}__int64 f(__int64 a,__int64 b){if(b==0) return 1;if(b==1) return (1+a)%mod;if(b%2==0) return (yu(a,b/2)+(1+yu(a,b/2+1))*f(a,b/2-1))%mod;return ((1+yu(a,b/2+1))*f(a,b/2))%mod;}int main(){prime();int n,m;while(scanf("%d%d",&n,&m)!=EOF){int i,j=0;if(n==0){printf("1\n");continue;}for(i=0;pri[i]*pri[i]<=n;i++)if(n%pri[i]==0){int t=0;while(n%pri[i]==0){t++;n=n/pri[i];}a[j]=pri[i];num[j++]=t;}if(n!=1){a[j]=n;num[j++]=1;}__int64 res=1;for(i=0;i<j;i++)res=res*f(a[i],num[i]*m)%mod;printf("%I64d\n",res);}}1941#include<stdio.h>#include<string.h>int h[22],s[22];char c[1025][2050],ss[1025][2050];void solve(int m){int i,j;if(m==1){h[m]=4;s[m]=2;c[1][1]=' ';c[1][4]=' ';c[1][2]='/';c[1][3]='\\';c[2][1]='/';c[2][2]='_';c[2][3]='_';c[2][4]='\\';memcpy(ss,c,sizeof(c));}if(m!=1){memset(c,' ',sizeof(c));solve(m-1);h[m]=h[m-1]*2;s[m]=s[m-1]*2;for(i=s[m-1]+1;i<=s[m];i++)for(j=1;j<=h[m-1];j++)c[i][j]=c[i][j+h[m-1]]=ss[i-s[m-1]][j];for(i=1;i<=s[m-1];i++)for(j=h[m-1]/2*3;j>h[m-1]/2;j--){c[i][j]=ss[i][j-h[m-1]/2];c[i][j-h[m-1]/2]=' ';}memcpy(ss,c,sizeof(c));}}int main(){int n,i,j,k;h[0]=2;solve(10);while(scanf("%d",&n)!=EOF&&n){for(i=1;i<=s[n];i++){for(j=h[9]-h[n]/2+1;j<=h[9]+i;j++)printf("%c",c[i][j]);printf("\n");}printf("\n");}}1947#include<iostream>#include<algorithm>using namespace std;#define big 10000000int num[155],flag[155],son[155][155],step[155][155],n,m,root; void dsf(int v)int i,j,k;if(v!=root) step[v][1]=num[v]+1;else step[v][1]=num[v];for(i=0;i<num[v];i++){dsf(son[v][i]);for(j=m-1;j>=1;j--)if(step[v][j]<big){for(k=1;k+j<=m;k++)step[v][k+j]=min(step[v][k+j],step[v][j]+step[son[v][i]][k]-2);}}}int main(){while(scanf("%d%d",&n,&m)!=EOF){memset(num,0,sizeof(num));memset(flag,0,sizeof(flag));int i,a,b,j;for(i=1;i<n;i++){scanf("%d%d",&a,&b);flag[b]=1;son[a][num[a]++]=b;}for(i=1;i<=150;i++)for(j=1;j<=150;j++)step[i][j]=big;for(i=1;i<=n;i++)if(flag[i]==0){root=i;dsf(i);break;}int res=big;for(i=1;i<=n;i++)if(step[i][m]<res) res=step[i][m];printf("%d\n",res);}}1964#include<stdio.h>#include<string.h>char s[1005][1005][2];int a[1005][1005],pre[1005],next[1005];int main(){int ca;scanf("%d",&ca);while(ca--){int n,m,i,j,k,res=0;scanf("%d%d",&n,&m);for(i=0;i<n;i++)for(j=0;j<m;j++)scanf("%s",s[i][j]);for(i=0;i<m;i++)if(strcmp(s[0][i],"F")==0) a[0][i]=1;else a[0][i]=0;for(i=1;i<n;i++)for(j=0;j<m;j++)if(strcmp(s[i][j],"F")==0) a[i][j]=a[i-1][j]+1;else a[i][j]=0;for(i=0;i<n;i++){memset(pre,-1,sizeof(pre));for(j=1;j<m;j++)for(k=j-1;k!=-1;k=pre[k])if(a[i][k]<a[i][j]){pre[j]=k;break;}for(j=0;j<m;j++)next[j]=m;for(j=m-2;j>=0;j--)for(k=j+1;k!=m;k=next[k])if(a[i][k]<a[i][j]){next[j]=k;break;}for(j=0;j<m;j++)if((next[j]-pre[j]-1)*a[i][j]>res) res=(next[j]-pre[j]-1)*a[i][j];}printf("%d\n",res*3);}}。
线段树的概念与应用线段树（Segment Tree）是一种用于解决区间查询问题的数据结构。
它可以高效地支持以下两种操作：区间修改和区间查询。
线段树的应用非常广泛，在离线查询、区间统计、区间更新等问题中有着重要的作用。
一、概念线段树是一颗二叉树，其中每个节点代表了一个区间。
根节点表示整个待查询区间，而叶子节点表示的是单个元素。
每个内部节点包含了其子节点所代表区间的并集。
二、构建线段树线段树的构建过程是自底向上的。
将待查询数组划分成一颗满二叉树，并将每个区间的和存储在相应的节点中。
对于叶子节点，直接存储对应元素的值。
而非叶子节点的值可以通过其子节点的值计算得到。
三、线段树的查询对于区间查询操作，可以通过递归方式实现。
从根节点开始，判断查询区间和当前节点所代表的区间是否有交集。
若没有交集，则返回当前节点的默认值。
若查询区间包含当前节点所代表的区间，则返回当前节点存储的值。
否则，将查询区间分割成左右两部分继续递归查询。
四、线段树的更新对于区间更新操作，也可以通过递归方式实现。
与查询操作类似，首先判断查询区间和当前节点所代表的区间的关系。
若没有交集，则无需更新。
若查询区间包含当前节点所代表的区间，则直接更新当前节点的值。
否则，将更新操作分割成左右两部分继续递归更新。
五、应用案例：区间最值查询一个常见的线段树应用是求解某个区间的最值。
以查询区间最小值为例，可以通过线段树来高效地解决。
首先构建线段树，然后进行区间查询时，分为以下几种情况处理：若当前节点所代表的区间完全包含于查询区间，则直接返回该节点的值；若当前节点所代表的区间与查询区间没有交集，则返回默认值；否则，将查询区间分割成左右两部分继续递归查询，最后返回两个子区间查询结果的较小值。
六、总结线段树是一种非常有用的数据结构，能够高效地解决区间查询问题。
通过合理的构建和操作，线段树可以应用于多种场景，如区间最值查询、离线查询等。
熟练掌握线段树的概念和应用方法，对解决问题具有重要意义。
ACM训练计划建议（转）前⾔：⽼师要我们整理⼀份训练计划给下⼀届的学弟学妹们，整理出来了，费了不少笔墨，就也将它放到博客园上供⼤家参考。
菜鸟之作，⼤⽜勿喷，如有不当或补充之处，欢迎指出。
本建议书分为三个阶段，⼤⼀、⼤⼆、⼤三。
⼤四暂没整理，⼀⽅⾯是⼤四要⾯临考验和找⼯作的问题，坚持继续acm的很少，另⼀⽅⾯，本⼈还没⼤四……下⾯以个⼈经验分析⼀下这三个阶段建议学习的内容和具体的训练计划。
正⽂：⼤⼀（第⼀阶段）： ⼤⼀是时间最充裕的⼀段时间，也是可塑性最⾼的⼀个阶段。
⼤⼀你有很多⾃由时间可以⾃⼰分配，建议这段时间先打好c/c++基础，或者是任何⼀门语⾔的基础，尽量做到“半精通”。
因为像c++这种语⾔，⼏年内达到精通都是不可能的。
⽽我这⾥所说的“半精通”，实际上是将课本完全搞透的基础上，再在课外拓展⼀些内容，加深对语⾔本⾝的理解。
为什么我这⾥强调语⾔的重要性呢？⼀⽅⾯是为了以后搞acm的需要，语⾔通畅了，可以保证你实现⼤部分算法没有障碍，⽽⽐赛时，时间是很重要的。
另⼀⽅⾯，也是你⾝为学计算机的学⽣的⼀个必须要学习的能⼒，语⾔就是你⼿中的剑，以后能披荆斩棘⾛多远，剑有多锋利占很⼤因素。
另⼀⽅⾯，建议打好数学的基础。
学长⾝为过来⼈，深受数学烂的苦。
acm越到后期的时候，其实⽤到的数学知识就越多。
像有些题⽬，⾚裸裸的就是求积分，还有⼀些题⽬，将求期望嵌⼊到了DP的题⽬⾥…… 其实这些还好说，都是显式的题⽬，还有⼀种隐式的东西，对acm帮助最⼤，那就是数学思维。
有数学思维和没有数学思维的区别，就是⼀道题有N种思路和N*N种思路的区别。
这越到后期越明显，思路很重要，⽐赛时⾯对⼀道题团队⾥⾸先要有多种思路可供分析，然后⼤家讨论哪种思路是最可⾏的，确定之后就是最擅长这个思路的⼈实现算法。
如果分析⼀道题⽬的时候，产⽣的思路很少，那么⽆疑会降低这道题的AC命中率。
啰嗦了这么多，其实我就想给⼤⼀的新⽣们强调两点，语⾔和数学。
第一阶段初级：第1周-第2周（共80题）项目时间必做题目基本算法枚举第1周poj1753,poj2965贪心poj1328,poj2109,poj2586分治法递推构造法poj3295模拟法poj1068,poj2632,poj1573,poj2993,poj2996图算法图的深度优先遍历和广度优先遍历第1周最短路径算法poj1860,poj3259,poj1062,poj2253,poj1125,poj2240最小生成树算法poj1789,poj2485,poj1258,poj3026拓扑排序poj1094二分图的最大匹配poj3041,poj3020最大流的增广路算法poj1459,poj3436数据结构串第1周poj1035,poj3080,poj1936排序poj2388,poj2299简单并查集的应用哈希表和二分查找等高效查找法poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503哈夫曼树poj3253堆树poj2513简深度优先搜索第2周poj2488,poj3083,poj3009,单搜索poj1321,poj2251广度优先搜索poj3278,poj1426,poj3126,poj3087.poj3414简单搜索技巧和剪枝poj2531,poj1416,poj2676,poj1129动态规划背包问题第2周poj1837,poj1276型如下表的简单DP poj3267,poj1836,poj1260,poj2533,poj3176,poj1080,poj1159数学组合数学第2周POJ3252,poj1850,poj1019,poj1942数论poj2635,poj3292,poj1845,poj2115计算方法poj3273,poj3258,poj1905,poj3122计算几何学几何公式第2周叉积和点积的运用poj2031,poj1039多边型的简单算法和相关判定poj1408,poj1584凸包poj2187,poj1113第二阶段中级：第3周-第4周（共85题）项目时间必做题目基本算法C++的标准模版库的应用第3周poj3096,poj3007较为复杂的模拟题的训练poj3393,poj1472,poj3371,poj1027,poj2706图算差分约束系统的建立和求解第3周poj1201,poj2983法最小费用最大流poj2516,poj2516,poj2195双连通分量poj2942强连通分支及其缩点poj2186图的割边和割点poj3352最小割模型poj3308数据结构线段树第3周poj2528,poj2828,poj2777,poj2886,poj2750静态二叉检索树poj2482,poj2352树状树组poj1195,poj3321RMQ poj3264,poj3368并查集的高级应用poj1703,2492KMP算法poj1961,poj2406搜索最优化剪枝和可行性剪枝第3周搜索的技巧和优化poj3411,poj1724记忆化搜索poj3373,poj1691动态规划较为复杂的动态规划第4周poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034记录状态的动态规划poj3254,poj2411,poj1185树型动态规划poj2057,poj1947,poj2486,poj3140数学组合数学第4周poj1286,poj2409,poj3270,poj1026高斯消元法poj2947,poj1487,poj2065,poj1166,poj1222概率问题poj3071,poj3440GCD、扩展的欧几里德poj3101计算方法poj2976,poj3150,poj3422,poj3070, poj3301随机化算法poj3318,poj2454杂题poj1870,poj3296,poj3286,poj1095计算几何学坐标离散化第4周扫描线算法poj1765,poj1177,poj1151,poj3277,poj2280,poj3004边形的内核poj3130,poj3335几何工具的综合应用poj1819,poj1066,poj2043,poj3227,poj2165,poj3429第三阶段高级：第5周-第6周（共59题）项目时间必做题目基本算法代码快速写成第5周poj2525,poj1684,poj1421,poj1048,poj2050,poj3306保证正确性和高效性poj3434图算法度限制最小生成树和第K最短路第5周poj1639最短路,最小生成树,二分图,最大流问题的相关理论poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446最优比率生成树poj2728最小树形图poj3164次小生成树无向图、有向图的最小环数据结trie图的建立和应用第5周poj2778 LCA和RMQ问题poj1330双端队列和它的应用poj2823构左偏树后缀树poj3415,poj3294搜索较麻烦的搜索题目训练第5周poj1069,poj3322,poj1475,poj1924,poj2049,poj3426广搜的状态优化poj1768,poj1184,poj1872,poj1324,poj2046,poj1482深搜的优化poj3131,poj2870,poj2286动态规划需要用数据结构优化的动态规划第6周poj2754,poj3378,poj3017四边形不等式理论较难的状态DP poj3133数学组合数学第6周poj2888,poj2154博奕论poj3317,poj1085计算几何学半平面求交第6周poj3384,poj2540可视图的建立poj2966点集最小圆覆盖对踵点poj2079综合题第6周poj3109,poj高手给的训练计划一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的，主要时间是花在思考算法上，不是花在写程序与debug上。
POJ上一些题目在http://162.105.81.202/course/problemSolving/可以找到解题报告。
《算法艺术与信息学竞赛》的习题提示在网上可搜到一.动态规划参考资料：刘汝佳《算法艺术与信息学竞赛》《算法导论》推荐题目：/JudgeOnline/problem?id=1141简单/JudgeOnline/problem?id=2288中等，经典TSP问题/JudgeOnline/problem?id=2411中等，状态压缩DP/JudgeOnline/problem?id=1112中等/JudgeOnline/problem?id=1848中等，树形DP。
可参考《算法艺术与信息学竞赛》动态规划一节的树状模型/show_problem.php?pid=1234中等，《算法艺术与信息学竞赛》中的习题/JudgeOnline/problem?id=1947中等，《算法艺术与信息学竞赛》中的习题/JudgeOnline/problem?id=1946中等，《算法艺术与信息学竞赛》中的习题/JudgeOnline/problem?id=1737中等，递推/JudgeOnline/problem?id=1821中等，需要减少冗余计算/show_problem.php?pid=2561中等，四边形不等式的简单应用/JudgeOnline/problem?id=1038较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答/JudgeOnline/problem?id=1390较难，《算法艺术与信息学竞赛》中有解答/JudgeOnline/problem?id=3017较难，需要配合数据结构优化（我的题目^_^）/JudgeOnline/problem?id=1682较难，写起来比较麻烦/JudgeOnline/problem?id=2047较难/JudgeOnline/problem?id=2152难，树形DP/JudgeOnline/problem?id=3028难，状态压缩DP，题目很有意思/JudgeOnline/problem?id=3124难/JudgeOnline/problem?id=2915非常难二.搜索参考资料：刘汝佳《算法艺术与信息学竞赛》推荐题目：/JudgeOnline/problem?id=1011简单，深搜入门题/JudgeOnline/problem?id=1324中等，广搜/JudgeOnline/problem?id=2044中等，广搜/JudgeOnline/problem?id=2286较难，广搜/JudgeOnline/problem?id=1945难，IDA*，迭代加深搜索，需要较好的启发函数/JudgeOnline/problem?id=2449难，可重复K最短路，A*。
