1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

//Prim
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
void read(T& w)
{
	char r;
	for(r=getchar();r<48||r>57;r=getchar());
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=103;
const int maxm=maxn*(maxn-1)/2;
int n,m;
struct EDGE
{
	int to,nxt,w;
	void init(int too,int nxtt,int ww)
	{
		to=too,nxt=nxtt,w=ww;
	}
}edge[maxm<<1];
int ek=0;

int node[maxn];
void addEdge(int from,int too,int ww)
{
	edge[++ek].init(too,node[from],ww);
	node[from]=ek;
}
void input()
{
	read(n),read(m);
	int x,y,l;
	for(int i=1;i<=m;++i)
	{
		read(x),read(y),read(l);
		if(x!=y)
		{
			addEdge(x,y,l);
			addEdge(y,x,l);
		}
	}
}
bool operator<(const EDGE& a,const EDGE& b)
{
	return a.w<b.w;
}
template<typename T>
struct HEAP
{
	T ary[maxm<<1];
	int f;
	HEAP(){f=0;}
	void clear(){f=0;}
	bool empty(){return f==0;}
	void push(const T& w)
	{
		ary[++f]=w;
		for(int k=f;k!=1&&ary[k]<ary[k/2];k=k/2)
		{
			Swap(ary[k],ary[k/2]);
		}
	}
	T top(){return ary[1];}
	T pop()
	{
		T tmp=ary[1];
		ary[1]=ary[f--];
		for(int k=1,son=k*2;son<=f;k=son,son=k*2)
		{
			if(son+1<=f&&ary[son+1]<ary[son])
				son=son+1;
			if(ary[son]<ary[k])
				Swap(ary[son],ary[k]);
			else break;
		}
		return tmp;
	}
};
int s=1;
bool vis[maxn];
HEAP<EDGE> h;
int Prim()
{
	int sum=0;
	for(int k=2,ff=1;k<=n;++k)
	{
		vis[ff]=true;
		for(int i=node[ff];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(!vis[v])
				h.push(edge[i]);
		}
		EDGE tmp;
		for(tmp=h.pop();vis[tmp.to];tmp=h.pop());
		ff=tmp.to;
		sum+=tmp.w;
	}
	return sum;
}
int main()
{
	input();
	printf("%d\n",Prim());
	return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//希尔排序 
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}

template<typename T>
void shellSort(T* ary,int l,int r)//默认为<,r为超尾 
{
	int len=(r-l);
	for(int k=len/2;k>=1;--k)
		for(int i=l+k-1;i<=r;++i)
			for(int j=i;j-k>=l&&ary[j]<ary[j-k];j-=k)
				Swap(ary[j],ary[j-k]);
}

template<typename T>
void shellSort(T* ary,int l,int r,bool comp(const T& a,const T& b))//r为超尾 
{
	int len=(r-l);
	for(int k=len/2;k>=1;--k)
		for(int i=l+k-1;i<=r;++i)
			for(int j=i;j-k>=l&&comp(ary[j],ary[j-k]);j-=k)
				Swap(ary[j],ary[j-k]);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

/*
ST表
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=int(1e5+3);
const int maxm=int(1e6+3);
int n,m;
int f[maxn][20];
int a[maxn];
void input()
{
	read(n),read(m);
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
	}
}
void initF()
{
	for(int i=1;i<=n;++i)
	{
		f[i][0]=a[i];
	}
	for(int k=1;(1<<k)<=n;++k)
	{
		for(int i=1;i<=n;++i)
		{
			f[i][k]=f[i][k-1];
			if(i+(1<<(k-1))<=n&&f[i+(1<<(k-1))][k-1]>f[i][k])//caution! 下标可能越界
				f[i][k]=f[i+(1<<(k-1))][k-1];
		}
	}
}
int lg[maxn];
void initLG()
{
	lg[1]=0;
	lg[2]=1;
	for(int i=3;i<=n;++i)
	{
		lg[i]=lg[i/2]+1;
	}
}
int askmax(int l,int r)
{
	int len=r-l+1;
	int k=lg[len];
	return Max(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
	int l,r;
	for(int i=1;i<=m;++i)
	{
		read(l),read(r);
		printf("%d\n",askmax(l,r));
	}
}
int main()
{
	input();
	initLG();
	initF();
	solve();
	return 0;
} 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//二维RMQ-正方形
int fm[maxn][maxn][8];
int fn[maxn][maxn][8];
void initMaxMin()
{
	for(int k=0;(1<<k)<=s;++k)
	{
		for(int i=1;i+(1<<(k))-1<=n;++i) for(int j=1;j+(1<<(k))-1<=m;++j)
		{
			if(k==0)
			{
				fm[i][j][0]=fn[i][j][0]=a[i][j];
			}
			else
			{
				fm[i][j][k]=
				Max(
					Max(
						fm[i][j][k-1],
						fm[i+(1<<(k-1))][j][k-1]),
					Max(
						fm[i][j+(1<<(k-1))][k-1],
						fm[i+(1<<(k-1))][j+(1<<(k-1))][k-1])
				);
				fn[i][j][k]=
				Min(
					Min(
						fn[i][j][k-1],
						fn[i+(1<<(k-1))][j][k-1]),
					Min(
						fn[i][j+(1<<(k-1))][k-1],
						fn[i+(1<<(k-1))][j+(1<<(k-1))][k-1])
				);
			}
		}
	}
}
int qMax(int ax,int ay,int bx,int by)
{
	int k=log2(bx-ax+1);
	return Max(
		Max(
			fm[ax][ay][k],
			fm[bx-(1<<k)+1][ay][k]),
		Max(
			fm[ax][by-(1<<k)+1][k],
			fm[bx-(1<<k)+1][by-(1<<k)+1][k])
	);
}
int qMin(int ax,int ay,int bx,int by)
{
	int k=log2(bx-ax+1);
	return Min(
		Min(
			fn[ax][ay][k],
			fn[bx-(1<<k)+1][ay][k]),
		Min(
			fn[ax][by-(1<<k)+1][k],
			fn[bx-(1<<k)+1][by-(1<<k)+1][k])
	);
}