题意就是题目上说的那样。。。给出一个n个数的序列,对于这个序列询问区间长度\(>=L\)且满足区间和\(>=M\)的区间的个数。数组下标从\(1\)开始,\(N\leq 10000,-100000\leq M,a[i] \leq 100000\)。
很久之前和ClearY吃饭的时候讨论的,后来她居然弄到校赛里面去了。。。
维护出来一个前缀和,那么对于位置\(pos\)来说,对答案的贡献就是位置\(i\)满足\(i <= pos-L\),而且\(sum[pos]-sum[i] >= M\)。那么我们从前往后扫,维护一棵平衡树,对于每个位置\(i\)找到他往后的\(L\)个位置\(pos\),查询比\(a[pos]-M\)小于等于的数有多少个就好了。这个treap写个rank函数就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> #define inf 0x3f3f3f3f #define oo ~0u>>1 #define maxn 10010 #define REP(i,x,y) for(int i=x;i<(y);i++) using namespace std; typedef long long ll; int n,m,L,sum[maxn]; struct node* null; struct node{ int key,s,w,num; node* ch[2]; node(int _key):key(_key),s(1),w(rand()),num(1){ch[0]=ch[1]=null;} inline void pushup(){s=ch[0]->s+ch[1]->s+num;} }*root; inline void rot(node* &rt,const bool& d){ //d=o left d=1 right node* k=rt->ch[d^1]; rt->ch[d^1]=k->ch[d]; k->ch[d]=rt; rt->pushup();k->pushup(); rt=k; } inline void Insert(node* &rt,const int& key){ if(rt==null) { rt=new node(key);return ; } bool d=key > rt->key; if(key==rt->key){ rt->num++; rt->pushup(); return ; } else Insert(rt->ch[d],key); if(rt->ch[d]->w < rt->w) rot(rt,d^1); else rt->pushup(); } inline int Rank(node* &rt,const int& key){ if(rt==null) return 0; //非法情况 int ls=rt->ch[0]->s; if(key<rt->key) return Rank(rt->ch[0],key); else return ls+rt->num+Rank(rt->ch[1],key); } inline void init(){ null=new node(0);null->ch[0]=null->ch[1]=null;null->s=0;null->w=oo;null->num=0; root=null; } int main() { int T;scanf("%d",&T); while(T--){ init(); scanf("%d %d %d",&n,&L,&m); REP(i,1,n+1) { int tmp;scanf("%d",&tmp); sum[i]=sum[i-1]+tmp; } int ans=0; for(int i=0;i+L<=n;i++){ Insert(root,sum[i]); int pos=i+L; int tmp=Rank(root,sum[pos]-m); ans+=tmp; } printf("%d\n",ans); } } |