vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 CF1461C 【Random Events】

posted on 2020-12-12 10:21:54 | under 题解 |

由于影响的总是某段前缀,因此当多个事件同时发生时,它的效果与 $r$ 最大的那个事件的效果是相同的。也就是说最终得到的序列是否满足要求只与单个事件有关,我们只需要求出那些发生后能使原排列升序的事件,它们中只要有一个事件发生就能满足要求,概率为 1-这些事件均不发生的概率。

判断事件 $i$ 发生后能否使排列升序也很简单,只需要满足两个条件: $[r_{i}+1,n]$ 本来就有序,且 $max[1,r_{i}]\le a_{r_{i}+1}$。前一个条件需要先求出最长的升序的后缀,后一个条件则需要预处理出前缀最大值。

注意,如果原排列已经有序,需要输出 $1$。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define db double
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=1e5+5;
int a[N],r[N],pre[N];
db p[N];

void work(){
    int n=read(),m=read(),len=0;
    db ans=1.0;
    fo(i,1,n) a[i]=read(),pre[i]=max(pre[i-1],a[i]);
    fo(i,1,m) r[i]=read(),cin>>p[i];
    a[n+1]=2e9;
    while(len<n&&a[n-len]<=a[n-len+1]) len++;
    //cout<<"len="<<len<<endl;
    if(len==n){
        puts("1.0000000");
        return;
    }
    fo(i,1,m) if(n-r[i]+1<=len&&pre[r[i]]<=a[r[i]+1]) ans*=(1.0-p[i]);
    printf("%.7lf\n",1-ans);
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}