Atcoder 260_D 反思
先回顾一下怎么想的
其实一开始拿到这个题就去$ Onenote $画了个草图 因为直接照着英文题面思考的话会很困难……不过这也促成了很好的思考。
但是这个事情没有做完啊……能写出这种数据结构：
using vec=list<int>;
struct pile{
int topm,cnt;
vec* ve;
pile(int x,vec* p=0,int c=1): topm(x),ve(p),cnt(c) {
if(p) p->push_back(x);
}
bool operator<(const pile& rhs)const{return topm<rhs.topm;}
};
set<pile> s;
更别提这个（类似成员函数的）函数：
void add(const pile* _this,int x,int i,decltype(s.begin()) lb){
if(_this->cnt==k-1){
seq[x]=i;
for(auto j: *(_this->ve) )seq[j]=i;
delete _this->ve;
s.erase(lb);
}
else{
_this->ve ->push_back(x);
s.erase(lb);
s.insert(pile(x,_this->ve,_this->cnt+1));
}
}
呃呃直接堆叠STL（STL套STL）当然不好 于是STL套指向STL的指针？小天才
怎么做更好呢？
当然是手写STL啊…… 不开玩笑的。
不定长数组就学学Atcoder解答さん的vector构造函数（2个参数的重载版本），相当于赋好初值的一个不定长数组。
而且真的足够快……相信-O2的力量！
链表？不需要的。维护每个东西\(key\)的:
\(val\)数组、\(pre/nex\)数组
（\(val\)数组完全可以不止一个唷，本题就是牌面和自己是牌堆第几张牌）
这样的话就是利用了更基本的STL（vector当VLA用，实现所谓类型安全，且有很多方便的成员函数）来实现数据结构
这才对嘛……就好比set不当作自己是个红黑树，rank()和kth()都不提供，STL也不是“给你实现好了的数据结构”：它的内部组织形式对外不可见！你只能获得一些时空复杂度上的保证，并不知道也不需要知道其内部如何实现。
看看Atcoder解答さん怎么做的
需要声明的容器
vector<int> under(n+5,-1);
vector<int> pile(n+5,0);
set<int> st;
vector<int> res(n+5,-1);
这就足够实现单链表，不需要也不要用std::list<> 或者std::vector<> 当list用
新建牌堆
for(int i=1;i<=n;i++){
int p;
cin >> p;
auto it=st.upper_bound(p);
if(it==st.end()){
pile[p]=1;
st.insert(p); // 敢直接用p而不用val数组是因为p是 1 ~ N 的，不然我想还是 val[cnt++]=read();
}
以上部分基本一样捏，不同的是Atcoder解答さん使用的set的模板参数是int，这样既快（set应该内部会有复制吧……）又明了，不会出现->
// lb是set<pile>::forward_iterator，先 *运算得到pile对象，再 & 得到_this指针
// 于是这里的 &* 运算就不是白干的…… 而且要运算一小会
add(&(*lb),x,i,lb);
这种神奇语句。
插入已有牌堆
直接注释在里面好了
else{
under[p]=(*it); // 这就是前驱数组
pile[p]=pile[(*it)]+1; // 记录 p 是第几张牌
st.erase(it);
st.insert(p); // 抹了旧的换上新的
}
if(pile[p]==k){
st.erase(p);
int x=p; // 确实大佬们也不怎么压行的…… 感觉做题的时候心思有些过多用于优化代码……
// 不过已经形成习惯的话也好。譬如这里我会把 x 的初始化放在 for 第一句里。甚至更狠，见下
for(int j=0;j<k;j++){ // 链表的遍历捏
res[x]=i;
x=under[x];
}
// 链表遍历的简介做法捏（under[]初值为 0 的话 就用按位取反判断.end()：
// for(int x=p; ~x; x=under[x]) res[x]=i;
}
}
最后输出res[]就好啦，C++11甚至14普及的当下直接用for(auto&& i:res)方便高效。
さいごのさいご
学习decltype auto 初值列等等语法
不是为了装逼、或者更快CE、或者更容易导致个别神奇的点不通过的。
所以现在要在上面的常用压行（一般也会减小常数）等等迫真好习惯基础上再加这么几条：
- 尽量不要STL套STL，STL套“指向STL的指针”
也更不行！ - 需要多阅读Atcoder解答さん以及其他大佬的代码，学习他们的有创意且高效的做法
譬如vector(_Num, __initializer)来构造不定长数组同时赋初值。
其实以上可以概括为先想好了再做题。
但是这几个字太抽象，事实上着手这个题的时候我也稍稍想了想有没有更好的做法，but failed。
所以需要多多写博客。今天这是第一篇，就多唠唠嗑，后面直接高效率总结需要改进的点就好了。