NC201976. 小L扔垃圾
描述
输入描述
一行 n 表示有几个人来扔垃圾。
一行一个字符串表示这一堆垃圾的情况，W 表示湿垃圾，D 表示干垃圾，R 表示
可回收垃圾。
接下来 n 行每行有 p，z，p==1 时表示放前面，p==2 表示放后面，z 表示什么类
型的垃圾。
输出描述
一共 n+1 行，第一行为一开始没人扔垃圾时的答案。
接下来 n 行表示每一个人扔完垃圾后的答案。
示例1
输入:
3 RWWWDD 2 W 1 D 1 D
输出:
4 4 7 9
说明:
C++(g++ 7.5.0) 解法, 执行用时: 1927ms, 内存消耗: 39432K, 提交时间: 2022-12-11 00:40:23
#include<bits/stdc++.h>
using namespace std;
int rsum=0,lsum=0;
int ans=0;
const int B=2000000;
const int N=2010000;
int ls[N*2],rs[N*2];
int l,r=-1;
void radd(int x)
{
rsum+=x;
r++;
ans=max(ans,r-ls[rsum+B]);
rs[rsum+B]=max(rs[rsum+B],r);
ls[rsum+B]=min(ls[rsum+B],r);
}
void ladd(int x)
{
lsum+=x;
l--;
ans=max(ans,rs[lsum+B]-l);
rs[lsum+B]=max(rs[lsum+B],l);
ls[lsum+B]=min(ls[lsum+B],l);
}
int main()
{
int n;
cin>>n;
string s;
cin>>s;
memset(ls,0x3f,sizeof ls);
memset(rs,-0x3f,sizeof rs);
radd(0);
for(int i=0;i<s.size();i++)
{
if(s[i]=='W')
{
radd(-1);
}
else if(s[i]=='D')
{
radd(1);
}
else
radd(0);
}
cout<<ans<<endl;
for(int i=0;i<n;i++)
{
int p;
char op[2];
cin>>p>>op;
if(p==1)
{
if(op[0]=='W')
{
ladd(1);
}
else if(op[0]=='D')
ladd(-1);
else
ladd(0);
}
else
{
if(op[0]=='W')
{
radd(-1);
}
else if(op[0]=='D')
radd(1);
else
radd(0);
}
cout<<ans<<endl;
}
}
C++11(clang++ 3.9) 解法, 执行用时: 431ms, 内存消耗: 88560K, 提交时间: 2020-05-02 20:32:28
#include<bits/stdc++.h>
using namespace std;
const int N=2000010;
int n,len;
char s[N];
int p[N],sum[N<<1],a[N<<2],b[N<<2],f[N<<1];
int get_num(char x){
if(x=='W') return -1;
else if(x=='D') return 1;
else return 0;
}
void min_up(int&x,int y){x=min(x,y);}
void max_up(int&x,int y){x=max(x,y);}
int main(){
scanf("%d",&n);
scanf("%s",s+1);len=strlen(s+1);
int l=2000001,r=2000000;
for(int i=1;i<=len;i++) p[i]=2,f[++r]=get_num(s[i]);
for(int i=1;i<=n;i++){
scanf("%d %s",&p[i+len],s);
if(p[i+len]==1) f[--l]=get_num(s[0]);
else f[++r]=get_num(s[0]);
}
sum[l-1]=2000000;for(int i=l;i<=r;i++) sum[i]=sum[i-1]+f[i];
int ans=0,now,T;l=2000001,r=2000000;
memset(a,63,sizeof(a));memset(b,-1,sizeof(b));
for(int i=1;i<=n+len;i++){
if(p[i]==1) now=--l;else now=++r;
min_up(a[sum[now-1]],now-1),max_up(b[sum[now]],now);
max_up(ans,now-a[sum[now]]),max_up(ans,b[sum[now-1]]-now+1);
if(i>=len) printf("%d\n",ans);
}
}