BEIJING2016 回转寿司

wjh15101051's space

卧薪尝胆，厚积薄发。

BEIJING2016 回转寿司

Date: Sat Sep 08 19:50:35 CST 2018

In Category: NoCategory

Description：

给一个序列，判断有多少子区间和 $\in[L,R]$ 。

$1\le n \le 100000$

Solution：

对于这种子区间计数问题，十有八九是枚举左(右)边界，统计合法的另一个边界个数。

这题就是统计有多少合法的子区间 $L\le sum_r-sum_{l-1}\le R$ ，移个项就是 $sum_r-R\le sum_{l-1}\le sum_r-L$ ，权值线段树扫一遍即可。

Code：


#include

#include

#include

#include

#include

#include

#include

using namespace std;

int n;

typedef long long ll;

#define MAXN 100010

ll lef,rig;

ll a[MAXN];

ll b[MAXN],tot = 0;

int m;

map fr;

struct node

{

	int lc,rc;

	int sum;

	node(){sum = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int p,int l,int r)

{

	if(l == r){++t[rt].sum;return;}

	++t[rt].sum;

	if(p <= mid)add(t[rt].lc,p,l,mid);

	else add(t[rt].rc,p,mid + 1,r);

	return;

}

int query(int rt,int L,int R,int l,int r)

{

	if(L > R)return 0;

	if(L <= l && r <= R)return t[rt].sum;

	int res = 0;

	if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

	if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

	scanf("%d%lld%lld",&n,&lef,&rig);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	ll sum = 0;b[++tot] = 0;

	for(int i = 1;i <= n;++i)

	{

		sum += a[i];

		b[++tot] = sum;

	}

	sort(b + 1,b + 1 + tot);

	m = 0;

	for(int i = 1;i <= tot;++i)if(i == 1 || b[i] != b[i - 1])fr[b[i]] = ++m;

	fr[0x3f3f3f3f3f3f3f3f] = m + 1;

	build(root,1,m);

	add(root,fr[0],1,m);

	sum = 0;

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		sum += a[i];

		ll l = fr.lower_bound(sum - rig) -> second,r = fr.upper_bound(sum - lef) -> second;--r;

		ans += query(root,l,r,1,m);

		add(root,fr[sum],1,m);

	}

	cout << ans << endl;

	return 0;

}

In tag: 数据结构-线段树

wjh15101051