题解 | #三角形#

一个明显的想法，就是对 $a_{i}a\_i$ 排序，然后从后往前扫，取连续 $33$ 位进行判断。

在这个基础上，特判一下哪根木棍被取走了即可。

看起来这个过程复杂度是 $O(n^2)O(n^2)$，但是实际上由于我们只要找到解就 break，复杂度是接近于斐波那契数列增长速度的，可以视作一个 $\log \backslash log$，即 $O(n\log n)O(n\backslash log\; n)$。

#include<cstdio>
#include<algorithm>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e5 + 5;
struct Node{
    int a, b; bool ok;
    friend bool operator<(const Node&p, const Node&q){
        return p.a < q.a;
    }
}s[N];
int pos[N];
signed main(){
    int n = init(), q = init();
    for (int i = 1; i <= n; ++i)
        s[i] = (Node) {init(), i, 1};
    std::stable_sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; ++i)
        pos[s[i].b] = i;
    for (int i = 1; i <= q; ++i) {
        int x = init();
        s[pos[x]].ok = 0;
        bool flag = 1;
        for (int j = n; j >= 3 && flag; --j) {
            if (s[j].ok == 0) continue;
            if (s[j - 1].ok == 0) {
                if (s[j - 2].a + s[j - 3].a > s[j].a) {
                    flag = 0;
                    print(s[j - 2].a + s[j - 3].a + s[j].a), putchar('\n');
                }
            }
            else if (s[j - 2].ok == 0) {
                if (s[j - 1].a + s[j - 3].a > s[j].a) {
                    flag = 0;
                    print(s[j - 1].a + s[j - 3].a + s[j].a), putchar('\n');
                }
            }
            else {
                if (s[j - 1].a + s[j - 2].a > s[j].a) {
                    flag = 0;
                    print(s[j - 1].a + s[j - 2].a + s[j].a), putchar('\n');
                }
            }
        }
        if (flag) print(-1), putchar('\n');
        s[pos[x]].ok = 1;
    }
}