2023NOIP A层联测26-competition

本文主要是介绍2023NOIP A层联测26-competition，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

现在有一个题目数量为 $m$ 的比赛，有一个团队想要来参加。

这个团队有 $n$ 位选手，编号为 $i$ 的选手能做第 $l_i\sim r_i$ 道题，每一道题他都有 $100\%$ 的概率能做出来。

这个团队会随机派出一支队伍来参加这个比赛。

因为编号相邻的人关系更好，默契度也更高，所以说一个团队派出的队伍一直都是编号为连续的区间的选手。

一个队伍的得分为该队伍能做出的题的数量。

求这个团队参加比赛的期望得分。

注：一道题只能被做出来一次

$n\le10^6，m\le10^{18}$

先考虑一道题可以被做出多次的情况，不难得出答案为
$\sum\limits_{i=1}^n(r_i-l_i+1)\cdot i\cdot(n-i+1)$

就是区间长度与包含 $i$ 的区间个数的乘积。

对于原题的情况，答案就要在这个基础上减去一道题重复做的次数。

从前往后做，令 $pre_{j}$ 表示当前这个人的左边最靠右的能做第 $j$ 道题的人。

那么对于第 $i$ 个人会做第 $j$ 道题，显然包含 $i,pre_{i,j}$ 的区间答案都会增加，所以答案减去 $pre_{i,j}\cdot(n-i+1)$

对于每个 $i$ ，先统计答案，再用线段树更新 $p re$ ，就是对于区间 $l_i,r_i]$ 用 $i$ 去覆盖。

具体实现上，不必开 $10^{18}$ 那么大的值域，只需把给的区间端点放在线段树就可以。线段树维护区间内的 $p re$ 之和，每次修改就区间覆盖。

时间复杂度 $O(n\log n)$ ，常数很大，需要优化，具体实现参照代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int N=1000001;
constexpr ll mod=1000000007;
int n,cnt,ans;
ll tr[N<<3],la[N<<3],a[N<<1],l[N],r[N],m;
unordered_map<ll,int> id;
inline int MOD(int x){return x>=mod?x-mod:x;}
ll ksm(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
inline void pushdown(int rt,int l,int r)
{if(la[rt]){int mid=l+r>>1;tr[rt<<1]=(a[mid+1]-a[l]+mod)*la[rt]%mod;tr[rt<<1|1]=(a[r+1]-a[mid+1]+mod)*la[rt]%mod;la[rt<<1]=la[rt<<1|1]=la[rt];la[rt]=0;}
}
int queryandchange(int rt,int l,int r,int x,int y,int d)
{if(x<=l&&r<=y){int ans=tr[rt];tr[rt]=(a[r+1]-a[l]+mod)*d%mod,la[rt]=d;return ans;}int mid=l+r>>1,ans=0;pushdown(rt,l,r);if(x<=mid) ans+=queryandchange(rt<<1,l,mid,x,y,d);if(mid<y) ans+=queryandchange(rt<<1|1,mid+1,r,x,y,d);tr[rt]=MOD(tr[rt<<1]+tr[rt<<1|1]);return MOD(ans);
}
int main()
{freopen("competition.in","r",stdin);freopen("competition.out","w",stdout);cin.tie(0)->sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>l[i]>>r[i],a[++cnt]=l[i],a[++cnt]=r[i]+1;sort(a+1,a+1+cnt);cnt=unique(a+1,a+1+cnt)-a-2;for(int i=1;i<=cnt+1;i++) id[a[i]]=i;for(int i=1;i<=cnt+1;i++) a[i]%=mod;for(int i=1;i<=n;i++) ans=(ans+1ll*queryandchange(1,1,cnt,id[l[i]],id[r[i]+1]-1,i)*(n-i+1))%mod;ans=MOD(-ans+mod);for(int i=1;i<=n;i++) ans=(ans+(r[i]-l[i]+1)%mod*i%mod*(n-i+1))%mod;cout<<(ans+mod)*ksm(1ll*n*(n+1)/2%mod,mod-2)%mod;
}