中国地质大学复试ACM测试题库

地大ACM题库

2017.5

目录

1.环境设置-3-

1.1.头文件-3-

1.2.Ubuntu相关设置-3-

2.基本算法-3-

2.1.三分（极小值）-3-

3.数论-4-

3.1.判断质数-4-

3.2.筛法打质数表-4-

3.3.分解质因数（打一个表）-4-

3.4,快速零取模-4-

3.5.费马小定理求逆元（M必须是质数）-5-

3.6.lucas定理-5-

3.7.扩展欧几里得-5-

3.8.扩展欧几里得求逆元（只需gcd（a,M）==l）-5-

3.9.欧拉函数-5-

3.10.欧拉函数打表-6-

3.11.中国剩余定理不互质-6-

3.12.高斯消元-7-

3.13.二进制下的高斯消元-7-

3.14.组合数打表-8-

4.图论-8-

4.1.邻接表-8-

4.2.spfa-8-

4.3.dijkstra+heap-9-

4.4.kruskal-10-

4.5.prim+heap-12-

4.6.最小树形图朱刘算法-13-

4.7.树的直径-14-

4.8.LCA的tarjan离线算法-15-

4.9.二分图最大匹配匈牙利算法-16-

5.数据结构-17-

5.1.离散化-17-

5.2.一维树状数组-18-

5.3.RMQ-18-

5.4.线段树-18-

5.5.对一棵树进行线段树操作-19-

5.6.KMP-20-

6.数学-21-

6.1.DeBruijn序列（格雷码）-21-

6.2.矩阵类-21-

6.3.巴什博弈（取石子游戏，1堆，一次取m个）-23-

6.4.尼姆博弈（取m堆石子游戏，一次只能在一堆里取）-24-

6.5.威佐夫博弈（取（2堆）石子游戏，一次取一堆的任意或两堆的相同）-24-

7.动态规划-25-

7.1.二维最大子段和-25-

8.计算几何-26-

9.其他-37-

9.1.旋转的坐标变换-37-

9.2.蔡勒公式-37-

9.3.归并排序求逆序数-38-

9.4.卡特兰数-38-

10.黑科技-38-

10.1.输入输出优化-38-

10.2.强制02优化-39-

10.3.其他-39-

1.环境设置

1.1.头文件

1#include<cstdio>

2#include<cstdlib>

3#include<cstring>

4#include<cmath>

5#include<ctime>

6#include<iostream>

7#include<algorithm>

8#include<string>

9#include<vector>

10#include<deque>

11#include<list>

12#include<set>

13#include<map>

14#include<stack>

15#include<queue>

16#include<numeric>

17#include<iomanip>

18#include<bitset>

19#include<sstream>

20#include<fstream>

21#definedebugputs("----")

22#definepi(acos(-1.0))

23#defineeps(le-8)

24#defineinf(1<<30)

25usingnamespacestd;

26intmain()

27{

28

29returnO;

30}

1.2.Ubuntu相关设置

CodeBlocks终端命令行：gnome-terminal--disable-factory-t$TITLE-x

计算器：gnome-calculator,xcalc

2.基本算法

2.1.三分（极小值）

1doubleleft,right,midl,mid2;

2left=-le7;

3right=le7;

4while(fabs(left-right)>eps)

5{

midl=(left+right)/2;

mid2=(midl+right)/2;

8if(f(midl)<f(mid2))

right=mid2;

10else

11left=midl;

12)

3.数论

3.1.判断质数

iintisprime(longlongn)

2(

3if(n==l)

4returnO;

5longlongx=sqrt(n);

6for(inti=2;i<=x;i++)

7if(n%i==0)

8returnO;

9returnl;

10}

3.2.筛法打质数表

iconstintNP=1000005;

2intispri[NP]={}Jprime[NP]={},pcnt=0;

3voidgetprime()

4{

5ispri[0]=ispri[l]=l;

6for(longlongi=2;i<NP;i++)

7if(ispri[i]==0)

8{

9prime[++pcnt]=i;

10for(longlongj=i*i;j<NP;j+=i)

11ispri[j]=l;

12}

13)

3.3.分解质因数(打一个表)

iinta[1000000]={}Jpcnt=0;

2voidpdec(intn)

3(

4intx=sqrt(n);

5for(inti=l;prime[i]<=x;i++)

6if(n%prime[i]==0)

7{

8a[++pcnt]=prime[i];

9n/=prime[i];

10i--；

11)

12if(n!=l)

13a[++pcnt]=n;

14)

3.4.快速鬲取模

iconstlonglongM=1000000007;

2longlongquickpow(longlonga^longlongb)

3{

4if(b<0)return0;

5longlongret=l;

6a%=M;

7for(;b;b>>=l,a=(a*a)%M)

8if(b&l)

9ret=(ret*a)%M;

10returnret;

11)

3.5.费马小定理求逆元(M必须是质数)

ilonglonginv(longlonga)

2{

3returnquickpow(a,M-2);

4)

3.6.Iucas定理

1constintfcnt=M;

2longlongfac[fcnt];

3voidgetfac()

4{

5fac[0]=fac[l]=l;

6for(inti=2;i<fcnt;i++)

7fac[i]=fac[i-l]*i%M;

8)

9longlongC(longlongn?longlongm^longlongM)

10{

11if(n<m)

12returnO;

13returnfac[n]*inv(fac[m],M)%M*inv(fac[n-m]

14)

15longlonglucas(longlongn,longlongm,longlongM)

16{

17if(m==0)

18returnl;

19return(iucas(n/M,m/M,M)*C(n%M,m%M,M))%M;

20)

3.7.扩展欧几里得

ilonglongexgcd(longlonga,longlongb,longlong&Xjlonglong&y)

2{

3if(b==0)

4{

5x=l;

6y=0;

7returna;

8}

9longlongans=exgcd(b,a%b,x,y);

10longlongtemp=x;

11x=y；

12y=temp-(a/b)*y;

13returnans;

14}

3.8.扩展欧几里得求逆元(只需gcd(a,M)=1)

ilonglonginv(longlonga?longlongM)

2{

3longlongx.y;

4longlongt=exgcd(a,M,x,y);

5if(t!=l)

6return-1;

7return(x%M+M)%M;

8)

3.9.欧拉函数

longlongphi(longlongn)

2

3longlongans=n;

4longlongx=sqrt(n);

5for(longlongi=2;i<=x;i++)

6(

7if(n%i==0)

8{

9while(n%i==0)

10n/=i;

11ans=ans/i*(i-l);

12)

13}

14if(n>l)

15ans=ans/n*(n-l);

16returnans;

17)

3.10.欧拉函数打表

iconstintMAXN=10005;

2longlongphi[MAXN];

3voidgetphi()

4{

5for(inti=l;i<MAXN;i++)

6phi[i]=i;

7for(inti=2;i<MAXN;i++)

8if(phi[i]==i)

9for(intj=i;j<MAXN;j+=i)

10phi[j]=phi[j]/i*(i-l);

11}

3.11.中国剩余定理不互质

ivoidcrt()

2{

3intt;

4while(cin>>t)

5{

6intflag=l;

7longlongnl^al;

8if(t)

9scanf(“%nd%lld"，&nl,&al),t--;

10while(t--)

11{

12longIongn2,a2,kl,k2;

13scanf("%lld%lld",&n2,&a2);

14if(flag==0)

15continue;

16longlongd:exgcd(nl,n2,kl,k2);

17if((a2-al)%d!=0)

18flag=0;

19if(flag)

20{

21kl=(kl*(a2-al)/d%(n2/d)+n2/d)%(n2/d);

22longlonga=nl*kl+al;

23longlongn=nl/d*n2;

24nl=n;

25al=a;

26}

27}

28if(flag)

29returnal;

30else

31return-1;

32)

33}

3.12.高斯消元

iconstintMAXN=105;

2doublea[MAXN][MAXN],b[MAXN];〃要注意-0.000的情况+eps

3intgauss_elimination(intredoublea[][MAXN]doubleb[])

4{

5inti,jjk,row;

6double

7for(k=l;k<=n;k++)

8{

9for(mx=0Ji=k;i<=n;i++)

10if(fabs(a[i][k])>fabs(mx))

11mx=a[row=i][k];

12if(fabs(mx)<eps)

13returnO;

14if(row!=k)

15{

16for(j=k;j<=n;j++)

17swap(a[k][j],a[row][j]);

18swap(b[k],b[row]);

19)

20for(j=k+l;j<=n;j++)

21for(a[k][j]/=mx,i=k+l;i<=n;i++)

22a[i][j]-=a[i][k]*a[k][j];

23for(b[k]/=mx>i=k+l;i<=n;i++)

24b[i]-=b[k]*a[i][k];

25}

26for(i=n;i>=l;i--)

27for(j=i+l;j<=n;j++)

28b[i]-=a[i][j]*b[j];

29returnl;

30}

3.13.二进制下的高斯消元

iconstintMAXN=105;

2inta[MAXN][MAXN],b[MAXN];

3voidgauss^intn,intaf][MAXN]?intb[])

4{

5for(inti=l;i<=n;i++)

6{

7intk;

8for(intj=i;j<=n;j++)

9if(a[j][i])

10{

11k=j;

12break;

13}

14for(intj=l;j<=n;j++)

15swap(a[i][j],a[k][j]);

16swap(b[i],b[k]);

17for(intj=l;j<=n;j++)

18if(i!=j&&a[j][i])

19{

20for(k=l;k<=n;k++)

21a[j][k]A=a[i][k];

22b[j]A=b[i];

23)

24)

25)

3.14.组合数打表

iconstintCN=20;

2longlongc[CN][CN]={};

3voidcinit()

4{

5for(inti=0;i<CN;i++)

6(

7c[i][0]=c[i][i]=l;

8for(intj=l;j<i;j++)

9c[i][j]=c[i-l][j]+c[i-l][j-l];

10}

11}

4.图论

4.1.邻接表

1typedefintmytype;

2constintNV=105;

3constintNE=10005*2;

4inthe[NV]>ecnt;

5structedge

6{

7intv,next;

8mytype1;

9}E[NE];

10voidadde(intu?intv,mytype1)

11{

12E[++ecnt].v=v;

13E[ecnt].1=1;

14E[ecnt].next=he[u];

15he[u]=ecnt;

16)

17初始化：

18ecnt=0;

19memset(he,-l,sizeof(he));

20调用：

21for(inti=he[u];i!=-l;i=E[i].next)

4.2.spfa

1typedefintmytype;

2constintNV=105;

3constintNE=10005*2;

4mytypedis[NV];

5intpreCNV],vis[NV],vent[NV],he[NV],ecnt;

6structedge

7{

8intv,next;

9mytype1;

10}E[NE];

11voidadde(intu.,intv,mytype1)

12(

13E[++ecnt].v=v;

14E[ecnt].1=1;

15E[ecnt].next=he[u];

16he[u]=ecnt;

17}

18voidinit(intn,intm,ints)

19{

20ecnt=0;

21memset(pre,0,sizeof(pre));

22memset(vis,O,sizeof(vis));

23memset(vent,0,sizeof(vent));

24memset(he,-1^sizeof(he));

25for(inti=0;i<=n;i++)

26dis[i]=inf;

27dis[s]=0;

28for(inti=l;i<=m;i++)

29{

30intu,v;

31mytype1;

32scanf("%d%d%d",&u,&v,&1);

33adde(u,v,1);

34adde(v,u,l);

35}

36}

37voidspfa(intn,intm,ints)

38{

39queue<int>q;

40vis[s]=l;

41q.push(s);

42while(!q.empty。)

43(

44intu=q.front();

45q.popO;

46vis[u]=0;

47for(inti=he[u];i!=-l;i=E[i].next)

48if(dis[u]+E[i].l<dis[E[i].v])

49{

50dis[E[i].v]=dis[u]+E[i].l;

51pre[E[i].v]=u;

52if(!vis[E[i].v])

53{

54vis[E[i].v]=l;

55q.push(E[i].v);

56vcnt[E[i].v]++;

57)

58)

59}

60}

4.3.dijkstra+heap

1typedefintmytype;

2constintNV=105;

3constintNE=10005*2;

4mytypedis[NV];

5intpre[NV],vis[NV],he[NV],ecnt;

6structedge

7{

8intv,next;

9mytype1;

10}E[NE];

11voidadde(intu,intv,mytype1)

12{

13E[++ecnt].v=v;

14E[ecnt].1=1;

15E[ecnt].next=he[u];

16he[u]=ecnt;

17}

18voidinit(intn,intm,ints)

19{

20ecnt=0;

21memset(pre,0,sizeof(pre));

22memset(vis,0?sizeof(vis));

23memset(he,-1,sizeof(he));

24for(inti=0;i<=n;i++)

25dis[i]=inf;

26dis[s]=0;

27for(inti=l;i<=m;i++)

28{

29intUjv;

30mytype1;

31scanf("%d%d%d"，&u,&v,&1);

32adde(u,v,l)J

33adde(v,u,l);

34}

35)

36structpoint

37{

38intu;

39mytype1;

40point(inta,mytypeb):u(a)>l(b){)

41booloperator<(constpointp)const

42{

43returnl>p.l;

44}

45};

46voiddijkstra_heap(intn,intm,ints)

47{-

48priority_queue<point>q;

49q.push(point(s,0));

50while(!q.empty())

51(

52pointp=q.top();

53q.pop();

54intu=p.u;

55if(vis[u])

56continue;

57vis[u]=l;

58for(inti=he[u];i!=-l;i=E[i].next)

59if(!vis[E[i].v]&&p.l+E[i].l<dis[E[i].v])

60{

61dis[E[i].v]=dis[u]+E[i].l;

62pre[E[i].v]=u;

63q.push(point(E[i].v,disfECi].v]));

64}

65}

66}

4.4.kruskaI

1typedefmtmytype;

2constintNV=105;

3constintNE=10005;

4structedge

5{

6intu,v;

7mytype1;

8booloperator<(constedgee)const

9

10returnl<e.l;

11}

12}E[NE];

13intf[NV]jrkfNV];

14intfinds(intx)

15{

16intk,j,r;

17r=x;

18while(r!=f[r])

19r=f[门；

20k=x;

21while(k!=r)

22{

23

24f[k]=r;

25k=j；

26)

27returnr;

28)

29voiduniCinta,intb)

30{

31a=finds(a);

32b=finds(b);

33if(a==b)

34return;

35if(rk[a]>rk[b])

36f[b]=a;

37else

38{

39if(rk[a]==rk[b])

40rk[b]++;

41f[a]=b;

42}

43}

44voidinitCintn,intm)

45{

46memset(rk,0,sizeof(rk));

47for(inti=l;i<=n;i++)

48

49for(inti=l;i<=m;i++)

,

50scanf("%d%d%d\&E[i].uJ&E[i].v,&E[i].l);

51}

52mytypekruskal(intn,intm)

53{

54sort(e+l,e+m+l);

55mytypeans=0;

56for(inti=l;i<=m;i++)

57if(finds(E[i].u)!=finds(E[i].v))

58(

59uni(E[i].u,E[i].v);

60ans+=E[i].1;

61}

62returnans;

63)

64booljudge(intn)

65{

66intflag=0;

67for(inti=l;i<=n;i++)

68if(finds(i)==i)

69flag++;

70returnflag==l;

71}一

4.5.prim+heap

typedefintmytype;

constintNV=105;

constintNE=10005*25

mytypedis[NV];

intpre[NV],vis[NV],he[NV],ecntjpent;

structedge

{

intv,next;

mytype1;

}E[NE]J

voidadde(intUjintv.,mytype1)

{

E[++ecnt].v=v;

E[ecnt].1=1;

E[ecnt].next=he[u];

he[u]=ecnt;

}

voidinitCintn,intm？ints)

{

ecnt=0;

memset(pre,0,sizeof(pre));

memsetCvis,O,sizeof(vis));

memset(he,-1,sizeof(he));

for(inti=0;i<=n;i++)

dis[i]=inf;

dis[s]=0;

for(inti=l;i<=m;i++)

{

intu,v;

mytype1;

scanf(”%d%d%d”，&u,&v,&1);

adde(uJv>l);

adde(v,u,l);

}

}

struetpoint

{

intu;

mytype1;

point(inta,mytypeb):u(a),l(b){}

booloperator<(constpointp)const

{

returnl>p.l;

}

};

mytypeprim_heap(intn,intm,ints)

{

priority_queue<point>q;

q.push(point(s,0));

mytypeans=0;

pcnt=0;

while(!q.empty())

(

pointp=q.top();

q.pop();

intu=p.u;

if(vis[u])

continue;

vis[u]=l;

ans+=p.l;//==dis[x]

61pcnt++;

62for(inti=he[u];i!=-l;i=E[i].next)

63if(!vis[E[i].v]&&E[i].l<dis[E[i].v])

64{

dis[E[i].v]=E[i].1;

66pre[E[i].v]=u;

q.push(point(E[i].v,dis[E[i].v]));

68)

69)

70returnans;

71)

72booljudge(intn)

73{'

74returnpcnt==n;

75)

4.6.最小树形图朱刘算法

1typedefintmytype;

2constintNV=1005;

3constintNE=NV*NV;

4structedge

5{

6intu,v;

7mytype1;

8}E[NE];

9intpre[NV]ID[NV],vis[NV];

10mytypeIn[NV];

11voidinit(intm)

12{

13for(inti=l;i<=m;i++)

14scanf("%d%d%d\&E[i].u>&E[i].v,&E[i].l);

15)

16mytypeDirected__MST(introot,intNV,intNE)

17{

18//memset(pre0,sizeof(pre));

19mytyperet=0;

20while(l)

21{

22〃:L.找最小入边

23for(inti=l;i<=NV;i++)

24In[i]=inf;

25for(inti=l;i<=NE;i++)

26{

27intu=E[i].u;

28intv=E[i].v;

29if(E[i].1<In[v]&&u!=v)

30{

31pre[v]=u;

32In[v]=E[i].1;

33)

34)

35for(inti=l;i<=NV;i++)

36{

37if(i==root)

38continue;

39if(fabs(In[i]-inf)<eps)

40return-1;)/除了跟以外有点没有入边，则根无法到达它

41)

42〃2,找环

43intentnode=0;

44memset(ID,-1,sizeof(ID));

45memset(vis,-1,sizeof(vis));

In[root]=0;

47for(inti=l;i<=NV;i++)〃标记每个环

48{

ret+=In[i];

50intv=i;

51while(vis[v]i&&ID[v]==-1&&v!=root)

52{

53vis[v]=i;

54v=pre[v];

55)

56if(v!=root&&ID[v]==-1)

{

58ID[v]=++cntnode;

59for(intu=pre[v];u!=v;u=pre[u])

60ID[u]=entnode;

61}

62)

63if(entnode==0)

64break;〃无环

65for(inti=l;i<=NV;i++)

66if(ID[i]==-1)

67ID[i]=++cntnode;

68〃3,缩点，重新标记

69for(inti=l;i<=NE;i++)

70{

71intv=E[i].v;

72E[i].u=ID[E[i].u];

73E[i].v=ID[E[i].v];

74if(E[i].u!=E[i].v)

75{

76E[i].l-=ln[v];

77}

78}

79NV=entnode;

80root=ID[root];

81}

82returnret;

83)

84booljudge(mytypeans)

85{

86returnfabs(ans+l)>eps;

87}

4.7.树的直径

1typedefintmytype;

2constintNV=40005;

3constintNE=2*NV;

4intvis[NV]^he[NV]^eent;

5structedge

6{

7intv,next;

mytype1;

9}E[NE];

10voidadde(intuJintvJmytype1)

11{

12E[++ecnt].v=v;

E[ecnt].1=1;

E[ecnt].next=he[u];

he[u]=ecnt;

16)

17voidinit(intn,intm)

18{

19ecnt=0;

20memset(he,-1,sizeof(he));

21for(inti=l;i<=m;i++)

22{

23intu,v;

24mytype1;

25scanf("%d%d%d",&u,&v,&1);

26adde(u,v,l);

27adde(v,u,l，；

28}

29)

30intU;

31mytypeL;

32voiddfsCintu>intuu,mytype1)

33{

34if(l>L)

35{

36U=u；

37L=l；

38}

39for(inti=he[u];i!=-l;i=E[i].next)

40if(E[i].v!=uu)

41dfs(E[i].v,u,l+E[i].1);

42}

43mytypesolve()

44{

45dfs(l,0,0);

46dfs(U,0,0);

47returnL;

48)

4.8.LCA的tarjan离线算法

1typedefintmytype;

2constintNV=40005;

3constintNE=NV;

4constintNQ=10005;

5mytypedis[NV],ans[NV];

6intvis[NV],he[NV],hqfNV]?ecnt,qcnt;

7structedge

8{

9intv,next;

10mytype1;

11}E[2*NE];

12structquer

13{

14intv,next,i;

15}q[2*NQ];

16voidadde(intu,intv,mytype1)

17{

18E[++ecnt].v=v;

19E[ecnt].1=1;

E[ecnt].next=he[u];

21he[u]=ecnt;

22)

23voidaddq(intu,intv,inti)

24{

25q[++qcnt].v=v;

26q[qcnt].i=i;

q[qcnt].next=hq[u];

28hq[u]=qcnt;

29}

30intfa[NV],rk[NV];

31voidinit(intn,intm)

32{

33ecnt=0;

34qcnt=0;

35memset(vis^O,sizeof(vis));

36memset(rk,0,sizeof(rk));

37memset(he,-l^sizeofChe));

38memset(hq,-1.,sizeof(hq));

39for(inti=l;i<=m;i++)

40{

41intu,v;

42mytype1;

43scanf(n%d%d%d",&u,&v,&1);

44adde(u,v,1);

45adde(v,u,l);

46}

47}

48intfinds(intx)

49(

50intkj,r;

51r=x;

52while(r!=fa[r])

53r=fa[r];

54k=x;

55while(k!=r)

56{

57j=fa[k]；

58fa[k]=r;

59k刁；

60)

61returnr;

62}

63voidtarjan(intumytyped)

64{

65dis[u]=d;

66fa[u]=u;

67vis[u]=l;

68for(inti=he[u];i!=-l;i=E[i].next)

69if(!vis[E[i].v])

70tarjan(E[i].v,d+E[i].v]=u;

71for(inti=hq[u];i!=-l;i=q[i].next)

72if(vis[q[i].vj)

73ans[q[i].i]=dis[u]+dis[q[i].v]-2*dis[finds(q[i].v)];

74}

75voidsolveCintn>intm)

76(

77init(n,m);

78

79scanf("%d",&k);

80for(inti=l;i<=k;i++)

81{

82intu,v;

83scanf("%d%dH,&u,&v);

84addq(u,v,i);

85addq(v,u,i);

86}

87tarjan(l,0);

88for(inti=l;i<=k;i++)

89printf("%d\n",ans[i]);

90}

4.9.二分图最大匹配匈牙利算法

1constintNV=505:

2constintNE=10005;

3inthe[NV],ecnt^preCNV],vis[NV];

4structedge

5{

6intv^next;

7}E[NE];

8voidadde(intUjintv)

9{

10E[++ecnt].v=v;

11E[ecnt].next=he[u];

12he[u]=ecnt;

13)

14intdfs(intu)

15{

16for(inti=he[u];i!=-l;i=E[i].next)

17(

18intv=E[i].v;

19if(!vis[v])

20{

21vis[v]=l;

22if(pre[v]==0||dfs(pre[v]))

23{

24pre[v]=u;

25returnl;

26}

27}

28)

29return©;

30}

31voidinit(intm)

32(

33ecnt=0;

34memset(he,-l,sizeof(he));

35memset(pre,0,sizeof(pre));

36while(m--)

37{

38intu,v;

39scanf("%d%d",&uJ&v);

40adde(u,v);

41}

42}

43inthungary(intn)

44{

45intans=0;

46for(inti=l;i<=n;i++)

47{

48memset(vis,0,sizeof(vis));

49ans+=dfs(i);

50}

51returnans;

52}

5.数据结构

5.1.离散化

1voiddiscrete(intdata[],intn,intdis[])

2{

3intsub[n+l];

4memcpy^sub^data？sizeof(sub));

5sort(sub+l,sub+n+1);

6intm=unique(sub+l,sub+n+l)-sub-l;

7for(inti=l;i<=n;i++)

dis[i]=lower_bound(sub+lJsub+m+lJdata[i])-sub;

9}—一

5.2.一维树状数组

1intn;

2inlineintlowbit(intt)

3(

4returnt&(-t);

5)

6voidupdate(intc[],intx,intv)

7{

8while(x<=n)

9{

10c[x]+=v;

11x+=lowbit(x);

12}

13}

14intquery(intc[],intx)

15{

16intans=0;

17while(x>0)

18{

19ans+=c[x];

20x-=lowbit(x);

21}

22returnans;

23}

5.3.RMQ

1constintNV=50005;

2constintNVB=20;

3intmx[NVB][NV]Jmn[NVB][NV],a[NV];

4voidrmqinit(intdata[],intn)

5{

6intk=log2(n);

7for(inti=l;i<=n;i++)

mx[0][i]=mn[0][i]=data[i];

9for(inti=l;i<=k;i++)

10for(intj=l;j+(l<<i)-l<=n;j++)

11{

mx[i][j]=max(mx[i-l][j]>mx[i-l][j+(l<<i>>l)]);

mn[i][j]=min(mn[i-l][j],mn[i-l][j+(l<<i>>l)]);

14)

15)

16intrmq(intlJintr,intflag)

17{

18intk=log2(r-l+l);

19if(flag)

20returnmax(mx[k][1],mx[k][r-(l<<k)+l]);

21else

22returnmin(mn[k][ll^mnfk][r-(l<<k)+l]);

23}

5.4.线段树

1#defineIson

2#definersonm+1,r<»rt<<l11

3constintNV=100005;

4intadd[NV*3],sum[NV*3];

5voidPushUp(intrt)

6{

sum[rt]=sum[rt<<l]+sum[rt<<l[1];

8)

9voidPushDown(intrt,intm)

10{

11if(add[rt])

12{

13add[rt<<l]+=add[rt];

add[rt<<l|1]+=add[rt];

sum[rt<<l]+=add[rt]*(m-(m>>l));

sum[rt<<l[1]+=add[rt]*(m>>l);

17add[rt]=0;

18}

19)

20voidbuild(intl,intr,intrt=l)

21{

22add[rt]=0;

23if(l==r)

24{

25sum[rt]=0;

26return;

27)

28intm=(1+r)>>1;

29build(lson);

30build(rson);

31PushUp(rt);

32}

33voidupdate(intL,intR,intc,inti,intr,intrt=l)

34{

35if(L<=l&&r<=R)

36{

37add[rt]+=c;

sumfrt]+=c*(r-1+1);

39return;

40)

41PushDown(rt,r-1+1);

42intm=(1+r)>>1;

43if(L<=m)update(L,R,c,lson);

44if(m<R)update(L,R,c,rson);

45PushUp(rt);

46}

47intquery(intL,intR,inti,intr,intrt=l)

48{

49if(L<=l&&r<=R)

50{

51returnsum[rt];

52}

53PushDown(rtr-1+1);

54intm=(1+r)>>1]

55intret=0;

56if(L<=m)ret+=query(L,R,Ison);

57if(m<R)ret+=query(L,R,rson);

58returnret;

59}

5.5.对一棵树进行线段树操作

1constintNV=10005;

2constintNE=NV;

3inthe[NV]^ecnt;

4structedge

5{

6intv,next;

7}E[NE]；

8voidadde(intu,intv)

9{

10ecnt++;

11E[ecnt].v=v;

12E[ecnt].next=he[u];

13he[u]=ecnt;

14}

15intl[NV],r[NV],p;

16voiddfs(intu)

17{

18p++;

19l[u]