题面：https://www.cnblogs.com/Juve/articles/11639755.html
trade：
70分sbdp，然后一直想优化，dp还是很好写的
正解是反悔贪心
维护一个小根堆，每到一天，设当前的值是a，堆中最小值是b，如果a>b，那么给ans加上a-b
然后堆中插入两个a，因为如果以后还有更优的一个c，那么a-b+b-c=a-c，相当与选了c
第二个a用于以后来卖a，和以后卖出的货物配对。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define int long long 7 using namespace std; 8 const int MAXN=1e5+5; 9 int n,a[MAXN],ans=0; 10 priority_queue<int>q; 11 signed main(){ 12 scanf("%lld",&n); 13 for(int i=1;i<=n;++i) scanf("%lld",&a[i]); 14 for(int i=1;i<=n;++i){ 15 if(!q.empty()){ 16 int x=-q.top(); 17 if(x<a[i]){ 18 ans+=a[i]-x; 19 q.pop(); 20 q.push(-a[i]); 21 } 22 } 23 q.push(-a[i]); 24 } 25 printf("%lld ",ans); 26 return 0; 27 }
sum：
n和m相等的测试点是为了启发我们得到正解
n都相等：$S_{n,m}=S_{n,m-1}+C_n^m$
m都相等：$S_{n,m}=2*S_{n-1,m}-C_{n-1}^m$
如果我们把n，m看成区间，那么区间扩展后的答案都可以O(1)转移
其实就是用上面的式子推$S_{n,m+1},S_{n,m-1},S_{n+1,m},S_{n-1,m}$
然后莫队即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define int long long 7 #define re register 8 using namespace std; 9 const int mod=1e9+7; 10 const int MAXN=1e5+5; 11 int id,q,n,m,ans=1,maxx=0,blo,l=0,r=0,res[MAXN]; 12 int fac[MAXN],inv[MAXN]; 13 inline int q_pow(re int a,re int b,re int p){ 14 re int res=1; 15 while(b){ 16 if(b&1) res=res*a%p; 17 a=a*a%p; 18 b>>=1; 19 } 20 return res; 21 } 22 inline void get_C(re int N){ 23 fac[0]=fac[1]=inv[0]=1; 24 for(re int i=2;i<=N;++i) fac[i]=fac[i-1]*i%mod; 25 inv[N]=q_pow(fac[N],mod-2,mod); 26 for(re int i=N-1;i>=0;--i) inv[i]=inv[i+1]*(i+1)%mod; 27 } 28 inline int C(re int n,re int m){ 29 if(m>n) return 0; 30 if(m==n) return 1; 31 return fac[n]*inv[m]%mod*inv[n-m]%mod; 32 } 33 struct node{ 34 int l,r,id; 35 friend bool operator < (node a,node b){ 36 return a.l/blo+1==b.l/blo+1?a.r<b.r:a.l<b.l; 37 } 38 }ask[MAXN]; 39 signed main(){ 40 scanf("%lld%lld",&id,&q); 41 get_C(1e5); 42 for(int i=1;i<=q;++i){ 43 scanf("%lld%lld",&ask[i].r,&ask[i].l); 44 ask[i].id=i; 45 maxx=max(ask[i].r,maxx); 46 } 47 blo=sqrt(maxx)+1; 48 sort(ask+1,ask+q+1); 49 for(int i=1;i<=q;++i){ 50 while(l<ask[i].l) ans=(ans+C(r,++l))%mod; 51 while(l>ask[i].l) ans=(ans-C(r,l--)+mod)%mod; 52 while(r<ask[i].r) ans=(ans*2%mod-C(r++,l)+mod)%mod; 53 while(r>ask[i].r) ans=(ans+C(--r,l))%mod*inv[2]%mod; 54 res[ask[i].id]=ans; 55 } 56 for(int i=1;i<=q;++i) 57 printf("%lld ",res[i]); 58 return 0; 59 }
building：