显然问题即求$frac{sum_{xle lle rle y}(max_{lle ile r}a_{i}+min_{lle ile r}a_{i})}{(y-x+2)(y-x+1)}$
分母显然是常数，分子中$max$和$min$是类似地，不妨仅考虑$sum_{xle lle rle y}max_{lle ile r}a_{i}$
将询问离线，不断增大右端点$r$，并维护$ans_{i}=sum_{r’=i}^{r}max_{ile jle r’}a_{j}$，那么即对$ans_{i}$区间求和
将$ans_{i}$写作$rcdot max_{i}-sum_{i}$的形式（其中$max_{i}=max_{ile jle r}a_{j}$），显然可以对两者分别求和
下面，考虑从$r-1$变为$r$对$(max_{i},sum_{i})$的影响：
维护一个单调栈（从栈底到栈顶单调递减），假设弹出栈顶元素$x$，且下一个元素为$y$（若栈为空则$y=0$），那么即对区间$(y,x]$的$max_{i}$增加$a_{r}-a_{x}$，$sum_{i}$增加$(r-1)(a_{r}-a_{x})$
另外还要维护$r$的答案，即令$(max_{r},sum_{r})=(a_{r},(r-1)a_{r})$
即要支持区间加和区间查询，使用线段树即可，复杂度为$o(nlog n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define mod 1000000007 5 #define ll long long 6 #define pii pair<int,int> 7 #define mp make_pair 8 #define fi first 9 #define se second 10 #define L (k<<1) 11 #define R (L+1) 12 #define mid (l+r>>1) 13 struct Data{ 14 int l,r,id; 15 bool operator < (const Data &k)const{ 16 return r<k.r; 17 } 18 }q[N]; 19 int t,n,m,inv[N],a[N],mn[N],mx[N],ans[N]; 20 pii tag[N<<2],f[N<<2]; 21 pii merge(pii x,pii y){ 22 return mp((x.fi+y.fi)%mod,(x.se+y.se)%mod); 23 } 24 void upd(int k,int l,int r,pii o){ 25 int len=r-l+1; 26 tag[k]=merge(tag[k],o); 27 f[k]=merge(f[k],mp((ll)len*o.fi%mod,(ll)len*o.se%mod)); 28 } 29 void down(int k,int l,int r){ 30 upd(L,l,mid,tag[k]); 31 upd(R,mid+1,r,tag[k]); 32 tag[k]=mp(0,0); 33 } 34 void build(int k,int l,int r){ 35 f[k]=mp(0,0); 36 if (l==r)return; 37 build(L,l,mid); 38 build(R,mid+1,r); 39 } 40 void update(int k,int l,int r,int x,int y,pii z){ 41 if ((l>y)||(x>r))return; 42 if ((x<=l)&&(r<=y)){ 43 upd(k,l,r,z); 44 return; 45 } 46 down(k,l,r); 47 update(L,l,mid,x,y,z); 48 update(R,mid+1,r,x,y,z); 49 f[k]=merge(f[L],f[R]); 50 } 51 pii query(int k,int l,int r,int x,int y){ 52 if ((l>y)||(x>r))return mp(0,0); 53 if ((x<=l)&&(r<=y))return f[k]; 54 down(k,l,r); 55 return merge(query(L,l,mid,x,y),query(R,mid+1,r,x,y)); 56 } 57 int main(){ 58 inv[0]=inv[1]=1; 59 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; 60 scanf("%d",&t); 61 while (t--){ 62 scanf("%d%d",&n,&m); 63 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 64 for(int i=1;i<=m;i++){ 65 scanf("%d%d",&q[i].l,&q[i].r); 66 q[i].id=i; 67 } 68 sort(q+1,q+m+1); 69 mn[0]=mx[0]=0; 70 memset(tag,0,sizeof(tag)); 71 memset(f,0,sizeof(f)); 72 for(int i=1,j=1;i<=n;i++){ 73 update(1,1,n,i,i,mp(2*a[i]%mod,(ll)2*(i-1)*a[i]%mod)); 74 while ((mx[0])&&(a[mx[mx[0]]]<a[i])){ 75 int x=mx[mx[0]],y=mx[--mx[0]]; 76 update(1,1,n,y+1,x,mp((a[i]-a[x]+mod)%mod,(ll)(i-1)*(a[i]-a[x]+mod)%mod)); 77 } 78 while ((mn[0])&&(a[mn[mn[0]]]>a[i])){ 79 int x=mn[mn[0]],y=mn[--mn[0]]; 80 update(1,1,n,y+1,x,mp((a[i]-a[x]+mod)%mod,(ll)(i-1)*(a[i]-a[x]+mod)%mod)); 81 } 82 mx[++mx[0]]=mn[++mn[0]]=i; 83 while ((j<=m)&&(q[j].r==i)){ 84 pii o=query(1,1,n,q[j].l,i); 85 ans[q[j].id]=((ll)i*o.fi-o.se+mod)%mod*inv[i-q[j].l+2]%mod*inv[i-q[j].l+1]%mod; 86 j++; 87 } 88 } 89 for(int i=1;i<=m;i++)printf("%d ",ans[i]); 90 } 91 return 0; 92 }
View Code
When you’re trying to spy on someone’s phone, you need to make sure the software isn’t found by them once it’s installed.
You can use parent management software to guide and supervise children’s behavior on the Internet. With the help of the following 10 smartest parent management software, you can track your child’s call history, browsing history, dangerous content access, apps they install, etc.