【BZOJ 4627】[BeiJing2016] 回转寿司

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4627
数据生成器:http://paste.ubuntu.com/23149177/

这个玩意儿,就是一个权值BIT
搞出前缀和之后,得到可行解是一个区间,于是BIT维护一下
考试的时候,一直想着NOI的超级钢琴,搞得连二分都想到了,却没想到正解
考试的时候,态度还是不端正啊H[O(5H1_XNFSSZ~@I6[~$VL

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 300000+9;

int arr[N],n,T,ls[N],rs[N];
LL sum[N],L,R,vout,hash[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int val[N];
	
	inline void modify(int p) {
		for (int i=p;i<=T;i+=lowbit(i))
			val[i]++;
	} 
	
	inline int query(int l, int r) {
		int ret = 0;
		for (int i=r;i;i-=lowbit(i)) ret += val[i];
		for (int i=l-1;i;i-=lowbit(i)) ret -= val[i];
		return ret;
	}	
};

int main(){
	n = read(); L = read(); R = read();
	for (int i=1;i<=n;i++) sum[i] = sum[i-1] + (arr[i]=read()); hash[++T] = 0;
	for (int i=1;i<=n;i++) hash[++T] = sum[i], hash[++T] = sum[i] - R, hash[++T] = sum[i] - L;
	sort(hash+1,hash+1+T); T = unique(hash+1,hash+1+T) - hash - 1;
	for (int i=1;i<=n;i++) 
		ls[i] = lower_bound(hash+1,hash+1+T,sum[i]-R) - hash,
		rs[i] = lower_bound(hash+1,hash+1+T,sum[i]-L) - hash,
		sum[i] = lower_bound(hash+1,hash+1+T,sum[i]) - hash;
	BIT::modify(lower_bound(hash+1,hash+1+T,0)-hash);
	for (int i=1;i<=n;i++) 
		vout += BIT::query(ls[i],rs[i]),
		BIT::modify(sum[i]);
	cout<<vout;
	return 0;
}

3 thoughts to “【BZOJ 4627】[BeiJing2016] 回转寿司”

  1. Having read this I thought it was very informative. I appreciate you taking the time and effort to put this article together. I once again find myself spending way to much time both reading and commenting. But so what, it was still worth it!

Leave a Reply

Your email address will not be published. Required fields are marked *