1.给两个非严格递增的序列，每次分别从两个数组中抽出一个区间并合并，求排序后第k小。单log。
分治即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=5E5+5; 4 int n,m,a[maxn],b[maxn]; 5 inline int read() 6 { 7 char ch=getchar(); 8 while(!isdigit(ch)) 9 ch=getchar(); 10 int sum=ch-'0'; 11 ch=getchar(); 12 while(isdigit(ch)) 13 { 14 sum=sum*10+ch-'0'; 15 ch=getchar(); 16 } 17 return sum; 18 } 19 void write(int x) 20 { 21 if(x>=10) 22 write(x/10); 23 putchar('0'+x%10); 24 } 25 inline void writen(int x) 26 { 27 write(x); 28 putchar(' '); 29 } 30 int ask(int*A,int*B,int lenA,int lenB,int k) 31 { 32 if(lenA>lenB) 33 return ask(B,A,lenB,lenA,k); 34 if(lenA==0) 35 return B[k]; 36 if(k==1) 37 return min(A[1],B[1]); 38 int x=min(lenA,k/2); 39 int y=k-x; 40 if(A[x]<B[y]) 41 return ask(A+x,B,lenA-x,lenB,y); 42 else 43 return ask(A,B+y,lenA,lenB-y,x); 44 } 45 inline int query(int L1,int R1,int L2,int R2) 46 { 47 int len=R1-L1+R2-L2+2; 48 return ask(a+L1-1,b+L2-1,R1-L1+1,R2-L2+1,len/2+1); 49 } 50 int main() 51 { 52 ios::sync_with_stdio(false); 53 n=read(),m=read(); 54 for(int i=1;i<=n;++i) 55 a[i]=read(); 56 for(int i=1;i<=n;++i) 57 b[i]=read(); 58 while(m--) 59 { 60 int opt=read(); 61 if(opt == 2) 62 { 63 int L1=read(),R1=read(); 64 int L2=read(),R2=read(); 65 writen(query(L1,R1,L2,R2)); 66 } 67 else 68 { 69 int p=read(),pos=read(),x=read(); 70 if(p==0) 71 a[pos]=x; 72 else 73 b[pos]=x; 74 } 75 } 76 return 0; 77 }
2.现在有m个数，每个数的位置在1~n之间，以pi的概率出现。现在有q个线段，它们互不包含，每个线段的贡献为（它覆盖的区间中）（（每个位置上（数的最小值））的最大值）的期望，若没有任何数，贡献为0。求所有线段贡献的和。单log。n,m≤1E5，数字的值≤1E9，均为正整数。
由于每条线段是独立的，考察单独线段，其贡献为：
$$E(x)=sum_{x=0}^{inf}{P(v_i geq x)}$$
其中x为这条线段覆盖到的数的最小值的随机变量。
则
$$P(max_{i=l}^{r}{v_igeq x})$$
$$=1-P(max_{i=l}^{r}{v_ileq x-1})$$
$$=1-prod_{i=l}^{r}{P(v_{i}leq x-1)}$$
$$=1-prod_{i=l}^{r}{1-P(v_{i}geq x)}$$
对于一个特定的x，可以通过所有小于等于x-1的数不出现的概率的积减去所有数都不出现的概率的积求出贡献。
观察连乘符号后的式子，只有x变为一个输入的数字时才会发生变化，即对于一个x，答案是以区间的行形式分布的。
这样每次计算一个新的值，只要除去一个数，再乘上一个数即可。由于除0问题，x的值应从大到小枚举。
注意到线段没有包含关系，因此某个位置上值的改动对于线段而言是区间修改的。
这样，我们要支持区间修改，全局查询，用一棵线段树维护即可。
1 #pragma GCC optimize 2 2 #include<bits/stdc++.h> 3 #define mod 1000000007 4 using namespace std; 5 typedef long long int ll; 6 const int maxn=2E5+5; 7 int n,m,q; 8 int tmpL[maxn],tmpR[maxn]; 9 ll tot[maxn],last[maxn]; 10 ll ans,sum[maxn*4],tag[maxn*4]; 11 vector<ll>val[maxn],small[maxn]; 12 struct pt 13 { 14 ll x,p,val; 15 bool operator<(const pt&A)const 16 { 17 return val>A.val; 18 } 19 }a[maxn]; 20 vector<pt>wait[maxn]; 21 inline ll qpow(ll x,ll y) 22 { 23 ll ans=1,base=x; 24 while(y) 25 { 26 if(y&1) 27 ans=ans*base%mod; 28 base=base*base%mod; 29 y>>=1; 30 } 31 return ans; 32 } 33 void build(int l,int r,int num) 34 { 35 tag[num]=1; 36 sum[num]=r-l+1; 37 if(l==r) 38 return; 39 int mid=(l+r)>>1; 40 build(l,mid,num<<1),build(mid+1,r,num<<1|1); 41 } 42 inline void pushdown(int l,int r,int num) 43 { 44 if(tag[num]==1) 45 return; 46 sum[num]=sum[num]*tag[num]%mod; 47 if(l==r) 48 { 49 tag[num]=1; 50 return; 51 } 52 tag[num<<1]=tag[num<<1]*tag[num]%mod; 53 tag[num<<1|1]=tag[num<<1|1]*tag[num]%mod; 54 tag[num]=1; 55 } 56 inline void update(int l,int r,int num) 57 { 58 pushdown(l,r,num); 59 if(l==r) 60 return; 61 int mid=(l+r)>>1; 62 pushdown(l,mid,num<<1),pushdown(mid+1,r,num<<1|1); 63 sum[num]=(sum[num<<1]+sum[num<<1|1])%mod; 64 } 65 void change(int L,int R,int l,int r,ll x,int num) 66 { 67 update(l,r,num); 68 if(L<=l&&r<=R) 69 { 70 tag[num]=tag[num]*x%mod; 71 update(l,r,num); 72 return; 73 } 74 int mid=(l+r)>>1; 75 if(R<=mid) 76 change(L,R,l,mid,x,num<<1); 77 else if(mid<L) 78 change(L,R,mid+1,r,x,num<<1|1); 79 else 80 change(L,R,l,mid,x,num<<1),change(L,R,mid+1,r,x,num<<1|1); 81 update(l,r,num); 82 } 83 int main() 84 { 85 ios::sync_with_stdio(false); 86 cin>>n>>m>>q; 87 for(int i=1;i<=m;++i) 88 { 89 cin>>a[i].x>>a[i].val>>a[i].p; 90 val[a[i].x].push_back(a[i].val); 91 wait[a[i].x].push_back(a[i]); 92 } 93 for(int i=1;i<=q;++i) 94 cin>>tmpL[i]>>tmpR[i]; 95 sort(tmpL+1,tmpL+q+1); 96 sort(tmpR+1,tmpR+q+1); 97 sort(a+1,a+m+1); 98 build(1,q,1); 99 for(int i=1;i<=n;++i) 100 { 101 last[i]=tot[i]=1; 102 sort(wait[i].begin(),wait[i].end()); 103 sort(val[i].begin(),val[i].end()); 104 for(int j=0;j<val[i].size();++j) 105 { 106 tot[i]=tot[i]*(1-wait[i][val[i].size()-j-1].p+mod)%mod; 107 small[i].push_back(tot[i]); 108 } 109 } 110 for(int i=1;i<=m;++i) 111 { 112 do 113 { 114 int L=lower_bound(tmpR+1,tmpR+q+1,a[i].x)-tmpR; 115 int R=upper_bound(tmpL+1,tmpL+q+1,a[i].x)-tmpL; 116 --R; 117 int pos=lower_bound(val[a[i].x].begin(),val[a[i].x].end(),a[i].val)-val[a[i].x].begin(); 118 if(L>R) 119 goto end; 120 change(L,R,1,q,qpow(last[a[i].x],mod-2),1); 121 --pos; 122 if(pos>=0) 123 last[a[i].x]=(1-small[a[i].x][pos]+tot[a[i].x]+mod)%mod; 124 else 125 last[a[i].x]=(tot[a[i].x]+mod)%mod; 126 change(L,R,1,q,last[a[i].x],1); 127 end:; 128 ++i; 129 }while(a[i].val==a[i-1].val); 130 --i; 131 ans=(ans+(q-sum[1]+mod)%mod*(a[i].val-a[i+1].val)%mod)%mod; 132 } 133 cout<<ans<<endl; 134 return 0; 135 }