首页 > 代码库 > hdu5141——LIS again

hdu5141——LIS again

2024-08-06 15:45:37   219人阅读

LIS again

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 132    Accepted Submission(s): 34


Problem Description
A numeric sequence of ai is ordered if a1<a2<…<aN. Let the subsequence of the given numeric sequence (a1,a2,…,aN) be any sequence (ai1,ai2,…,aiK), where 1≤i1<i2<…<iK≤N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others.
S[ i , j ] indicates ( ai,ai+1,ai+2,…,aj) .
Your program, when given the numeric sequence (a1,a2,…,aN), must find the number of pair ( i, j) which makes the length of the longest ordered subsequence of S[ i , j ] equals to the length of the longest ordered subsequence of (a1,a2,…,aN).
 

Input
Multi test cases (about 100), every case occupies two lines, the first line contain n, then second line contain n numbersa1,a2,…,aN separated by exact one space.
Process to the end of file.

[Technical Specification]
1≤n≤100000
0≤ai≤1000000000
 

Output
For each case，.output the answer in a single line.
 

Sample Input
3
1 2 3
2
2 1
 

Sample Output
1
3
 

Source
BestCoder Round #21
 

Recommend
heyang   |   We have carefully selected several similar problems for you:  5140 5139 5138 5137 5136 
 


线段树+dp，dp[i]表示以第i个元素结尾的LIS的长度，线段树维护此LIS的最靠右的起始位置和长度，靠右是是为了完全统计出这样的区间，最后只要O(n)的时间去统计


#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
const int inf = -0x3f3f3f3f;
int xis[N];
int arr[N];
int dp[N];
int sta[N];
int end[N];
int ans, s;
int cnt;

struct node
{
	int l, r;
	int val, s;
}tree[N << 2];

void build(int p, int l, int r)
{
	tree[p].l = l;
	tree[p].r = r;
	tree[p].val = inf;
	tree[p].s = inf;
	if (l == r)
	{
		return;
	}
	int mid = (l + r) >>1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
}

int BinSearch(int val)
{
	int l = 1, r = cnt, mid;
	int ans;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (xis[mid] > val)
		{
			r = mid - 1;
		}
		else if (xis[mid] < val)
		{
			l = mid + 1;
		}
		else
		{
			ans = mid;
			break;
		}
	}
	return ans;
}

void update(int p, int pos, int val, int s)
{
	if (tree[p].l == tree[p].r)
	{
		if (tree[p].val == val && tree[p].s < s)
		{
			tree[p].s = s;
		}
		else if (tree[p].val < val)
		{
			tree[p].val = val;
			tree[p].s = s;
		}
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (pos <= mid)
	{
		update(p << 1, pos, val, s);
	}
	else
	{
		update(p << 1 | 1, pos, val, s);
	}
	if (tree[p << 1].val > tree[p << 1 | 1].val)
	{
		tree[p].val = tree[p << 1].val;
		tree[p].s = tree[p << 1].s;
	}
	else if (tree[p << 1].val < tree[p << 1 | 1].val)
	{
		tree[p].val = tree[p << 1 | 1].val;
		tree[p].s = tree[p << 1 | 1].s;
	}
	else
	{
		tree[p].s = max(tree[p << 1].s, tree[p << 1 | 1].s);
	}
}

void query(int p, int l, int r)
{
	if (tree[p].l >= l && tree[p].r <= r)
	{
		if (tree[p].val > ans)
		{
			ans = tree[p].val;
			s = tree[p].s;
		}
		else if (tree[p].val == ans && s < tree[p].s)
		{
			s = tree[p].s;
		}
		return;
	}
	int mid = (tree[p].l + tree[p].r) >> 1;
	if (r <= mid)
	{
		query(p << 1, l, r);
	}
	else if (l > mid)
	{
		query(p << 1 | 1, l, r);
	}
	else
	{
		query(p << 1, l, mid);
		query(p << 1 | 1, mid + 1, r);
	}
}

int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		__int64 ret = 0;
		cnt = 0;
		int tmp = 0;
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &arr[i]);
			xis[++cnt] = arr[i];
		}   
		if (n == 1)
		{
			printf("1\n");
			continue;
		}
		sort (xis + 1, xis + cnt + 1);
		cnt = unique(xis + 1, xis + cnt + 1) - xis - 1;
		dp[1] = 1;
		sta[1] = 1;
		build(1, 1, cnt);
		update(1, BinSearch(arr[1]), dp[1], sta[1]);
		for (int i = 2; i <= n; ++i)
		{
			ans = inf;
			s = inf;
			if (BinSearch(arr[i]) == 1)
			{
				dp[i] = 1;
				sta[i] = i;
			}
			else
			{
				query(1, 1, BinSearch(arr[i]) - 1);
			}
			if (ans == inf)
			{
				dp[i] = 1;
				sta[i] = i;
			}
			else
			{
				dp[i] = ans + 1;
				sta[i] = s;
			}
			update(1, BinSearch(arr[i]), dp[i], sta[i]);
			tmp = max(tmp, dp[i]);
		}
		int last = n + 1;
		for (int i = n; i >= 1; --i)
		{
			if (dp[i] == tmp)
			{
				end[i] = last - 1;
				last = i;
			}
		}
		for (int i = 1; i <= n; ++i)
		{
			if (dp[i] == tmp)
			{
				ret += (__int64)sta[i] * (__int64)(end[i] - i + 1);
			}
		}
		printf("%I64d\n", ret);
	}
	return 0;
}


hdu5141——LIS again


联系
我们