NOIP2023模拟13联测34 competition

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

题目大意

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

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

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

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

一个队伍的得分为该队伍能做出的题的数量，求这个团队参加比赛的期望得分。输出答案模 $10^9+7$ 后的值。

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

$1\leq n\leq 10^6,1\leq l_i\leq r_i\leq m\leq 10^{18}$

时间限制 $2000 m s$ ，空间限制 $512 MB$ 。

题解

直接求能做出多少道题并不简单，我们换一种思路：对于每道题，有多少种队伍做不出这道题？

对于每道题 $k$ ，我们设 $z_i$ 表示 $k$ 是否包含在 $l_i,r_i]$ 中，也就是第 $i$ 个人能不能做出这道题。那么，如果当前的队伍不能做出这道题，那选择的区间就不能包含任意一个 $z_i=1$ 的 $i$ 。也就是说，将所有 $z_i=1$ 的 $i$ 放在一起，则相邻的两个数 $i, j$ 之间有 $t = j - i - 1$ 个人不会做这道题，那么这部分中有 $\dfrac{t(t+1)}{2}$ 种队伍的选法使得这道题不能被做出来。

我们先求每种方案的得分之和，那么可以先将每种方案的得分都先看作 $m$ ，然后再减去不能做出的题目。

对于每道题 $k$ ，维护在 $i$ 之前最后一个能做出这道题的人 $lst_k$ 。然后遍历每个人，遍历 $l_i$ 到 $r_i$ ，每个位置 $k$ 的贡献为 $\dfrac{t(t+1)}{2}$ ，其中 $t=i-lst_k-1$ ，然后令 $lst_k=i$ 。这样做的话，时间复杂度为 $O (nm)$ 。下面考虑优化。

我们用一个 $v ec t or$ 来存储 $l s t$ 值相同的每一个区间，一开始总共只有一个区间 $[1, m]$ ， $l s t$ 值都是 $0$ 。对于每个人 $i$ ，都要修改 $l_i,r_i]$ 上的 $l s t$ 值。那么，我们对于 $v ec t or$ 中每一个与 $l_i,r_i]$ 有交集的区间 $[a, b]$ ，将这些区间与 $l_i,r_i]$ 有交集的部分按上面的方法向答案做出 $\dfrac{t(t+1)}{2}\times (b-a+1)$ 的贡献（注意这里的贡献是负的，是在原本将这道题看作做对，然后在减去不能做对的方案数乘上题目数量），因为这个区间表示 $m$ 道题中的 $b - a + 1$ 道题，所以要乘上 $(b - a + 1)$ 。再把有交集部分删掉，没有交集的部分再放回去。最后加上一个区间 $l_i,r_i]$ ， $l s t$ 值为 $i$ 。因为最后还有一部分没有算贡献的，我们可以在最后再加入一个区间 $[1, m]$ ， $l s t$ 值为 $n + 1$ ，就能够统计到这部分的贡献。

这样做的话会不会 $\text{TLE}$ 呢？不会。因为每次加入一个区间最多能够产生 $3$ 个区间（这个区间本身，与这个区间有交集的区间中最左边的没有交集的部分，与这个区间有交集的区间中最右边的没有交集的部分），为保证区间是从小到大排序的，所以加入一次区间的时间复杂度为 $O(\log n)$ （区间总数不会超过 $3 n$ ）。而每个区间在之后如果与新加入的区间有交集，则这个区间就会被删去，也就是说在之后最多只造成 $O (1)$ 的时间复杂度。所以，总时间复杂度为 $O(n\log n)$ 。

我们最终得到了每种方案的得分之和，再乘上方案数的逆元即可。

时间复杂度为 $O(n\log n)$ 。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
const long long mod=1e9+7;
int n;
long long m,ans=0;
struct node{long long x,y,w;bool operator<(const node ax)const{return y<ax.y;}
};
vector<node>v;
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
long long gt(long long k){return k*(k+1)/2%mod;
}
void pt(long long x,long long y,long long w){auto it=lower_bound(v.begin(),v.end(),(node){0,x,0});node vl=(node){0,0,-1},vr=(node){0,0,-1};while((*it).x<=y){if((*it).x<x) vl=(node){(*it).x,x-1,(*it).w};if((*it).y>y) vr=(node){y+1,(*it).y,(*it).w};long long vx=max(x,(*it).x),vy=min(y,(*it).y);ans=(ans-(vy-vx+1)%mod*gt(w-(*it).w-1)%mod+mod)%mod;v.erase(it);}int vt=it-v.begin();if(vr.w!=-1) v.insert(v.begin()+vt,vr);v.insert(v.begin()+vt,(node){x,y,w});if(vl.w!=-1) v.insert(v.begin()+vt,vl);
}
int main()
{
//	freopen("competition.in","r",stdin);
//	freopen("competition.out","w",stdout);scanf("%d%lld",&n,&m);ans=m%mod*gt(n)%mod;v.push_back((node){1,m,0});v.push_back((node){m+1,m+1,0});for(int i=1;i<=n;i++){long long x,y;scanf("%lld%lld",&x,&y);pt(x,y,i);}pt(1,m,n+1);ans=ans*mi(gt(n),mod-2)%mod;printf("%lld",ans);return 0;
}