滑动窗口时单调队列的经典问题。时间复杂度和空间复杂度都是o（n）。单调队列即，队列中保存的值是有单调性的。实现原理类似双指针。用head指针代表对首，tail代表队尾，head > tail 即队列为空。当窗体大小大于k时，head++，即q[head]+k-1 < i.当a[i]比队尾若干元素的值更最时，tail--，相当于删除了这若干值，因为这若干值对答案的贡献为0。单调队列的代码如下： int head = 0,tail = -1; for(int i = 1;i <= n; i++) { while(head <= tail && q[h...

题意：给你以1为根的树，问u到v有多少个节点，权值严格大于路径上所有节点的权值和w。保证v在u到根节点的路径上。首先我们考虑普通的解法，对于每一次询问，dfs从u节点到v节点，保存前缀最大值，那么当搜到的这个节点的权值大于前缀最大值时，答案加一，这样做的时间复杂度是o(nq)code: #include <bits/stdc++.h> #define pb push_back using namespace std; const int maxn = 1e5+100; vector<int>G[maxn]; int f[maxn],a[maxn]; void dfs(i...