非正经题解

这题数据较弱,暴力优化后可AK.
(Tips:老师已经知道了可能要优化数据力）

#include<bits/stdc++.h>
using namespace std;

int n,m;
struct node
{
	int v,n;
} a[500005];
bool cmp(node x,node y)
{
	return x.v < y.v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i].v;
		a[i].n = i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i = 1;i <= m;i++)
	{
		int l,r;
		cin >> l >> r;
		for(int j = 1;j <= n;j++)
			if(a[j].n >= l && a[j].n <= r)
			{
				cout << a[j].v << " ";
				break;
			}
	}
	return 0;
}

未优化前代码:20pts

#include<bits/stdc++.h>
using namespace std;

int n,m;
int a[500005];
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	for(int i = 1;i <= m;i++)
	{
		int l,r;
		cin >> l >> r;
		sort(a+l,a+r);
		cout << a[l] << " ";
	}
	return 0;
}

纯暴力时,由于sort()平均复杂度为$O(nlogn)$,因此本方法时间复杂度为$O(mnlogn)$.对于$m = n = 5 * 10 ^ 5$,有$T ≈1.42*10^{12}$,会超时。
优化后时间复杂度将为$O(mn)$,并有剪枝(? 虽然剪枝一般说的是搜索,但是找不到好的形容词了)优化,且本题数据较弱,故能AK.