蒟蒻的小窝

蒟蒻的小窝

题解 P3105 【[USACO14OPEN]Fair Photography S】

posted on 2020-08-15 19:54:54 | under 题解 |

我的想法很奇怪,将白牛标成 $-1$ ,斑点牛标成 $+1$ ,然后把所有的奇偶分开来做,再用 $RMQ$ 分别标记前面每个区间的最大值,找在前面的第一个大于当前位置的数,当前位置的最优解就是前面第一个大于当前位置的数的下标了,然后结果就是当前位置下标-找到位置下标 $+1$ ,容斥嘛,最后 $ans$ 刷一趟最大值就ok了。感觉这也是一种新解法。。。

Code:

#include<bits/stdc++.h>
using namespace std;
struct ZS{
    int x,y;
    bool operator <(const ZS b)const{return x<b.x;}
}c[1000005];
int n,ans,lena,lenb,m;
int s[1000005],a[500005][25],b[500005][25];
void make(int &L,int &R,int j,int x){
    if(L+(1<<j)-1<=R){
        if(a[L][j]>=s[x]){R=L+(1<<j)-1;return;}
        if(a[R-(1<<j)+1][j]>=s[x]){L=R-(1<<j)+1;return;}
    }
    else return;
    L=0;R=0;
}
int check(int x){
    int L=1,R=x/2;
    for(int j=15;j>=0;j--){
        make(L,R,j,x);
        if(!L&&!R)return -1;
    }
    return c[(L-1)*2+2].x;
}
void make_(int &L,int &R,int j,int x){
    if(L+(1<<j)-1<=R){
        if(b[L][j]>=s[x]){R=L+(1<<j)-1;return;}
        if(b[R-(1<<j)+1][j]>=s[x]){L=R-(1<<j)+1;return;}
    }
    else return;
    L=0;R=0;
}
int check_(int x){
    int L=1,R=x/2;
    for(int j=15;j>=0;j--){
        make_(L,R,j,x);
        if(!L&&!R)return -1;
    }
    return c[L*2-1].x;
}
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        c[i].x=read();char ch=getchar();
        if(ch=='W')c[i].y--;
        else c[i].y++;
    }
    sort(c+1,c+1+n);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+c[i].y;
    for(int i=1;i<=n;i+=2)if(i<=n)a[++lena][0]=s[i];
    b[++lenb][0]=0;for(int i=2;i<=n;i+=2)if(i<=n)b[++lenb][0]=s[i];
    for(int j=1;j<=15;j++)
        for(int i=1;i<=(n+1)/2;i++)if((1<<j)<=((n+1)/2-i+1))a[i][j]=max(a[i][j-1],a[i+(1<<j-1)][j-1]);
    for(int j=1;j<=15;j++)
        for(int i=1;i<=n/2;i++)if((1<<j)<=(n/2-i+1))b[i][j]=max(b[i][j-1],b[i+(1<<j-1)][j-1]);
    for(int i=3;i<=n;i+=2)if(i<=n){
        int x=check(i);
        if(x!=-1)ans=max(ans,c[i].x-x);
    }
    for(int i=2;i<=n;i+=2)if(i<=n){
        int x=check_(i);
        if(x!=-1)ans=max(ans,c[i].x-x);
    }
    printf("%d\n",ans);
    return 0;
}