牛客練習賽 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
*/