• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

hdu7020 Array(2021杭电暑假多校5)多数投票算法

admin

11月 28, 2021

题意

给一个长度为(n)​的数组(a)​,问有多少个子区间存在绝对众数(即有一个数出现次数大于(lfloorfrac{R-L+1}{2}floor)​)。((a_ile{10}^6,1le nle{10}^6)​)

分析

其实这是道原题:「CodePlus 2017 11 月赛」Yazid 的新生舞会

首先枚举哪个数是绝对众数,设为(x)​​​​,由多数投票算法我们可以把所有(x)​​​​的位置改为(1)​​​​,所有非(x)​​​​的位置改为(-1)​​​​。(x)​​​​是区间绝对众数的区间就是和大于(0)​​​的区间(即算前缀和的一个二维偏序)。用树状数组维护的复杂度为(n^2logn)​​​​。

我们发现,上面暴力的做法复杂度比暴力(O(n^2))​还高是由于(-1)​的点太多了。但是他们大多数不对答案产生贡献,那么就可以考虑用到哪些(-1)​再在树状数组中对它进行插入/查询。对于值为(1)​的点,直接在树状数组上查询/插入即可。对于值为(-1)​的点,若它的前缀和为当前最小值,那么它之后的一段(-1)​的答案一定为(0)​,考虑之后用到再延迟插入即可。其他值为(-1)​的点同样直接查询/插入即可。因为一个(1)​最多只在它之后产生一个非最小值的(-1)​且最多在它之前用掉一个延迟更新的(-1)​,所以操作次数不超过(3n)​。又发现所有延迟更新的区间是不相交的,所以可以(O(1))​维护延迟更新的段。总时间复杂度为(O(nlogn))​​​​​。

最后考虑到当前前缀和的变化一定是(+1,-1)​​​或者直接变为最小值的。直接用数组和一个指针替换树状数组,暴力转移当前答案即可。

代码

(O(nlogn))

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
constexpr int N(1e6+5);
struct Fenwick{
  int cnt[N*2];
  vector<pii>inserted;
  void insert(int p,int v) {
    if(v>0) inserted.push_back({p,v});
    for(p+=N;p<N*2;p+=(p&-p)) {
      cnt[p]+=v;
    }
  }
  int count(int p) {
    int ans=0;
    for(p+=N;p;p-=(p&-p)) {
      ans+=cnt[p];
    }
    return ans;
  }
  void clear() {
    for(pii p:inserted)
      insert(p.first,-p.second);
    inserted.clear();
  }
}fw;

struct Seg{
  vector<pii>segs;
  void add(int l,int r) {
    segs.push_back(pii(l+N,r+N));
  }
  void de(int i) {
    i+=N;
    while(!segs.empty() && segs.back().first<=i){
      int& j=segs.back().first;
      fw.insert(j-N,1);
      j++;
      if(j>segs.back().second)
        segs.pop_back();
    }
  }
  void clear() {
    segs.clear();
  }
}sg;

void solve() {
  int n,mx=0;
  cin>>n;
  vector<int>a(n+1);
  for(int i=1;i<=n;i++) {
    cin>>a[i];
    mx=max(a[i],mx);
  }
  vector<vector<int>>nums(mx+1);
  for(int i=1;i<=n;i++) nums[a[i]].push_back(i);
  ll ans=0;
  for(int num=0;num<=mx;num++) {
    vector<int>&pos=nums[num];
    if(pos.empty()) continue;
    pos.push_back(n+1);
    int minn=0,now=0;
    fw.clear();
    sg.clear();
    fw.insert(0,1);
    for(int i=1,j=0;i<=n;) {
      if(a[i]==num) {
        sg.de(now);
        fw.insert(++now,1);
        ans+=fw.count(now-1);
        j++;
        i++;
      }
      else {
        if(now==minn) {
          int l=now-1,r=now-(pos[j]-i);
          now-=(pos[j]-i);
          sg.add(r,l);
          i=pos[j];
        }
        else {
          fw.insert(--now,1);
          ans+=fw.count(now-1);
          i++;
        }
        minn=min(minn,now);
      }
    }
  }
  cout<<ans<<'
';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin>>T;
  while(T--) solve();
  return 0;
}

(O(n))

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
constexpr int N(1e6+5);

struct Array{
  int a[N*2],ans=0;
  vector<int>pos;
  void insert(int i) {
    i+=N;
    a[i]++;
    pos.push_back(i);
  }
  int count(int i,int d) {
    i+=N;
    ans+=d*a[i];
    return ans;
  }
  void to0() {
    ans=0;
  }
  void clear() {
    for(int p:pos) a[p]=0;
    pos.clear();
    to0();
  }
}fw;

struct Seg{
  vector<pii>segs;
  void add(int l,int r) {
    segs.push_back(pii(l+N,r+N));
  }
  void de(int i) {
    i+=N;
    while(!segs.empty() && segs.back().first<=i){
      int& j=segs.back().first;
      fw.insert(j-N);
      j++;
      if(j>segs.back().second)
        segs.pop_back();
    }
  }
  void clear() {
    segs.clear();
  }
}sg;

void solve() {
  int n,mx=0;
  cin>>n;
  vector<int>a(n+1);
  for(int i=1;i<=n;i++) {
    cin>>a[i];
    mx=max(a[i],mx);
  }
  vector<vector<int>>nums(mx+1);
  for(int i=1;i<=n;i++) nums[a[i]].push_back(i);
  ll ans=0;
  for(int num=0;num<=mx;num++) {
    vector<int>&pos=nums[num];
    if(pos.empty()) continue;
    pos.push_back(n+1);
    int minn=0,now=0;
    fw.clear();
    sg.clear();
    fw.insert(0);
    for(int i=1,j=0;i<=n;) {
      if(a[i]==num) {
        sg.de(now);
        ans+=fw.count(now++,1);
        fw.insert(now);
        j++;
        i++;
      }
      else {
        if(now==minn) {
          int l=now-1,r=now-(pos[j]-i);
          now-=(pos[j]-i);
          fw.to0();
          sg.add(r,l);
          i=pos[j];
        }
        else {
          ans+=fw.count(--now,-1);
          fw.insert(now);
          i++;
        }
        minn=min(minn,now);
      }
    }
  }
  cout<<ans<<'
';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T=1;
  cin>>T;
  while(T--) solve();
  return 0;
}

发表评论

您的电子邮箱地址不会被公开。