daily 1

CF 540E

树状数组+离散化+思维

首先如果交换序列之间没有数，那么就很好求，现在我们考虑不属于交换序列内的数

我们假定当前位置为i，p[i]为该位置一开始的位置 f[i]为离散化后i的值

那么我们先加上交换序列的逆序对

然后加上之间数的逆序对,再减去交换序列里的逆序对

abs(f[i]-f[p[i]])+1-(abs(i-p[i])+1)

然后就ok了

#define lowbit(x) x&-x
void solve(){
  int n;cin>>n;
  vector<int>l(n+1),r(n+1),pre_pos,pre_value;
  map<int,int>mp;
  for(int i=1;i<=n;++i){
    cin>>l[i]>>r[i];
    mp[l[i]]=0;
    mp[r[i]]=0;
  }
  int cnt=0;
  pre_pos.push_back(0);
  pre_value.push_back(0);
  for(auto& k:mp){
    k.second=++cnt;
    pre_pos.push_back(cnt);
    pre_value.push_back(k.first);
  }
  vector<int>tree(cnt+1);
  for(int i=1;i<=n;++i){
    l[i]=mp[l[i]];
    r[i]=mp[r[i]];
  }
  auto add=[&](int x,int v){
    while(x<=cnt){
        tree[x]+=v;
        x+=lowbit(x);
    }
  };
  auto sum=[&](int x){
    ll ans=0;
    while(x){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
  };
  for(int i=1;i<=n;++i){
    swap(pre_pos[l[i]],pre_pos[r[i]]);
  }
  ll ans=0;
  for(int i=1;i<=cnt;++i){
    add(pre_pos[i],1);
    ans+=i-sum(pre_pos[i]);
    ans+=(abs(pre_value[i]-pre_value[pre_pos[i]])-abs(i-pre_pos[i]));
  }
  cout<<ans<<'\n';
  return;
}

下午做点某讯的面试题吧，今天上午面了tx一面，感觉还挺好的