P4684 [IOI2008]Fish（组合数学）

传送门

组合数学好题

时间复杂度$O(FlogF)$
code:

#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int const N=5e5+1;
struct fish{
    int len,col,pre;
    friend bool operator <(fish x, fish y){
        return x.len<y.len;
    }
}f[N];
int n,m,p,t[N*8],h[N],last[N],w[N],q[N],now[N],v[N],ans;
void add(int pos, int l, int r, int x){
    if (l==r){ 
        t[x]=(v[pos]+1) % p;
        return;
    }
    int mid=((l+r)>>1);
    if (pos<=mid) add(pos,l,mid,x*2);
    if (pos>mid) add(pos,mid+1,r,x*2+1);
    t[x]=(t[x*2]*t[x*2+1]) % p;
}
int ask(int a, int b, int l, int r, int x){
    if (a>b) return 1;
    if (a<=l && r<=b) return t[x];
    int ans=1,mid=((l+r)>>1);
    if (a<=mid) ans=ans*ask(a,b,l,mid,x*2);
    if (b>mid) ans=ans*ask(a,b,mid+1,r,x*2+1);
    return ans % p;
}
int find(int x){
    int l=1,r=m;
    while (r-l>1){
        int mid=((l+r)>>1);
        if (f[w[mid]].len>=x) r=mid; else l=mid+1;
    }
    if (f[w[l]].len>=x) return l;
    if (f[w[r]].len>=x) return r;
    return m+1;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for (int i=1;i<=n;i++)
        cin>>f[i].len>>f[i].col;
    sort(f+1,f+n+1);
    for (int i=n;i>=1;i--){
        if (!h[f[i].col]) h[f[i].col]=i;
        f[i].pre=last[f[i].col];
        last[f[i].col]=i;
    }
    m=0;
    for (int i=1;i<=n;i++)
        if (h[f[i].col]==i) w[q[f[i].col]=++m]=i;
    for (int i=1;i<=8*m;i++)
        t[i]=1;
    for (int i=1,j=1;i<=m;i++){
        while (f[j].len*2<=f[w[i]].len){
            int s=f[j].col;
            v[q[s]]++;
            now[s]=j++;
            add(q[s],1,m,1);
        }
        int k,d=ask(1,i-1,1,m,1);
        if (!now[f[w[i]].col]) k=last[f[w[i]].col]; else k=f[now[f[w[i]].col]].pre;
        if (!k) k=m+1; else k=find(f[k].len*2);
        ans=(ans+d*ask(i+1,k-1,1,m,1)+d*(v[i] % p)) % p;
    }
    cout<<ans<<endl; 
    return 0;
}