MLE 0pts求助!

P1001 A+B Problem

crz_qwq @ 2024-08-02 19:27:39

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=32;
struct balanced_tree{
    int trie[N*M][2],sz[N*M],tot=0;
    void init()
    {
        memset(trie,0,sizeof trie);
        memset(sz,0,sizeof sz);
    } 
    bool find(int x)
    {
        int p=0;
        for(int i=M-1;i>=0;--i)
        {
            int k=(x>>i)&1;
            if(!trie[p][k])
                return 0;
            p=trie[p][k];
        }
        return 1;
    }
    void insert(int x)
    {
        int p=0;
        for(int i=M-1;i>=0;--i)
        {
            int k=(x>>i)&1;
            if(!trie[p][k])
                trie[p][k]=++tot;
            p=trie[p][k];
            ++sz[p];
        }
    }
    void erase(int x)
    {
        if(!find(x))
            return ;
        int p=0;
        for(int i=M-1;i>=0;--i)
        {
            int k=(x>>i)&1;
            p=trie[p][k];
            --sz[p];
        }
    }
    int rank(int x)
    {
        int p=0,res=0;
        for(int i=M-1;i>=0;--i)
        {
            int k=(x>>i)&1;
            if(k)
                res+=sz[trie[p][0]];
            p=trie[p][k];
            if(!p)
                break;
        }
        return res;
    }
    int kth(int x)
    {
        int p=0,res=0;
        for(int i=M-1;i>=0;--i)
        {
            if(sz[trie[p][0]]>=x)
                p=trie[p][0]; 
            else
            {
                x-=sz[trie[p][0]];
                res+=(1<<i);
                p=trie[p][1];
            }
        }
        return res;
    }
    int pre(int x){return kth(rank(x));}
    int nxt(int x){return kth(rank(x+1)+1);}
}tr;
int a[N];
int query_rank(int p,int pl,int pr,int L,int R,int k)
{
    if(R<pl||pr<L)
        return 0;
    if(L<=pl&&pr<=R)
    {
        for(int i=pl;i<=pr;++i)
            tr.insert(a[i]);
        int ans=tr.rank(k);
        for(int i=pl;i<=pr;++i)
            tr.erase(a[i]);
        return ans;
    }
    int mid=(pl+pr)>>1;
    return query_rank(p<<1,pl,mid,L,R,k)+query_rank(p<<1|1,mid+1,pr,L,R,k);
}
int query_kth(int p,int pl,int pr,int L,int R,int k)
{
    int l=-1,r=1e9+1;
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(query_rank(p,pl,pr,L,R,mid)<k)
            l=mid;
        else
            r=mid;
    }
    return l;
}
void update(int p,int d){a[p]=d;}
int query_pre(int p,int pl,int pr,int L,int R,int k)
{
    if(R<pl||pr<L)
        return -2147483647;
    if(L<=pl&&pr<=R)
    {
        for(int i=pl;i<=pr;++i)
            tr.insert(a[i]);
        int ans=tr.pre(k);
        for(int i=pl;i<=pr;++i)
            tr.erase(a[i]);
        return ans;
    }
    int mid=(pl+pr)>>1;
    return max(query_pre(p<<1,pl,mid,L,R,k),query_pre(p<<1|1,mid+1,pr,L,R,k));
}
int query_nxt(int p,int pl,int pr,int L,int R,int k)
{
    if(R<pl||pr<L)
        return 2147483647;
    if(L<=pl&&pr<=R)
    {
        for(int i=pl;i<=pr;++i)
            tr.insert(a[i]);
        int ans=tr.nxt(k);
        for(int i=pl;i<=pr;++i)
            tr.erase(a[i]);
        return ans;
    }
    int mid=(pl+pr)<<1;
    return min(query_nxt(p<<1,pl,mid,L,R,k),query_nxt(p<<1|1,mid+1,pr,L,R,k));
}
int query(int p,int pl,int pr,int L,int R)
{
    if(R<pl||pr<L)
        return 0;
    if(L<=pl&&pr<=R)
    {
        int res=0;
        for(int i=pl;i<=pr;++i)
            res+=a[i];
        return res;
    }
    int mid=(pl+pr)>>1;
    return query(p<<1,pl,mid,L,R)+query(p<<1|1,mid+1,pr,L,R);
}
signed main()
{
    int x,y;
    cin>>x>>y;
    update(1,x);
    update(2,y);
    cout<<query_rank(1,1,2,1,1,2)*query_kth(1,1,2,1,1,2)*query_nxt(1,1,2,1,1,2)*query_pre(1,1,2,2,1,2)*1+query(1,1,2,1,2);
}

by huyangmu @ 2024-08-02 20:08:56

莱德,需要我们。


by crz_qwq @ 2024-08-02 20:09:33

@General0826


by crz_qwq @ 2024-08-02 21:15:42

@General0826 我们,需要莱德!


by crz_qwq @ 2024-08-03 09:18:39

@huyangmu gengen队全体阵亡了。。。


by jz17751587162 @ 2024-08-06 09:35:11

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a+b; 
    return 0;
}

简单易懂的代码 @crz_qwq


by Max_robot @ 2024-09-13 19:00:01

不是,一道红题被你做成了紫题?


上一页 |