MENU

HDU 6534 Chika and Friendly Pairs

2019-06-24 • 阅读: 21 • 数据结构—树状数组莫队阅读设置

莫队+树状数组+离散化

2019CCPC湖南全国邀请赛(广东省赛、江苏省赛)C题

C Chika and Friendly Pairs

这题是江苏省赛的题目,当时我和对友做出了4个题之后,我一个人就一直在看这题,然后就一直看到了比赛结束也不会做,正好昨天学了莫队,就把这题补一下。

首先这题题意很明确,题目所求答案需要满足的条件是 i<j,aiaj<=ki<j, |a_i - a_j|<=k ,化简一下变成 i<j,aik=<aj<=ai+ki<j, a_i-k=<a_j<=a_i+k , 给出 mm 个询问,对于这些询问我们可以用莫队来处理。关键在于我们怎么实现快速的转移呢?
加入我们当前区间为[l,r][l,r],也就是已知区间。我们需要转移到[q[i].l,q[i].r][q[i].l,q[i].r] ,可以发现我们每次转移l,rl,r 的时侯,已知区间都在我们的一侧,也就是说满足了 i<ji<j 这个关系,我们只需要统计 转移当前位置对答案带来的影响即可。 由刚刚推的关系式可得,当我们每转移一次时,我们只需要统计我们的已知区间[l,r][l,r]内有多个数满足 aik=<aj<=ai+ka_i-k=<a_j<=a_i+k ,这个可以用树状数组来解决。这样我们实现了O(logn)O(log_n) 转移。
另外数比较大,先离散化。另外一些细节在代码中说明。
总复杂度O(n3/2logn)O(n^{3/2} log_n)

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
using namespace std; 
#define lowbit(x) (x&(-x))
const int N = 27000+10;
int b[N],Ans[N];
int c[N];
int  a[N], g[N];
int up[N], low[N];
int n, m,block,tot, ans;
int  k;
int l, r;
struct query{
	int id, l, r,t;
}q[N];
bool cmp1(query o1, query o2)
{
	if (b[o1.l] == b[o2.l]) 
		return o1.r < o2.r; 
	return o1.l < o2.l;
}
void update(int pos,int val)
{
	for (; pos <= tot; pos += lowbit(pos))
		c[pos] += val;
}
int ask(int pos)
{
	int res=0;
	for (; pos; pos -= lowbit(pos))
		res += c[pos];
	return res;
}
void add(int pos)
{
	int s = ask(up[pos]) - ask(low[pos] - 1);
	ans += s;
	update(a[pos], 1);//这个最后加,如果刚开始就加的话就会把本身也算进去了
}
void del(int pos)
{
	update(a[pos], -1);//这个必须刚开始就减去,也是防止把自身算进去
	int s = ask(up[pos]) - ask(low[pos] - 1);
	ans -= s;
}
void Mo()
{
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++)
	{
		while (l < q[i].l) del(l++);
		while (l>q[i].l) add(--l);
		while (r < q[i].r) add(++r);
		while (r> q[i].r)  del(r--);
		Ans[q[i].id] = ans;
	}
	for (int i = 1; i <= m; i++)
		printf("%d\n", Ans[i]);
}
int main()
{
	scanf("%d%d%d", &n, &m,&k);
	block = sqrt(n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		g[i] = a[i];
		b[i] = (i - 1) / block + 1;
	}
	sort(g + 1, g + n + 1);
	tot = unique(g + 1, g + n + 1) - g - 1;
	for (int i = 1; i <= n; i++)
	{
		up[i] = upper_bound(g + 1, g + tot + 1, a[i] + k) - g -1 ;//因为需要找到<=a[i]+k,所以减1
		low[i] = lower_bound(g + 1, g + tot + 1, a[i] - k) - g;//这两个上下区间必须预处理,每次转移的时候再求这个上下界就会超时。
		a[i] = lower_bound(g + 1, g + tot + 1, a[i]) - g;
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp1);
	Mo();
	return 0;
}

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码