也好。
该来的迟早会来。
反思再说吧。
T1：
处理平均数类题的通用方法：把每一项都减去平均数。
李某东上的原题，不会。
直接做是没法做的，很容易想到二分答案，关键就是怎么check。
把每一项都减去mid值之后再做前缀和，统计逆序对。
具体统计的方法，就是扔进结构体里sort，用树状数组统计下标的逆序对，答案是一样的。
卡常且卡精度。
要开long long。不然一分没有。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int a[100005],n,t[100005],s[100005];long long k; 5 void add(int p,int w){for(;p<=100001;p+=p&-p)t[p]+=w;} 6 int ask(int p,int a=0){for(;p;p-=p&-p)a+=t[p];return a;} 7 struct ps{double w;int p;friend bool operator<(ps a,ps b){return a.w<b.w;}}p[100005]; 8 long long chk(double x){ 9 long long inver=0;double sum=0;p[0]=(ps){0,0}; 10 for(int i=1;i<=n;++i)p[i]=(ps){sum+=a[i]-x,i}; 11 sort(p,p+n+1); 12 for(int i=n;~i;--i)inver+=ask(p[i].p+1),add(p[i].p+1,1); 13 for(int i=0;i<=n;++i)add(i+1,-1);//printf("%lld\n",inver); 14 return inver; 15 } 16 int main(){ 17 scanf("%d%lld",&n,&k);k--; 18 double l=1,r=0; 19 for(int i=1;i<=n;++i)scanf("%d",&a[i]),r=max(r,a[i]*1.0); 20 while(r-l>1e-5)if(chk((l+r)/2)>k)r=(l+r)/2;else l=(l+r)/2; 21 printf("%.4lf\n",l); 22 }
T2：
最裸的矩阵快速幂。
这一行的填色方案只与上一行有关，所以dp。
dp[i][j]表示在第i行填了特定j中颜色的方案数。
考虑转移。枚举两行的颜色数再枚举交集即可。
如果上一行有i种下一行有j种交集为k种。
转移条件是i+j-k<=p&&i+j-k>=q。
那么就是一个组合数学问题了。
先在上一行的颜色里选出重复部分$C_i^k$
再选出这一行交集以外的部分$C_{p-i}^{j-k}$
然后的问题就是已知某k种颜色填n个位置，要求每种颜色必须出现。我是dp做的，据说可以容斥。
然后发现每一层的转移系数都相同，那就是简单的矩阵快速幂了。
注意取模。
1 #include<cstdio> 2 #define int long long 3 #define mod 998244353 4 int n,m,p,q,pl[101][101],C[101][101],base[101][101],ans[101],re[101][101],Ans; 5 void mult_base(){ 6 for(int i=1;i<=p;++i)for(int j=1;j<=p;++j)for(int k=1;k<=p;++k)re[i][j]=(re[i][j]+base[i][k]*base[k][j])%mod; 7 for(int i=1;i<=p;++i)for(int j=1;j<=p;++j)base[i][j]=re[i][j],re[i][j]=0; 8 } 9 void mult_ans(){ 10 for(int i=1;i<=p;++i)for(int j=1;j<=p;++j)re[0][i]=(re[0][i]+ans[j]*base[j][i])%mod; 11 for(int i=1;i<=p;++i)ans[i]=re[0][i],re[0][i]=0; 12 } 13 signed main(){ 14 scanf("%lld%lld%lld%lld",&n,&m,&p,&q);m--; 15 pl[0][0]=1; 16 for(int i=1;i<=n;++i)for(int j=1;j<=p;++j)pl[i][j]=(pl[i-1][j-1]+pl[i-1][j])*j%mod; 17 for(int i=0;i<=p;++i)C[i][0]=1; 18 for(int i=1;i<=p;++i)for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; 19 for(int x=1;x<=p;++x)for(int y=1;y<=p;++y)for(int c=0;c<=p;++c)if(x+y-c<=p&&x+y-c>=q) 20 base[x][y]=(base[x][y]+C[x][c]*C[p-x][y-c]%mod*pl[n][y])%mod; 21 for(int i=1;i<=p;++i)ans[i]=pl[n][i]*C[p][i]%mod; 22 for(;m;m>>=1,mult_base())if(m&1)mult_ans(); 23 for(int i=1;i<=p;++i)Ans=(Ans+ans[i])%mod; 24 printf("%lld\n",Ans); 25 }
T3：
对于每一个区间询问都可以拆成两部分：l-1以内的w以上的数产生-1贡献，r以内w以上的数产生1贡献。
然后就是可以考虑每一个位置的贡献了。是个二维偏序。
用主席树可以做到一个log，两个log会T成暴力。
然后修改一个位置就是删除原贡献添加新贡献。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 struct qs{int p,w,v;friend bool operator<(qs a,qs b){return a.p<b.p;}}qt[200005]; 5 int n,m,q,a[100005],cnt,rt[100005],ecnt,lc[10000005],rc[10000005],w[10000005],nw;long long lastans; 6 void insert(int &p,int cpy,int wp,int v,int cl=1,int cr=n+2){ 7 p=++ecnt; 8 if(cl==cr){w[p]=w[cpy]+v;return;} 9 if(wp<=cl+cr>>1)insert(lc[p],lc[cpy],wp,v,cl,cl+cr>>1),rc[p]=rc[cpy]; 10 else insert(rc[p],rc[cpy],wp,v,(cl+cr>>1)+1,cr),lc[p]=lc[cpy]; 11 w[p]=w[lc[p]]+w[rc[p]]; 12 } 13 int ask(int p,int pos,int cl=1,int cr=n+2){ 14 if(cr<=pos)return w[p]; 15 if(cl+cr>>1>=pos)return ask(lc[p],pos,cl,cl+cr>>1); 16 return w[lc[p]]+ask(rc[p],pos,(cl+cr>>1)+1,cr); 17 } 18 int main(){ 19 scanf("%d%d%d",&n,&m,&q); 20 for(int i=1;i<=n;++i)scanf("%d",&a[i]); 21 for(int i=1,x,y,W;i<=m;++i)scanf("%d%d%d",&x,&y,&W),qt[++cnt]=(qs){n-x+2,W,-1},qt[++cnt]=(qs){n-y+1,W,1}; 22 sort(qt+1,qt+1+cnt); 23 for(int i=1;i<=cnt;++i)if(qt[i].p==qt[i-1].p)insert(nw=0,rt[qt[i].p],qt[i].w,qt[i].v),rt[qt[i].p]=nw; 24 else{for(int j=qt[i-1].p+1;j<qt[i].p;++j)rt[j]=rt[j-1];insert(rt[qt[i].p],rt[qt[i].p-1],qt[i].w,qt[i].v);} 25 for(int j=qt[cnt].p+1;j<=n+2;++j)rt[j]=rt[j-1]; 26 for(int i=1;i<=n;++i)lastans+=ask(rt[n-i+1],a[i]); 27 printf("%lld\n",lastans); 28 for(long long i=1,p,W;i<=q;++i){ 29 scanf("%lld%lld",&p,&W); 30 p^=lastans;W^=lastans; 31 lastans-=ask(rt[n-p+1],a[p]);lastans+=ask(rt[n-p+1],a[p]=W); 32 printf("%lld\n",lastans); 33 } 34 }