[ICPC 2018 Beijing Onsite F]The Kth Largest Value

Link

Solution

询问组数极少。。一开始居然没看到。。。。
首先,用bitset维护出每个点能到的点的集合。对于每组询问,二分答案。
二分答案的时候,需要快速地查询bitset里面某段区间1的个数。
对于一个bitset,直接做区间和是O(\frac n{32})的。但是,可以对1的个数做一个前缀和,类似分块一样。这样,单次询问的复杂度就是O(1)了。

Code

const int XN=5e4+11;

std::vector<int> G[XN],C[XN];int n;

const int SIZE=(XN>>6)+1;
struct BitSet {
    unsigned long long b[SIZE];
    int sum[SIZE];

    void Reset() {
        memset(b,0,sizeof(b));
    }

    void Set(unsigned int pos,bool val) {
        val==0?(b[pos>>6]&=~(1ull<<(pos&63))):(b[pos>>6]|=1ull<<(pos&63));
    }

    void GetSum() {
        for(int i=0;i<SIZE;++i)
            sum[i]=(i==0?0:sum[i-1])+__builtin_popcountll(b[i]); 
    }

    int Sum(int l,int r) {
        return Sum(r)-Sum(l-1);
    }

    int Sum(int pos) {
        Reduce(pos,n);
        return pos<1?0:((pos>>6?sum[(pos>>6)-1]:0)+__builtin_popcountll(b[pos>>6]&(((__int128)1<<((pos&63)+1))-1)));
    }

    BitSet &operator |=(BitSet const &other) {
        for(int i=0;i<SIZE;++i)
            b[i]|=other.b[i];
        return *this;
    }

    bool Test(unsigned int pos) const {
        return b[pos>>6]>>(pos&63)&1;
    }
}set[XN];

int low[XN],dfn[XN],stack[XN],dfc,cc,belong[XN],size[XN],top;
bool instack[XN];
void DFS(int pos) {
    dfn[pos]=low[pos]=++dfc;
    instack[stack[++top]=pos]=1;
    for(auto u : G[pos])
        if(!dfn[u]) {
            DFS(u);
            Reduce(low[pos],low[u]);
        } else if(instack[u])
            Reduce(low[pos],dfn[u]);
    if(dfn[pos]==low[pos])
        for(size[++cc]=0,set[cc].Reset();stack[top+1]!=pos;top--) {
            int u=stack[top];
            instack[u]=0;
            belong[u]=cc;
            size[cc]++;
            set[cc].Set(u,1);
        }
}

int Sum(int x,int allb) {
    int res=0;
    for(int i=1;i<=n;++i)
        res+=set[belong[i]].Sum((x^i)&(~allb),(x^i)|allb);
    return res;
}

int Query(int k) {
    int res=0;
    for(int b=15;b>=0;--b) {
        int cnt=Sum(res|(1<<b),(1<<b)-1);
        if(k<=cnt)
            res|=1<<b;
        else
            k-=cnt;
    }
    return res;
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int T;std::cin>>T;
    while(T--) {
        int m,q;std::cin>>n>>m>>q;
        dfc=cc=0;
        for(int i=1;i<=n;++i) {
            G[i].clear();
            dfn[i]=0;
        }
        for(int i=1;i<=m;++i) {
            int x,y;std::cin>>x>>y;
            G[x].push_back(y);
        }

        for(int i=1;i<=n;++i)
            if(!dfn[i]) {
                DFS(i);
                assert(top==0);
            }

        static int deg[XN];

        for(int i=1;i<=cc;++i) {
            C[i].clear();
            deg[i]=0;
        }

        for(int i=1;i<=n;++i)
            for(auto u : G[i])
                if(belong[u]!=belong[i])
                    C[belong[i]].push_back(belong[u]);

        for(int i=1;i<=cc;++i) {
            std::sort(C[i].begin(),C[i].end());
            C[i].erase(std::unique(C[i].begin(),C[i].end()),C[i].end());
            for(int u : C[i])
                deg[u]++;
        }

        std::queue<int> Q;

        for(int i=1;i<=cc;++i)
            if(!deg[i])
                Q.push(i);

        while(!Q.empty()) {
            int pos=Q.front();Q.pop();
            for(auto u : C[pos]) {
                set[u]|=set[pos];
                if(--deg[u]==0)
                    Q.push(u);
            }
        }

        for(int i=1;i<=cc;++i)
            set[i].GetSum();

        while(q--) {
            int k;std::cin>>k;
            std::cout<<Query(k)<<'\n';
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注