HDU 3564 Another LIS 线段树+最长上升子序列

排队问题是线段树中很常见的题型。题目大意就是不断的向一个序列插入数据，插入的位置为当前序列的第某个位置，每次插入后都要求当前序列的最长上升子序列的长度。

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 100005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
    int left, right, mid, cnt;
}tree[4 * MAXN];
int a[MAXN], pos[MAXN];
int nk[MAXN];
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mid = ((s + e) >> 1);
    tree[C].cnt = tree[C].right - tree[C].left + 1;
    if(s == e) return;
    make_tree(s, tree[C].mid, L(C));
    make_tree(tree[C].mid + 1, e, R(C));
}
void  insert(int p, int v, int C)
{
    tree[C].cnt--;
    if(tree[C].right == tree[C].left)
    {
        pos[v] = tree[C].right;
        return;
    }
    if(tree[L(C)].cnt >= p)
    insert(p, v, L(C));
    else insert(p - tree[L(C)].cnt, v, R(C));
}
int main()
{
    int n, i;
    int T;
    scanf("%d", &T);
    int cas = 0;
    while(T--)
    {
        scanf("%d", &n);
        printf("Case #%d:\n", ++cas);
        make_tree(1, n, 1);
        for(i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
        }
        for(i = n - 1; i >= 0; i--)
        {
            insert(a[i] + 1, i + 1, 1);
        }
        int cnt = 0;
        for(i = 1; i <= n; i++)
        {
            if(cnt == 0 || pos[i] > nk[cnt]) //如果是第一个或者比队头的大，则存入数组
            nk[++cnt] = pos[i];
            else
            {
                int high = cnt;
                int low = 1;
                while(low <= high) //在已存序列中寻找位置，将输入的数替换进去，这样可以保证一直是上升序列
                {
                    int mid = (low + high) / 2;
                    if(nk[mid] < pos[i])
                    low = mid + 1;
                    else high = mid - 1;
                }
                nk[low] = pos[i];
            }
            printf("%d\n", cnt);
        }
        printf("\n");
    }
    return 0;
}