[传送门]（https://www.luogu.com.cn/problem/P7078）
这题的质量是真的高，而且部分分给的莫名其妙的多。
但是洛谷评分是黑题我就很蒙，虽然挺费脑，但紫题足以。
这题刚开始我还以为是什么博弈论，后来发现是自己吓自己。
首先有两个小结论要推一下：
1.当前最强的蛇如果吃了最弱的没有成为最弱的，那么他一定不会被吃。
证明很简单：因为({ a_i})从小到大有序，所以(a_n - a_1 geqslant a_{n - 1} - a_2)，即第(n-1)条蛇吃完后必定会更弱，所以在第(n)条蛇被吃前一定会先吃第(n-1)条蛇。
我们把“最强的蛇吃完后没有变成最弱的”称为阶段1，那么如果一条蛇吃完后成为最弱的，就进入了阶段2.
阶段2：
现在就要考虑第(n)条蛇是吃还是不吃的问题。
比如(a_{n-1})吃完后同样也成为了最弱的，那么(a_{n-1})必定不会吃(a_{n})，因此(a_{n})就可以吃。
以此类推我们得到了一条链(a_n,a_{n-1}, ldots a_{n-k})，表示这些蛇依次吃完后都会变成最弱的。那么我们从(a_{n-k})考虑：
(a_{n-k})能吃(a_{n-k+1})，那么(a_{n-k+1})就不会吃(a_{n-k+2})；
(a_{n-k+2})不会被吃，那么他就会吃(a_{n-k+3})；
(a_{n-k+2})能吃(a_{n-k+3})，那么(a_{n-k+3})就不会吃(a_{n-k+4});
(a_{n-k+4})不会被吃，那么他就会吃(a_{n-k+5});
……
我们就得到了一条"能吃——不能吃——能吃——不能吃……"循环的链。
说白了，这就是结论2：如果链长为奇数，那么(a_n)就能吃(a_1)；如果链长为偶数，那么(a_n)就不能吃。
这个就是这道题的主要思想了，接下来能不能拿满分就是维护的问题了。
首先大家都能想到的是用一个set维护，复杂度(O(Tnlogn))，1e6正好是2e8.
先放一个70代码的主要部分（洛谷给了我90哈哈）：
int n, a[maxn];
#define pr pair<int, int>
#define mp make_pair
#define F first
#define S second
#define spr set<pr>::iterator
set<pr> s;
In int work()
{
s.clear();
for(int i = 1; i <= n; ++i) s.insert(mp(a[i], i));
int ret = 0, flg = 0, cnt = 1;
while(s.size() > 1)
{
spr it = s.end(); it--;
int Max = (*it).F, Min = (*s.begin()).F, p = (*it).S;
s.erase(it), s.erase(s.begin());
pr tp = mp(Max - Min, p); s.insert(tp);
if(tp == *s.begin())
{
if(!flg) flg = 1, ret = s.size() + 1;
else ++cnt;
}
else if(flg) return ret - (cnt & 1);
}
return flg ? ret - (cnt & 1) : 1;
}
我自认为我的代码写的还是很巧妙的：通过flg变量控制了阶段1还是阶段2，从而不用写两个函数，大大的减少了代码量。
至于满分做法，很多人说是16年的蚯蚓排队，鉴于我当时啥也不会，我对这个说法并没有什么感觉。
我们用两个双端队列维护。
这道题的关键在于当(a_n)吃完(a_1)后还是阶段1的话，队列的单调性就会被破坏，从而使插入达不到(O(1))。
因此我们再开一个队列，把这个新的(a_n - a_1)放进去。更具体的说，我们把所有吃过的蛇都放进这个队列的队尾，因为有式子(a_n - a_1 geqslant a_{n - 1} - a_2)，所以这个队列必定是单调的。
那么每次最强的蛇就是两个队首的更强者，最弱的蛇就是两个队尾的更弱者，这样就完美的代替了set的(O(logn))的取最大值、取最小值、插入、删除的操作。
于是我们把上面代码有关set的操作开成deque，事情就解决了，复杂度(O（Tn）)。
比较大小因为有编号的限制，我就单独写了两个函数，可能略显繁琐，还是给出主要代码吧。
int n, a[maxn];
#define pr pair<int, int>
#define mp make_pair
#define F first
#define S second
#define ff front()
#define bb back()
deque<pr> q[2]; //都是头最大，尾最小
In pr getMax()
{
bool flg = 1;
if(q[0].empty()) flg = 1;
else if(q[1].empty()) flg = 0;
else if(q[0].ff.F > q[1].ff.F || (q[0].ff.F == q[1].ff.F && q[0].ff.S > q[1].ff.S)) flg = 0;
pr ret = q[flg].ff; q[flg].pop_front();
return ret;
}
In pr getMin()
{
bool flg = 1;
if(q[0].empty()) flg = 1;
else if(q[1].empty()) flg = 0;
else if(q[0].bb.F < q[1].bb.F || (q[0].bb.F == q[1].bb.F && q[0].bb.S < q[1].bb.S)) flg = 0;
pr ret = q[flg].bb; q[flg].pop_back();
return ret;
}
In int work()
{
q[0].clear(), q[1].clear();
for(int i = 1; i <= n; ++i) q[0].push_front(mp(a[i], i));
int ret = 0, flg = 0, cnt = 1;
while(q[0].size() + q[1].size() > 1)
{
pr tp = getMax();
int Max = tp.F, Min = getMin().F, p = tp.S;
tp = mp(Max - Min, p); q[1].push_back(tp);
if(tp < q[0].bb)
{
if(!flg) flg = 1, ret = q[0].size() + q[1].size() + 1;
else ++cnt;
}
else if(flg) return ret - (cnt & 1);
}
return flg ? ret - (cnt & 1) : 1;
}