有点像JRY的那道序列题,大概是统计题的经典套路?
先说无修改的:将白奶牛记为$-1$,花奶牛记为$1$,然后做前缀和统计某个前缀和$sum$第一次出现的位置,之后再出现就统计答案。对于修改(将$-1$改成$1$),即是令某个前缀和$sum$的$sum+2k(k∈N)$的所有位置同样可以更新,对这些位置再都取一次$min$即可
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=100005; 6 struct a{int val,pos;}cow[N]; 7 int firs[2*N],n,tot,ans; 8 char rd[2]; 9 bool cmp(a x,a y) 10 { 11 return x.pos<y.pos; 12 } 13 int main () 14 { 15 scanf("%d",&n); 16 for(int i=1;i<=n;i++) 17 { 18 scanf("%d%s",&cow[i].pos,rd); 19 cow[i].val=(rd[0]=='W')?-1:1; 20 } 21 sort(cow+1,cow+1+n,cmp); 22 memset(firs,0x3f,sizeof firs); 23 firs[tot=n]=cow[1].pos; 24 for(int i=1;i<n;i++) 25 tot+=cow[i].val,firs[tot]=min(firs[tot],cow[i+1].pos); 26 for(int i=2*n;~i;i--) 27 firs[i]=min(firs[i],firs[i+2]); tot=n; 28 for(int i=1;i<=n;i++) 29 tot+=cow[i].val,ans=max(ans,cow[i].pos-firs[tot]); 30 printf("%d",ans); 31 return 0; 32 }