T1
用一个堆维护最小的是谁，每次加入一个值x时查询堆顶是否小于x，有则买top卖x，之后分为是不是反悔操作判断要不要把pop。
然而好像其他人都push两个来进行反悔操作。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 #define int long long 7 using namespace std; 8 int ans,n; 9 struct point 10 { 11 int x,y; 12 friend bool operator <(point l,point r) 13 { 14 return l.x>r.x; 15 } 16 }; 17 priority_queue<point>q; 18 signed main() 19 { 20 //freopen("1.in","r",stdin); 21 //freopen("1.out","w",stdout); 22 scanf("%lld",&n); 23 for(int i=1,x;i<=n;i++) 24 { 25 scanf("%lld",&x); 26 point tmp={x,0}; 27 if(q.size()&&q.top().x<x) 28 { 29 ans+=x-q.top().x; 30 if(!q.top().y) q.pop(); 31 else 32 { 33 point res=q.top(); 34 q.pop(); 35 res.y=0; 36 q.push(res); 37 } 38 tmp.y=1; 39 } 40 q.push(tmp); 41 } 42 printf("%lld",ans); 43 return 0; 44 }
T2
1>
$ S(n,m)=sum_{i=0}^{m}C_{n}^{i} $
$ S(n,m)=sum_{i=0}^{m-1}C_{n-1}^{i}+sum_{i=0}^{m}C_{n-1}^{i} $
$ S(n,m)=S(n-1,m-1)+S(n-1,m) $
$ S(n,m)=2*S(n-1,m)-C_{n-1}^{m} $
2>
$ S(n,m)=S(n,m-1)+C_{n}^{m} $
有了这两个递推式子便可以用莫队O(nsqrt(n))解决啦。
ps:这里的莫队是一维的，可以把n,m看成一条线段。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define int long long 7 using namespace std; 8 const int k=490,N=1e5+10,mod=1e9+7; 9 int ans,n,m,id,q,S,fac[N],inv[N],f[N]; 10 struct question{int x,y,id;}a[N]; 11 bool comp(question l,question r) 12 { 13 if(l.x/k==r.x/k) return (l.x/k)&1?l.y>r.y:l.y<r.y; 14 return l.x/k<r.x/k; 15 } 16 int read() 17 { 18 int sum,k=1;char s; 19 while(s=getchar(),s<'0'||s>'9') if(s=='-') k=-1;sum=s-'0'; 20 while(s=getchar(),s>='0'&&s<='9') sum=sum*10+s-'0'; 21 return k*sum; 22 } 23 int qpow(int x,int y,int z) 24 { 25 int sum=1; 26 while(y) 27 { 28 if(y&1) sum=sum*x%z; 29 y>>=1; 30 x=x*x%z; 31 } 32 return sum; 33 } 34 int C(int x,int y) 35 { 36 if(x<y) return 0; 37 return fac[x]*inv[y]%mod*inv[x-y]%mod; 38 } 39 signed main() 40 { 41 //freopen("1.in","r",stdin); 42 //freopen("2.out","w",stdout); 43 id=read(),q=read(); 44 for(int i=1;i<=q;i++) 45 { 46 a[i].x=read(),a[i].y=read(),a[i].id=i; 47 S=max(S,max(a[i].x,a[i].y)); 48 } 49 fac[0]=1; 50 for(int i=1;i<=S;i++) fac[i]=fac[i-1]*i%mod; 51 inv[S]=qpow(fac[S],mod-2,mod); 52 for(int i=S-1;i>-1;i--) inv[i]=inv[i+1]*(i+1)%mod; 53 sort(a+1,a+q+1,comp); 54 n=m=0;ans=1; 55 for(int i=1;i<=q;i++) 56 { 57 while(n<a[i].x) n++,ans=(ans*2-C(n-1,m)+mod)%mod; 58 while(n>a[i].x) n--,ans=(ans+C(n,m))%mod*inv[2]%mod; 59 while(m<a[i].y) m++,ans=(ans+C(n,m))%mod; 60 while(m>a[i].y) m--,ans=(ans-C(n,m+1)+mod)%mod; 61 f[a[i].id]=ans; 62 } 63 for(int i=1;i<=q;i++) printf("%lld ",f[i]); 64 return 0; 65 }
T3
首先有一个重要性质：本题的边点同阶
疯狂模拟即可