牛客练习赛 73 D

题目链接

离别

离线算法+线段树

容易发现当我们枚举右端点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

*/

巴特西

牛客练习赛 73 D

题目链接

代码

最新文章

热门文章