题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4627
数据生成器:http://paste.ubuntu.com/23149177/
这个玩意儿,就是一个权值BIT
搞出前缀和之后,得到可行解是一个区间,于是BIT维护一下
考试的时候,一直想着NOI的超级钢琴,搞得连二分都想到了,却没想到正解
考试的时候,态度还是不端正啊
#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; }
I am so grateful for your article. Fantastic.
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!
Well I really enjoyed reading it. This tip procured by you is very constructive for accurate planning.