2019icpc徐州网络赛 E.XKC's basketball team(线段树)

题目链接

大意:给你长度n的数组和k,让你输出n个数,表示每个位置向右最远的位置pos,使得a[pos]-a[i]>=k,输出两个位置中间隔的数量。
思路:直接建一个维护区间最大值的线段树,每次查询直接查[i+1,n]范围内>=a[i]+k的最远位置即可。
我们查询的时候先查右儿子,没查到就查左儿子,否则答案必然在右儿子中,右儿子中没答案的话,那么答案必然在左儿子中(查询的区间要合法)



#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 11;
int n;
LL m;
LL a[N];
#define mid (l+r>>1)
#define ls o<<1
#define rs o<<1|1
int t[N << 2];
void build(int o, int l, int r) {
	if (l == r) {
		t[o] = a[l];
		return ;
	}
	build(ls, l, mid);
	build(rs, mid + 1, r);
	t[o] = max(t[ls], t[rs]);
}
int get(int o, int l, int r, int x, int y, int d) {
	if (l == r && t[o] >= d) {
		return l;
	}
	if (l == r)return -1;
	int tmp = -1;
	if (t[rs] >= d && y > mid) {
		tmp = get(rs, mid + 1, r, x, y, d);
	}
	if (t[ls] >= d && x <= mid && tmp == -1) {
		tmp = get(ls, l, mid, x, y, d);
	}
	return tmp;

}
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		int tmp;
		if (i == n)tmp = -1;
		else tmp = get(1, 1, n, i + 1, n, a[i] + m);
		if (tmp == -1)cout << -1;
		else cout << tmp - i - 1;
		if (i != n)cout << ' ';
		else cout << '\n';
	}
	return 0;
}
全部评论

相关推荐

03-15 20:26
已编辑
电子科技大学 C++
T3题面:给一个3e5数组,每次询问长度为len的子数组乘积的和,如果子数组乘积&gt;1e9,则视为0.赛后一分钟想出来了,比赛时打了个暴力+线段树注意到1e9大约是2^30,&nbsp;因此len长度如果&gt;30就直接输出0,30以内做一个记忆化就行,复杂度O(30*n)感觉是以前比赛做过的题,忘了怎么做了。。。---upd:&nbsp;忘了数据范围了,如果有0,1的话那这样也不行
blueswiller:给出一个做法,刚刚才想到,应该没问题,时间复杂度为 O(max(30n, nlogn)): 1. 根据 0 切分数组。2. 现在问题转化为>=1 的情况,我们首先维护每一个数前一个 > 1 的数的位置,同时维护一个长度的差分数组,初始值全为 0。3. 我们从每一个数 i 开始向前跳,至多跳 30 次,维护这个过程中的乘积,于是得到 30 个区间加和。举例:假设从 j1 跳到 j2 ,相当于对查询长度 (i- j1 + 1) 至 (i - j2) 贡献 a_i * ... * a_j1。4. 对于所有区间加和,我们采用差分数组结合树状数组对其进行维护,由于长度至多为 n ,树状数组构建的复杂度为 O(nlogn),于是,构建阶段的复杂度为 O(max(30n, nlogn))。在线单次查询的复杂度为树状数组查询的复杂度 O(logn)。
投递淘天集团等公司10个岗位 > 笔试
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务