【牛客挑战赛32E】树上逆序对

ゝ一世哀愁。 2023-10-11 06:30 117阅读 0赞

[题目][Link 1]

数据范围非常奇怪，询问的逆序对个数\\(k\\leq 30000\\)，我们应该可以把所有的情况都求出来

发现对于树上两点\\(x,y\\)，如果\\(x\\)是\\(y\\)的祖先，那么绝对值较大的点的符号决定了能否形成逆序对

如果\\(a\_x>a\_y\\)，不取反\\(a\_x\\)，那么无论\\(a\_y\\)取反与否，肯定会形成逆序对，因为\\(a\_x>a\_y>-a\_y\\)；反之如果取反\\(a\_x\\)，那么无论\\(a\_y\\)取反与否，肯定不对形成逆序对，因为\\(a\_y>-a\_y>-a\_x\\)

于是我们按照绝对值从小到大排序，之后按照顺序加入树中，一个点对答案的贡献是**其子树内部小于它的点的个数加上到根的路径上大于它的点的个数**；当我们加入一个点\\(x\\)时，如果不取反，那么到根的路径上显然不会有点大于它，且子树内部全都小于它，形成的逆序对个数就是其子树内部的点的个数；如果取反，那么到根的路径上的点全都大于它，子树内部不会有点小于它，形成的逆序对个数就是到根的路径上点的个数

所以用树剖+树状数组求一下，之后搞一个背包来转移就好了，背包需要\\(\\rm bitset\\)优化

复杂度\\(O(n\\log^2n+\\frac\{nk\}\{w\})\\)

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define lb(i) (i&-i)
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    struct E{int v,nxt;}e[maxn<<1];
    struct pt{int x,id;}a[maxn];
    std::bitset<300001> dp;
    int n,num,Q,c[maxn],__;
    int sum[maxn],dfn[maxn],top[maxn],fa[maxn],head[maxn],deep[maxn],son[maxn];
    inline int cmp(pt A,pt B) {return A.x<B.x;}
    inline void add(int x,int y) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;
    }
    inline void ins(int x) {
        for(re int i=x;i<=n;i+=lb(i)) c[i]++;
    }
    inline int ask(int x) {
        int now=0;
        for(re int i=x;i;i-=lb(i)) now+=c[i];
        return now;
    }
    inline int calc(int l,int r) {return ask(r)-ask(l-1);}
    inline int get(int x) {
        int now=0;
        while(top[x]) now+=calc(dfn[top[x]],dfn[x]),x=fa[top[x]];
        return now;
    }
    void dfs1(int x) {
        sum[x]=1;
        for(re int i=head[x];i;i=e[i].nxt) {
            if(deep[e[i].v]) continue;
            deep[e[i].v]=deep[x]+1,fa[e[i].v]=x;
            dfs1(e[i].v),sum[x]+=sum[e[i].v];
            if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;
        }
    }
    void dfs2(int x,int topf) {
        top[x]=topf,dfn[x]=++__;
        if(!son[x]) return;
        dfs2(son[x],topf);
        for(re int i=head[x];i;i=e[i].nxt)
        if(!top[e[i].v]) dfs2(e[i].v,e[i].v);
    }
    int main() {
        n=read();
        for(re int i=1;i<=n;i++) a[i].x=read(),a[i].id=i;
        for(re int x,y,i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
        deep[1]=1,dfs1(1),dfs2(1,1);
        std::sort(a+1,a+n+1,cmp);
        dp[0]=1;
        for(re int i=1;i<=n;i++) {
            int x=calc(dfn[a[i].id],dfn[a[i].id]+sum[a[i].id]-1),y=get(a[i].id);
            dp=(dp<<x)|(dp<<y);ins(dfn[a[i].id]);
        }
        Q=read();while(Q--) puts(dp[read()]?"Orz":"QAQ");
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11566025.html

[Link 1]: https://ac.nowcoder.com/acm/contest/1087/E