nowcoder (树状数组+贡献计数+前缀和)

發表於 更新於 分類於 Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘

题目

https://ac.nowcoder.com/acm/contest/9033/D

大意

给数组，和整数k

每次询问一个区间，它的所有子区间出现次数最多的数正好等于k的区间数

数组长度和询问数都是3e5

题解

我们要统计的是正好，

那么如果可以计算出 <=k,那么我们可以计算出<=k-1 然后想减少，只需要2倍时间

对于询问我们采取离线计算

下面问题变成如何计算 区间[l,r] 上满足 <=k 的方案数

考虑以 i 为起点，其对应的右侧<=k的分界点split(i2)。

很容易发现，这个分界点是随着i增加，单调递增的，因为如果 i1 < i2,那么[i2,split(i2)] 是最长的<=k，也就是其最多出现次数为k,那么[i1,split(i2)] 的最多出现次数,大于等于k,且[i1,split(i2)+1] 大于等于k+1

因此split(i1)<=split(i2)

有这个单调性质，我们很容易能扫一遍在O(n)时间内求出，每个左侧i的点，对应的右侧分界点

再一个O(n) 可以在不考虑选点范围的情况下，计算出 点对的前缀和presum[i] =presum[i-1]+(split(i)-i+1)

来看看和目标之间的差距

要求[l,r] 中间满足<=k 的点对数量

presum[r] - presum[l-1] 计算了左侧起点在[l,r]的满足<=k点对数量，但是没有对点对的右侧点进行限制

也就是需要去掉 左侧断点 [l,r] 内，但是右侧端点 >r的点对

= sum[i = l->r][ split(i) > r? split(i) - r: 0 ]

询问很多，不可能每次去计算，想前缀和之类，却 r和i没有直接关系，因为i是原始数组下标，而r是询问中提供的

拆分一下, 这样 前面部分可以通过 前缀和的方式统计，而后面的部分，只需要统计左端点在[l,r],右端点超过r的个数，在处理具体询问的时候乘上r即可。

= sum[i = l->r][ split(i) > r? split(i): 0 ] - sum[i = l->r][ split(i) > r? r : 0 ]

由此r从大到小处理询问即可。 O(n)

关于区间统计，上树状数组就行了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
#define lowbit(x) ((x)&(-x))
#define MAXN 300010
ll n,q,k;
ll a[MAXN];

// 树状数组
void add(vector<ll>&arr,ll x,ll y) {
  for(; x <= n; x += lowbit(x)){
    arr[x] += y;
  }
}
ll sum(vector<ll>&arr,ll x) {
  ll ans = 0;
  for(; x > 0; x -= lowbit(x)){
    ans += arr[x];
  }
  return ans;
}
ll sto(vector<ll>&arr,ll l,ll r) {
  return sum(arr,r) - sum(arr,l-1);
}

// [值] = 下标数组
vector<ll>v[MAXN];
// 离线 询问
struct ask {
  ll l,r,i;
}w[MAXN];

ll ans[MAXN];

bool cmp(ask a,ask b) {
  return a.r > b.r;
}

// < k
void solve(ll k,ll pw) {
  priority_queue< pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>> >p; // {idx,value}
  rep(i,1,n+1){
    if(v[i].size() >= k){
      // 首个超过 k个的坐标和值
      p.push({v[i][k-1],i});
    }
  }
  vector<ll> cnt(MAXN,0);
  vector<ll>l2r(MAXN,0); // 以i为区间左端点，右侧端点选取(>=k)范围的左侧
  vector< vector<ll> > r2l(MAXN,vector<ll>());
  rep(i,1,n+1){
    while(!p.empty() && (
          // 之后的部分个数 小于k
          cnt[p.top().second] + k-1 >= v[p.top().second].size() ||
          // 每次用完了头部不pop，靠这个来避免重复？
          v[p.top().second][cnt[p.top().second] + k-1] != p.top().first
          )){
      p.pop();
    }
    // 扫描到当前 a[i] 出现的次数
    cnt[a[i]] ++;
    // 后续可出现连续 k个a[i]
    if(v[a[i]].size() > cnt[a[i]]+k-1){
      p.push({v[a[i]][cnt[a[i]]+k-1],a[i]});
    }
    l2r[i] = p.empty()?n:(p.top().first - 1);
    // 右侧区间的左侧坐标 -> 左端点, 从i到f[i] 这一段 最大次数小于k
    r2l[l2r[i]].pb(i);
  }

  // [0->i]为左端点不合法个数前缀和
  vector<ll>s(MAXN,0);
  rep(i,1,n+1){
    // 表示<k的对的方案数
    s[i] = s[i-1] + l2r[i]-i+1;
  }
  // 树状数组
  vector<vector<ll> >tr(2, vector<ll>(MAXN,0));
  ll nn = 0;
  // 询问从右向左处理
  per(i,1,n+1){
    while(w[nn].r >= i && nn < q) {
      ans[w[nn].i] += pw*(
          // 小于k 的对数方案
          (s[w[nn].r] - s[w[nn].l-1])
          // 当前  大于k 的对数方案
          +sto(tr[0],w[nn].l,w[nn].r)+w[nn].r*sto(tr[1],w[nn].l,w[nn].r)
      );
      nn ++;
    }
    rep(j,0,r2l[i].size()){
      ll xay = r2l[i][j];
      // 大于等于k的对数
      add(tr[0],xay,-i);
      // 次数
      add(tr[1],xay,1);
    }
  }
}

int main() {
  scanf("%lld %lld %lld",&n,&q,&k);
  rep(i,1,n+1){
    cin >> a[i];
    v[a[i]].pb(i);
  }
  rep(i,0,q){
    scanf("%lld %lld",&w[i].l,&w[i].r);
    w[i].i = i;
  }
  // 询问 右侧r 从大到小排列
  sort(w,w+q,cmp);

  solve(k+1,1);
  if(k != 1){
    solve(k,-1);
  }
  rep(i,0,q){
    printf("%lld\n",ans[i]);
  }
  return 0;
}

收获总结

  1. =k如果难算，可以变成计算<=k 和 <=k-1 然后进行 相减
  2. 离线处理询问
  3. 处理“不能”前缀和的部分，拆分成可前缀和的部分，和部分统计，询问时再乘积的部分分别处理，降低到O(n)
  4. 在有前缀和的代码里 用1-index比0-index方便一些