牛客练习赛 73 D

• 2020 年 12 月 16 日
• 筆記
• 数据结构

题目链接

离别

离线算法+线段树

容易发现当我们枚举右端点r时，符合条件的左端点是一段连续的区间

我们可以用队列来维护这个连续区间的左右端点

当枚举到端点\(i\)时，将下标\(i\)插入到队列\(q[a_i]\)中

如果元素大于k，队首+1即为左端点（注意要与之前的取max)

如果元素等于k，队首即为右端点

这样对每个右端点，就找到了符合条件的左端点

然后将询问离线，以右端点排序

对于每个右端点，将符合条件的左端点插入线段树中，同时查询答案

时间复杂度\(O（nlogn)\)

（注意要开long long，还有update 与 query 都要push_down)

代码

#include <bits/stdc++.h>
#define LL long long
#define int long long 
#define ls(p) p << 1
#define rs(p) p << 1|1
using namespace std;
const int N = 3e5 + 101;
int tree[N * 4], laz[N * 4];
int a[N], b[N], tl[N], tr[N];
int n, q, k, ans[N];
struct node {int id, l;};
queue<int>que[N];
vector<node>ask[N];

void push_up(int p)
{
	tree[p] = tree[ls(p)] + tree[rs(p)];
}
void push_down(int p,int l,int r)
{
	int mid = (l + r) / 2;
	tree[ls(p)] += (mid - l + 1) * laz[p];
	tree[rs(p)] += (r - mid) * laz[p];
	laz[ls(p)] += laz[p];
	laz[rs(p)] += laz[p];
	laz[p] = 0;
} 

void update(int p,int l,int r,int nl,int nr,int ad)
{
	if(nl <= l && r <= nr)
	{
		laz[p] += ad;tree[p] += (r - l + 1) * ad;
		return; 
	}
	push_down(p,l,r);
	int mid = (l + r) / 2; 
	if(nl <= mid) update(ls(p),l,mid,nl,nr,ad);
	if(nr > mid) update(rs(p),mid + 1,r,nl,nr,ad);
	push_up(p); 
}

int query(int p,int l,int r,int nl,int nr)
{
	int ans = 0;
	if(nl <= l && r <= nr) return tree[p];
	push_down(p,l,r);
	int mid = (l + r) / 2;
	if(nl <= mid) ans += query(ls(p),l,mid,nl,nr);
	if(nr > mid) ans += query(rs(p),mid + 1,r,nl,nr);
	return ans;
}
signed main()
{
	scanf("%lld%lld%lld",&n,&q,&k);
	for(int i = 1;i <= n; i++)
	    scanf("%lld",&a[i]);
	int L = 0,R = 0; // 对应的左区间符合条件的答案 
	for(int i = 1;i <= n; i++)
	{
		que[a[i]].push(i);
		if(que[a[i]].size() > k)
			L = max(L,que[a[i]].front()),que[a[i]].pop(); //更新左端点 
		if(que[a[i]].size() == k)
			R = max(R,que[a[i]].front());
		tl[i] = L + 1;tr[i] = R;
	} 
	for(int i = 1;i <= q; i++)
	{
		int l, r;scanf("%lld%lld",&l,&r);
		ask[r].push_back((node){i,l});
	}
	for(int i = 1;i <= n; i++)
	{
		if(tl[i] <= tr[i]) update(1,1,n,tl[i],tr[i],1);
		for(int j = 0;j < ask[i].size(); j++)
			ans[ask[i][j].id] = query(1,1,n,ask[i][j].l,i);
	}
	for(int i = 1;i <= q; i++) printf("%lld\n",ans[i]);
}

/*
4 4 2
1 2 3 4
1 2
1 3 
1 4 
2 4
*/