SPOJ-HJB
给出一段长度为n(1≤n≤500000)的数列A(0≤a[i]≤109)，定义f(a,b)=min{A[i]|a≤i≤b}求该数列的
∑1≤a≤b<c≤d≤n[f(a,b)≤f(c,d)](mod109+7)首先离散化,对于区间[l，r],RMQ找值最小的位置pos,计算含有这个位置的区间个数tot=(pos−l+1)(r−pos)这些区间的f值都为a[pos]，树状数组中求得小于等于它的区间个数num,这些区间的影响为tot∗num再加上这个区间中含有该位置的区间对答案的影响为(pos−l+1)(r−pos)(r−pos+1)(r−pos+2)6(推导过程略)递归处理[l,pos−1],[pos+1,r]，最后再把tot插入树状数组中。注意模防止溢出，复杂度为O(nlogn)
#include <cstdio> #include <queue> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int maxn=5e5+7; const int mod=1e9+7; int n,m; int dp[maxn][22]; int mm[maxn],a[maxn]; int bit[maxn]; int inv6; vector<int> hh; void initRMQ(int n,int b[]) { mm[0] = -1; for(int i = 1; i <= n; i++) { mm[i] = ((i&(i-1)) == 0)?mm[i-1]+1:mm[i-1]; dp[i][0] = i; } for(int j = 1; j <= mm[n]; j++) for(int i = 1; i + (1<<j) -1 <= n; i++) { int ll=dp[i][j-1],rr=dp[i+(1<<(j-1))][j-1]; if(a[ll]<a[rr]) dp[i][j] = ll; else dp[i][j] = rr; } } int qpow(int a,int b) { long long r=1,x=a; while(b) { if(b&1) r=r*x%mod; b>>=1; x=x*x%mod; } return r; } int rmq(int x,int y) { int k = mm[y-x+1]; int ll=dp[x][k],rr=dp[y-(1<<k)+1][k]; if(a[ll]<a[rr]) return ll; else return rr; } int getid(int x) { return lower_bound(hh.begin(),hh.end(),x)-hh.begin()+1; } void add(int x,int d) { while(x<=n) { bit[x]=(bit[x]+d)%mod; x+=x&-x; } } int sum(int x) { int res=0; while(x) { res=(res+bit[x])%mod; x-=x&-x; } return res; } long long ans=0; void divide(int L,int R) { if(L>R) return ; int pos=rmq(L,R),res=0; int val=getid(a[pos]),rl=R-pos; res=(pos-L+1ll)*rl%mod*(rl+1)%mod*(rl+2)%mod*inv6%mod; long long tot=(pos-L+1ll)*(rl+1)%mod; ans=(ans+tot*sum(val))%mod; ans=(ans+res)%mod; divide(L,pos-1); divide(pos+1,R); add(val,tot); } int main() { inv6=qpow(6,mod-2); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); hh.push_back(a[i]); } initRMQ(n,a); sort(hh.begin(),hh.end()); divide(1,n); printf("%d\n",ans); return 0; }