P1020 [noip1999 popularization group] missile interception problem solution

Ideas : Sequence DP + Line segment tree optimization DP

First, the first question , In fact, it is to find the longest Non rising sequence

We design ${dp}_i$ For from 1 To $i$ And its longest Non rising sequence is $i$ For the end The sequence length of . Then we can update the answer from missiles that are higher or equal than the current missile . That is to say :

dp[i] = max{
    dp[v]} + 1 (a[v] >= a[i] && v <= i)

The time complexity here is $O(n^2)$

For the second question , We can think of , If we first use an interception facility to shoot down all missiles that can be hit , Repeat this action for the remaining interception facilities , Until all missiles are intercepted . Suppose we get the minimum partition （ Subject requirements ） Of $k$ Group missile . So for the $i$ Any of the group missiles , In the $i+1$ There must be a missile higher than this one , without , Then we can put $i+1$ Combine to $i$ Group .

So we find the longest ascending subsequence , Make sure that each missile in the sequence corresponds to a group of missiles , If there is more, it must be redundant , If less , Do not meet the above grouping . So when we are looking for the minimum partition , Just find one Longest ascending subsequence Length can .

We redesign ${dp}_i$ For from 1 To $i$ And its longest ascending subsequence is $i$ For the end The sequence length of . ditto , We can get :

dp[i] = max{
    dp[v]} + 1 (a[v] < a[i] && v <= i)

Time complexity is also $O(n^2)$

For optimization : ( Two questions are common )

We can find that one dimension is used to find ${dp}_{\mathrm{1..}n}$ The maximum value that satisfies the condition in . We can consider using segment tree to optimize . We use $a_i$ （ It's height ） It's coordinates , Maintain in the segment tree $f_i$ The maximum of . When we traverse regularly , Every time you update $f_i$ We will update it in the segment tree , When looking for the maximum , We follow the size , In the corresponding interval （ For example, find the longest ascending subsequence , We should start from a height less than $a_i$ Of $f_v$ Transfer in , So we asked $(1,a[i]-1)$ Interval information ） inquiry , And transfer .

The time complexity is $O(n\log n)$

AC code:

#include <cstdio>
#include <algorithm>
using namespace std;

#define root 1,1,maxn
#define ls p<<1,l,m
#define rs p<<1|1,m+1,r

const int maxn=(int)5e4+10;

int Min[maxn<<2], Max[maxn<<2];

inline void update(int p) {
    
    Min[p]= min(Min[p<<1], Min[p<<1|1]);
    Max[p]= max(Max[p<<1], Max[p<<1|1]);
    return;
}

inline void build(int p,int l, int r) {
    
    if(l==r){
     Min[p]=Max[p]=0;return; }
    int m= (l+r)>>1;
    build(ls); build(rs); update(p);
    return;
}

inline void modify(int p, int l, int r, int now, int v) {
    
    if(l==r){
     Min[p]=Max[p]=v;return; }
    int m= (l+r)>>1;
    if(now <= m) modify(ls, now, v);
    else modify(rs, now, v);
    update(p); return;
}

inline int query(int p, int l, int r, int li, int ri) {
    
    if(li<=l && r<=ri) return Max[p];
    int m= (l+r)>>1;
    if(li <= m) {
    
        if(m < ri) return max( query(ls, li, ri), query(rs, li, ri) );
        else return query(ls, li, ri);
    }
    else return query(rs, li, ri);
}

int f[maxn]={
    0}, a[maxn]={
    0};
int n=0, ans1=0, ans2=0, i=0;
int max_i=0;

int main(){
    
    while(scanf("%d",&a[++n])!=EOF); n--;
    for(i=1;i<=n;i++) f[i]=0;
    build(root);
    for(i=1;i<=n;i++) {
    
        max_i=0;
        max_i= query(root, a[i], maxn);
        f[i]= max_i+1;
        modify(root, a[i], f[i]);
        ans1= max(f[i], ans1);
    }
    printf("%d\n",ans1);
    for(i=1;i<=n;i++) f[i]=0;
    build(root);
    for(i=1;i<=n;i++) {
    
        max_i=0;
        max_i= query(root, 1, a[i]-1);
        f[i]= max_i+1;
        modify(root, a[i], f[i]);
        ans2= max(f[i], ans2);
    }
    printf("%d\n",ans2);
    return 0;
}