排队问题是线段树中很常见的题型。题目大意就是不断的向一个序列插入数据,插入的位置为当前序列的第某个位置,每次插入后都要求当前序列的最长上升子序列的长度。
/*
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;
}
分享到:
相关推荐
hdu 1166线段树代码
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 1695 GCD(欧拉函数+容斥原理).docx
hdu 1166线段树
acm hdu as easy as a+b
1257 最低拦截系统 lis做的哦 详情可访问球球网 www.loveqiuqiu.com
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
ACM题库,一些题目和答案,以及解题报告,传上来共享
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
杭电OnlineJudge 200-2099的解题报告
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
NULL 博文链接:https://128kj.iteye.com/blog/1738772
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码