题解：P3605 [USACO17JAN] Promotion Counting P

ivyjiao · 2024-10-02 17:48:58 · 题解

大家好，我是只会打暴力的 ivyjiao，我觉得权值树状数组太麻烦了，所以我拿暴力 AC 了这道题。什么线段树、离散化我觉得都没必要。

这题最开始也是等了很长时间没思路，苦于没法记录子树中的每个节点的值，又因为这题的 p_i 并不单调，所以树形 dp 是行不通了。

那么考虑把不在子树内的节点手动排除，具体的，我们遍历到每个节点时，先把这个节点的答案减掉现在已被记录的节点的值，搜完子树后得到新的已被记录的节点的值，新记录的值肯定都是这个节点的子树内的，再把新的答案加回来，就是正确的答案了。最后再把当前节点的值记录一下即可，这里我用的是 vector，加减答案时用 lower/upper_bound 就行。

然后就愉快的 AC 了，而且代码非常简短。

时间复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,q,a[N],fa[N],ans[N];
vector<int>b,G[N];
void dfs(int u){
    ans[u]-=b.size()-(upper_bound(b.begin(),b.end(),a[u])-b.begin());
    for(int i=0;i<G[u].size();i++) dfs(G[u][i]);
    ans[u]+=b.size()-(upper_bound(b.begin(),b.end(),a[u])-b.begin());
    b.insert(lower_bound(b.begin(),b.end(),a[u]),a[u]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        G[fa[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}

upd on 2024/11/2：

听说 vector 被卡了？为什么？？？

查了一下，原来 vector 的 \text{insert} 和 \text{erase} 是 O(n) 的，只不过做了很多优化。

但是 rope 的 \text{insert} 和 \text{erase} 都是严格 O(\sqrt n) 的！本题 1\leq n\leq 10^5，O(\sqrt n) 完全可过，时间复杂度 O(n\sqrt n)。

注意，rope 和 vector 的 \text{insert} 和 \text{erase} 的写法稍有不同，详见代码。

代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
const int N=1e5+1;
int n,q,a[N],fa[N],ans[N];
rope<int>b,G[N];
void dfs(int u){
    ans[u]-=b.size()-(upper_bound(b.begin(),b.end(),a[u])-b.begin());
    for(int i=0;i<G[u].size();i++) dfs(G[u][i]);
    ans[u]+=b.size()-(upper_bound(b.begin(),b.end(),a[u])-b.begin());
    b.insert(lower_bound(b.begin(),b.end(),a[u])-b.begin(),a[u]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
        cin>>fa[i];
        G[fa[i]].push_back(i);
    }
    dfs(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}