NC21666. qko的烦恼
描述
输入描述
输入两个整数n(1<=n<=1000000),m(1<=m<=1000000),接下来输出m个区间[l,r],表示每次操作的区间,并且(1<=l<=r<=n)
输出描述
输出一个数 表示每次操作后剩余白色节点的乘积在模1e9+7下的答案
示例1
输入:
10 3 3 3 5 7 2 8
输出:
162
C++11(clang++ 3.9) 解法, 执行用时: 232ms, 内存消耗: 19944K, 提交时间: 2020-03-26 14:15:28
#include<stdio.h>
#define ll long long
const int mod=1e9+7;
const int N=1e6+1;
int s[N];
int cal(int x)
{
if(s[x]==x) return s[x];
return s[x]=cal(s[x]);
}
int main()
{
int n,l,r;
int t;
ll ans=1;
scanf("%d %d",&n,&t);
for(int i=1;i<=n+1;i++)
s[i]=i;
while(t--)
{
int l,r;
scanf("%d %d",&l,&r);
for(int i=cal(l);i<=r;i=cal(i+1))
{
s[i]=i+1;
n--;
}
ans=ans*n%mod;
}
printf("%lld\n",ans);
}