hdu 6464 “字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛 1004 免费送气球

其实一个线段树维护当前区间数字的个数和当前区间和就可以A了。

然后赛时加了很多了mod依旧没有过的原因是在存储询问的时，脑残的用了（看到op=1时，均小于的错觉）。

然后就过了。

思路：

1、首先想到需要离散化一下。

2、考虑用一颗线段树来维护当前区间的数字个数，和当前区间和（离散化前的数字的和）。

3、前缀和的思想，求第L小和第R小之间数字的和 就是 求前R小的数字和减去前L-1小的数字和。

Code：

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
struct node
{
	int l;
	int r;
	ll cnt;//次数
	ll sum;//和
}que[100005 * 4];
const ll mod = 1000000007;
int n, m, ql, qr;
int a[100005], cnt = 0;
ll val;
void up(int k)
{
	que[k].cnt = que[k << 1].cnt + que[k << 1 | 1].cnt;
	que[k].sum = (que[k << 1].sum + que[k << 1 | 1].sum) % mod;
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].cnt = 0;
	que[k].sum = 0;
	if (left == right)
		return;
	imid;
	build(lson);
	build(rson);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].cnt += val;
		que[k].sum += (val * a[left - 1]) % mod;
		return;
	}
	imid;
	update(lson);
	update(rson);
	up(k);
}
ll query(int left = 1, int right = n, int k = 1)
{
	if (left == right)
		return a[left - 1] * val % mod;
	imid;
	if (que[k << 1].cnt > val)
		return query(lson);
	else if (que[k << 1].cnt < val)
	{
		val -= que[k << 1].cnt;
		return (que[k << 1].sum + query(rson)) % mod;
	}
	else
		return que[k << 1].sum;
}
struct Q
{
	ll op;
	ll ql;
	ll qr;
}qq[100005];
int main()
{
	int q;
	n = 100000;
	scanf("%d", &q);
	build();
	for (int i = 0; i < q; i++)
	{
		scanf("%lld%lld%lld", &qq[i].op, &qq[i].ql, &qq[i].qr);
		if (qq[i].op == 1)
			a[cnt++] = qq[i].qr;
	}
	sort(a, a + cnt);
	cnt = unique(a, a + cnt) - a;
	for (int i = 0; i < q; i++)
	{
		if (qq[i].op == 1)
			qq[i].qr = lower_bound(a, a + cnt, qq[i].qr) - a + 1;
		if (qq[i].op == 1)
		{
			ql = qq[i].qr;
			qr = qq[i].qr;
			val = qq[i].ql;
			update();
		}
		else
		{
			qq[i].ql--;
			ll ans = 0;
			val = qq[i].qr;
			ans += query();
			ans %= mod;
			val = qq[i].ql;
			ans -= query();
			ans %= mod;
			ans = (ans + mod) % mod;
			printf("%lld\n", ans);
		}
	}
}
/*
4
1 1000000000 1000000000
1 1000000000 1000000000
1 1000000000 1000000000
2 1 3000000000

6
1 1000000000 1000000000
1 1000000000 1000000000
1 1000000000 1000000000
1 1000000000 1000000000
1 1000000000 1000000000
2 1 5000000000

6
1 5 1
1 6 3
2 2 5
2 4 8
1 2 2
2 4 8
*/