序列变换,线段树单点更新

作者: 计算机网络  发布:2019-11-15

hdu 5256 序列变换 (LIS变形)

 

HDOJ 题目3564 Another LIS(线段树单点更新,LIS)

序列变换

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

Problem Description 我们有一个数列A1,A2...An,你现在要求修改数量最少的元素,使得这个数列严格递增。其中无论是修改前还是修改后,每个元素都必须是整数。
请输出最少需要修改多少个元素。
Input 第一行输入一个T(1≤T≤10),表示有多少组数据

每一组数据:

第一行输入一个N(1≤N≤105),表示数列的长度

第二行输入N个数A1,A2,...,An。

每一个数列中的元素都是正整数而且不超过106。
Output 对于每组数据,先输出一行

Case #i:

然后输出最少需要修改多少个元素。
Sample Input

2
2
1 10
3
2 5 4

Sample Output

Case #1:
0
Case #2:
1

非严格递增时,只需要求最长不降子序列就行了;严格上升,就需要求a[i]-i序列的最长LIS; a[j]-a[i]>j-i,即是两个元素不改变需要满足两数之差大于下标之差。

#include 
#include
#include
#include
#include
using namespace std;
#define N 100005
#define LL __int64
int a[N];
int b[N];
int fun(int n)
{
    int i,t,cnt=0;
    for(i=0;i  

5256 序列变换 (LIS变形) 序列变换 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 519 Accepted Submission(s): 245...

Another LIS

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1291 Accepted Submission(s): 451

Problem Description There is a sequence firstly empty. We begin to add number from 1 to N to the sequence, and every time we just add a single number to the sequence at a specific position. Now, we want to know length of the LIS (Longest Increasing Subsequence) after every time's add.
Input An integer T (T <= 10), indicating there are T test cases.
For every test case, an integer N (1 <= N <= 100000) comes first, then there are N numbers, the k-th number Xk means that we add number k at position Xk (0 <= Xk <= k-1).See hint for more details.

Output For the k-th test case, first output Case #k: in a separate line, then followed N lines indicating the answer. Output a blank line after every test case.
Sample Input

1
3
0 0 2

Sample Output

Case #1:
1
1
2

Hint
In the sample, we add three numbers to the sequence, and form three sequences.
a. 1
b. 2 1
c. 2 1 3

Author standy
Source 2010 ACM-ICPC Multi-University Training Contest(13)——Host by UESTC
Recommend zhouzeyong | We have carefully selected several similar problems for you: 3572 2389 3584 3293 1255 思路:就是从左插入找空位,从1~n用线段树记录他们的位置,然后再对他们的位置进行LIS就好 ac代码

#include
#include
#define max(a,b) (a>b?a:b)
int a[100010];
int node[100010<<2],d[100010],len,dp[100010];
void build(int l,int r,int tr)
{
 node[tr]=r-l+1;
 if(l==r)
  return;
 int mid=(l+r)>>1;
 build(l,mid,tr<<1);
 build(mid+1,r,tr<<1|1);
 node[tr]=node[tr<<1]+node[tr<<1|1];
}
int bin(int x)
{
 int l=1,r=len;
 while(l<=r)
 {
  int mid=(l+r)>>1;
  if(x>dp[mid])
   l=mid+1;
  else
   r=mid-1;
 }
 return l;
}
void insert(int pos,int num,int l,int r,int tr)
{
 if(l==r)
 {
  d[num]=l;
  node[tr]=0;
  return;
 }
 int mid=(l+r)>>1;
 node[tr]--;
 if(pos<=node[tr<<1])
 {
  insert(pos,num,l,mid,tr<<1);
 }
 else
  insert(pos-node[tr<<1],num,mid+1,r,tr<<1|1);
}
int main()
{
 int t,c=0;
 scanf(%d,&t);
 while(t--)
 {
  int n;
  scanf(%d,&n);
  int i;
  for(i=1;i<=n;i++)
  {
   scanf(%d,&a[i]);
   dp[i]=0;
  }
  build(1,n,1);
  for(i=n;i>0;i--)
  {
   insert(a[i]+1,i,1,n,1);
  }
  len=0;
  /*for(i=1;i<=n;i++)
  {
   printf(%d
,d[i]);
  }*/
  printf(Case #%d:
,++c);
  for(i=1;i<=n;i++)
  {
   int k=bin(d[i]);
   len=max(len,k);
   dp[k]=d[i];
   printf(%d
,len);
  }
  printf(
);
 }
}

 

题目3564 Another LIS(线段树单点更新,LIS) Another LIS Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1291...

本文由今晚开什么码发布于计算机网络,转载请注明出处:序列变换,线段树单点更新

关键词: