发布时间：2024-06-04

abc356

D - Masked Popcount

题意：
$给定n,m,求\sum _{i=0}^n i\&m$
思路：
枚举m的二进制为1的位，则它出现的次数显然位在他前面的数+(在他后面的数+1)

• 例：$198的9出现次数为10(090,091,092,...,099)+(8+1)(190,191,..,198)=19$ 二进制同理，易推出式子，见代码

void solve(){
    int n,m;
    cin>>n>>m;
    int ans=0;
    //n++;
    for(int i=60;i>=0;i--){
        if(!(m>>i&1))continue;
        (ans+=(n>>i+1)<<i)%=mod;
        (ans+=max((n%(1ll<<i+1)-(1ll<<i))+1,0ll))%=mod;
    }
    cout<<ans<<"\n";
}

E - Max/Min

题意：
求$\sum_{i=1}^{N-1} \sum_{j=i+1}^N \frac{max(A_i,A_j)}{min(A_i,A_j)}$
$1 \leq n \leq 200000$
$1 \leq a_i \leq 1000000$
思路：
值域很小直接前缀和，然后枚举倍数即可，时间复杂度位nlogn

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1),cnt(1e6+10);
    for(int i=1;i<=n;i++)cin>>a[i],cnt[a[i]]++;
    for(int i=1;i<=1e6;i++)cnt[i]+=cnt[i-1];
    int ans=0;
    for(int i=1;i<=1e6;i++){
        ans+=(cnt[i]-cnt[i-1])*(cnt[i]-cnt[i-1]-1)/2;
        for(int j=i;j<=1e6;j+=i){
            ans+=(j/i)*(cnt[i]-cnt[i-1])*(cnt[min(1000000ll,j+i-1)]-cnt[j==i?i:j-1]);
        }
    }
    cout<<ans<<"\n";
}

F - Distance Component Size Query

题意：
给定询问q,值k，如果两个值差值小于等于k则连边

• 1 x如果x在集合S，则删除，否则加入
• 2 x求x的连通块

思路：
缩点，用pbds的平衡树实现set
集合s1维护原题意S,s2维护每个连通块值最大的点
则查询在哪个连通块只需要找大于等于当前值的点在哪
大小即为两个连通块最大值在s1中的下标相减

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define TR tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update>
TR s1,s2;
int q,k;
void solve(){
    cin>>q>>k;
    s1.insert(-3e18),s1.insert(3e18);
    s2.insert(-3e18),s2.insert(3e18);
    while(q--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            if(s1.find(x)==s1.end()){
                auto it=s1.insert(x).first;
                int w1=*prev(it),w2=*next(it);
                if(x-w1<=k)s2.erase(w1);
                if(w2-x>k)s2.insert(x);
            }
            else{
                auto it=s1.find(x);
                int w1=*prev(it),w2=*next(it);
                s1.erase(x),s2.erase(x);
                if(w2-w1>k)s2.insert(w1);
            }
            continue;
        }
        auto it=s2.lower_bound(x);
        cout<<s1.order_of_key(*it)-s1.order_of_key(*prev(it))<<"\n";
    }
}