分析
欢迎私聊,感觉说的不太清晰。
我们考虑如何保证每个区间的某一个种类个数达到 。这个我们可以考虑离线询问,将 的询问差分成 的答案。那么我们先把一个询问拆分成两个,再来考虑前缀的做法 。我们对于每个数,保留它的前一个和他相同相同的元素。那么枚举的右端点到了 ,那么左端点在 都是可以保证区间恰好 个的。那么这个我们可以考虑使用线段树来维护。
如何保证我们枚举的区间是保证它是最大元素。这个可以考虑动态维护两个指针 。 我们每当这两个指针中相同元素到达了 时,就移动到这个元素的 处,这样就保证了这个区间最多出现 个相同元素。
图例
代码
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define ll long long ll read() { ll x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();} return f ? -x : x; } const ll N = 3e5 + 1000; ll tag[N << 2],sum[N << 2]; void pushdown(ll x,ll l,ll r) { if(tag[x]) { ll mid = l + r >> 1; tag[x << 1] += tag[x];tag[x << 1 | 1] += tag[x]; sum[x << 1] += (mid - l + 1) * tag[x]; sum[x << 1 | 1] += (r - mid) * tag[x]; tag[x] = 0; } } void update(ll u,ll l,ll r,ll L,ll R,ll vl) { if(l > R || r < L) return; if(L <= l && r <= R) {tag[u] += vl;sum[u] += (r - l + 1) * vl;return;} ll mid = (l + r) >> 1;pushdown(u,l,r); update(u << 1,l,mid,L,R,vl);update(u << 1 | 1,mid + 1,r,L,R,vl); sum[u] = (sum[u << 1] + sum[u << 1 | 1]); } ll ask(ll u,ll l,ll r,ll L,ll R) { if(l > R || r < L) return 0; if(L <= l && r <= R) return sum[u]; ll mid = (l + r) >> 1;pushdown(u,l,r); return ask(u << 1,l,mid,L,R) + ask(u << 1 | 1,mid + 1,r,L,R); } struct Node {ll l,r,type,id;}; vector<Node> Q[N]; ll n,m,k,A[N],si[N],ans[N]; vector<ll> pos[N]; int main() { n = read();m = read();k = read(); for(ll i = 1;i <= n;i++) A[i] = read(); for(ll i = 1;i <= m;i++) { ll l = read(),r = read(); Q[r].push_back((Node){l,r,1,i}); } for(ll i = 1;i <= n;i++) si[i] = pos[A[i]].size(),pos[A[i]].push_back(i); for(ll i = 1,l = 0,r = 0;i <= n;i++) { if(si[i] >= k - 1) r = max(r,pos[A[i]][si[i] - k + 1]); if(si[i] >= k) l = max(l,pos[A[i]][si[i] - k]); if(l < r) update(1,1,n,l+1,r,1); for(auto x : Q[i]) { ans[x.id] += x.type * ask(1,1,n,x.l,x.r); } } for(ll i = 1;i <= m;i++) printf("%lld\n",ans[i]); return 0; }