求指教,程序TLE了。
#include <iostream>
#define INT_MAX 2147483647
using namespace std;
int FillSegmentationTree(int left, int right);
int FindSegmentationTree(int lowerBound, int rightBound, int left, int right);
int FindNormal(int left, int right);
int* weight;
int* segmentationTreeMin;
int main(char* argv[], int argc)
{
int N;
cin >> N;
weight = new int[N + 1];
for (int i = 0; i < N; i++)
{
cin >> weight[i + 1];
}
segmentationTreeMin = new int[N + 1];
for (int i = 0; i <= N; i++)
{
segmentationTreeMin[i] = INT_MAX;
}
FillSegmentationTree(1, N);
int Q;
cin >> Q;
int L, R;
for (int i = 0; i < Q; i++)
{
cin >> L >> R;
cout << FindSegmentationTree(1, N, L, R) << endl;
}
}
int FindNormal(int left, int right)
{
int min = INT_MAX;
for (int i = left; i <= right; i++)
{
if (weight[i] < min)
{
min = weight[i];
}
}
return min;
}
int FillSegmentationTree(int left, int right)
{
if (left == right)
{
return weight[left];
}
else if (right - left == 1)
{
int mid = (left + right) / 2;
segmentationTreeMin[mid] = weight[left] < weight[right] ? weight[left] : weight[right];
return segmentationTreeMin[mid];
}
else
{
int mid = (left + right) / 2;
int leftMin = FillSegmentationTree(left, mid);
int rightMin = FillSegmentationTree(mid + 1, right);
segmentationTreeMin[mid] = leftMin < rightMin ? leftMin : rightMin;
return segmentationTreeMin[mid];
}
}
int FindSegmentationTree(int lowerBound, int rightBound, int left, int right)
{
if (rightBound == lowerBound)
{
return weight[lowerBound];
}
else
{
int mid = (lowerBound + rightBound) / 2;
if (left == lowerBound && right == rightBound)
{
return segmentationTreeMin[mid];
}
else if (right <= mid)
{
return FindSegmentationTree(lowerBound, mid, left, right);
}
else if (left > mid)
{
return FindSegmentationTree(mid + 1, rightBound, left, right);
}
else
{
int leftMin = FindSegmentationTree(lowerBound, mid, left, mid);
int rightMin = FindSegmentationTree(mid + 1, rightBound, mid + 1, right);
return leftMin < rightMin ? leftMin : rightMin;
}
}
}
segment tree虽然通用但容易由于写不好而使得常数耗费大。你先用提示1里面的sparse table的方法试试,代码短小精悍