TLE求调
查看原帖
TLE求调
655457
zichen3004楼主2024/6/13 17:06
#include<bits/stdc++.h>
using namespace std;
int upg[200005], dng[200005];
int uid[200005], did[200005];
int a[200005], n, tmpmaxn, tmp;
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
int bin1(int x)
{
	int l = 1, r = tmpmaxn, mid, ans = 0;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(upg[mid] < x)
			l = mid + 1, ans = mid;
		else
			r = mid - 1;
	}
	return ans;
}
int bin2(int x)
{
	int l = 1, r = tmpmaxn, mid, ans = 0;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(dng[mid] > x)
			l = mid + 1, ans = mid;
		else
			r = mid - 1;
	}
	return ans;
}
void Solve()
{
	n = read();
	for(register int i = 1; i <= n; i++)
		a[i] = read();
	memset(upg, 0, sizeof upg);
	memset(dng, 0, sizeof dng);
	tmpmaxn = 0;
	for(register int i = 1; i <= n; i++)
		if(a[i] > upg[tmpmaxn])
			upg[++tmpmaxn] = a[i], uid[i] = tmpmaxn;
		else
			tmp = bin1(a[i]) + 1, upg[tmp] = a[i], uid[i] = tmp;
	int tmptmp = tmpmaxn; tmpmaxn = 0;
	dng[0] = 1e9 + 7; int ansn = 0;
	for(register int i = n; i >= 1; i--)
	{
		if(a[i] < dng[tmpmaxn])
			dng[++tmpmaxn] = a[i], did[i] = tmpmaxn;
		else
			tmp = bin2(a[i]) + 1, dng[tmp] = a[i], did[i] = tmp;
		if(uid[i] + did[i] - 1 == tmptmp)
			ansn++;
	}
	cout << ansn << endl;
	for(register int i = 1; i <= n; i++)
		if(uid[i] + did[i] - 1 == tmpmaxn)
			cout << i << " ";
	cout << endl;
	return;
}
int main()
{
	cin.tie(0), cout.tie(0);
	int T = read(); 
	while(T--)
		Solve();
	return 0;
}
2024/6/13 17:06
加载中...