四个小时T1硬是没想到双指针。只能说学啥就嗯对着啥输出。
T1
挺简单一个题。发现区间右端点向右的同时，左端点不向左，就可以用双指针。\(r\) 一直向右，如果当前区间不合法 \(l\) 也向右直到合法。
建一个权值线段树维护两个端点之间的区间的最长连续段（常规），然后每次给答案加上区间长度的贡献。
点击查看代码
#include<bits/stdc++.h>
typedef int count ;
typedef long long value;
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;
#define maxn 200010
count n,k;
value a[maxn],ans;
#define lc (hao<<1)
#define rc (hao<<1 | 1)
struct tree{
count l,r;
value lm,rm,maxx,cnt;
} shu[maxn<<2];
inline void pushup(count hao){
shu[hao].maxx=std::max({shu[lc].maxx,shu[rc].maxx,shu[lc].rm+shu[rc].lm});
shu[hao].lm=shu[lc].lm+(shu[lc].lm==shu[lc].r-shu[lc].l+1)*shu[rc].lm;
shu[hao].rm=shu[rc].rm+(shu[rc].rm==shu[rc].r-shu[rc].l+1)*shu[lc].rm;
}
void insert(count hao,count l,count r,count pos){
shu[hao].l=l,shu[hao].r=r;
if(l==r){
shu[hao].cnt++;
shu[hao].lm=shu[hao].rm=shu[hao].maxx=1;
return ;
}
count mid=(l+r)>>1;
if(pos<=mid) insert(lc,l,mid,pos);
else insert(rc,mid+1,r,pos);
pushup(hao);
}
void del(count hao,count pos){
if(shu[hao].l==shu[hao].r){
shu[hao].cnt--;
if(!shu[hao].cnt){
shu[hao].lm=shu[hao].rm=shu[hao].maxx=0;
}
return ;
}
count mid=(shu[hao].l+shu[hao].r)>>1;
if(pos<=mid) del(lc,pos);
else del(rc,pos);
pushup(hao);
}
tree ask(count hao,count l,count r){
if(shu[hao].l>=l && shu[hao].r<=r){
return shu[hao];
}
count mid=(shu[hao].l+shu[hao].r)>>1;
tree now={0,0,0,0,0,0};
if(l<=mid && r>mid){
tree le=ask(lc,l,r);
tree ri=ask(rc,l,r);
now.maxx=std::max({le.maxx,ri.maxx,le.rm+ri.lm});
now.lm=le.lm+(le.lm==le.r-le.l+1)*ri.lm;
now.rm=ri.rm+(ri.rm==ri.r-ri.l+1)*le.rm;
return now;
}
if(l<=mid){
return ask(lc,l,r);
}
return ask(rc,l,r);
}
int main(){
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
n=read(),k=read();
for(count i=1;i<=n;i++){
a[i]=read();
}
for(count l=1,r=1;r<=n;r++){
insert(1,1,n,a[r]);
while(ask(1,1,n).maxx>k){
del(1,a[l]);
l++;
}
ans+=r-l+1;
}
write(ans),putchar('\n');
return 0;
}
T2 差后队列
咱也不知道这个名字是啥含义。
赛时读了读发现是概率期望就直接跳了。好吧其实也没啥时间做了，T1之外的题我总共投入了不到15min的时间。
每次弹空都只是
发现弹数大小还是比较好维护的。先把最大值挑出来，不考虑弹出，剩下的就直接维护当前所有元素的平均值。弹出的时候相当于均匀减少了，乘上 \(\dfrac{cnt-1}{cnt}\)，\(cnt\) 为删前总数。
对于弹出时间不太好维护，对于期望，比较直接的，最大值一定最后弹出；其他的值都是在进入后到弹空前都有可能弹出。可以直接倒着扫一遍，记录一个 \(now\) 表示可能时间的总和。
这里有种特殊情况，就是原本一个数是最大值，又来了一个更大的，这就把原本这个顶掉了，后面的时间就应该记上。
可以整一个 \(nx\) 数组，找前一个前缀最大值，每次扫到后面的最大值就直接在上面改就好，非常方便。
最后一个问题。他可能pop操作不能排空。这时候就虚空加一堆1。上面操作完就直接操作这一步就好。这一步和上面大同小异，但是因为原本的右端点都能确定，所以最大值不用遍历到,直接修改就行。这时候我们不好知道最后一个时间是多少，就直接遍历完整区间。
一开始感觉太难了，理解了……也就那样
点击查看代码
#include<bits/stdc++.h>
typedef long long count ;
typedef long long value ;
#define int long long
inline value read(){
count f(1);
value x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
void write(value x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
#define debug(x) std::cout<<"###"<<x<<std::endl;
#define mod 998244353
#define maxn 1000010
count n,duan,cnt;
inline value kuai(value base,value x){
value val=1;
while(x){
if(x&1) val=val*base%mod;
base=base*base%mod;
x>>=1;
}
return val;
}
count nx[maxn];
value ans[maxn];
struct cun{
count op;
value val;
} a[maxn];
inline void jie(count l,count r){
count ma=l,sum=0;
value tot=0;
for(count i=l+1;i<r;i++){
if(a[i].op==0){
if(a[ma].val<a[i].val){
tot=(tot+a[ma].val)%mod;
nx[i]=ma;
ma=i;
}else{
tot=(tot+a[i].val)%mod;
}
sum++;
}else{
value ni=kuai(sum,mod-2);
ans[i]=tot*ni%mod;
tot=(tot*(sum-1)%mod*ni)%mod;
sum--;
}
}
ans[r]=a[ma].val;
ans[ma]=r;
sum=0;
tot=0;
for(count i=r-1;i>=l;i--){
if(a[i].op==1){
sum++;
tot=(tot+i)%mod;
}else{
if(a[nx[i]].val==a[ma].val) continue;
value ni=kuai(sum,mod-2);
ans[nx[i]]=(ans[nx[i]]+tot*ni%mod)%mod;
//不是最大值但原本被当做最大值，没算上贡献，现在补上
tot=(tot*(sum-1)%mod*ni)%mod;
sum--;
}
}
}
inline void jie2(count l,count r){
if(l>r) return ;
count ma=l,sum=0;
value tot=0;
count cnt=1;
for(count i=l+1;i<=r;i++){
if(a[i].op==0){
if(a[ma].val<a[i].val){
tot=(tot+a[ma].val)%mod;
nx[i]=ma;
ma=i;
}else{
tot=(tot+a[i].val)%mod;
}
sum++;
cnt++;
}else{
value ni=kuai(sum,mod-2);
ans[i]=tot*ni%mod;
tot=(tot*(sum-1)%mod*ni)%mod;
sum--;
}
}
cnt=(cnt-(r-l+1-cnt));
sum=cnt-1;
tot=0;
for(count i=r;i>=l;i--){
if(a[i].op==1){
sum++;
tot=(tot+i)%mod;
}else{
if(a[nx[i]].val==a[ma].val) continue;
value ni=kuai(sum,mod-2);
ans[nx[i]]=(ans[nx[i]]+tot*ni%mod)%mod;
tot=(tot*(sum-1)%mod*ni)%mod;
sum--;
}
}
}
main(){
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
n=read();
duan=1;
// iota(nx+1,nx+1+n,1);
for(count i=1;i<=n;i++){
a[i].op=read();
if(!a[i].op){
a[i].val=read();
cnt++;
}else{
cnt--;
}
if(!cnt){
jie(duan,i);
duan=i+1;
}
}
jie2(duan,n);
for(count i=1;i<=n;i++){
write(ans[i]),putchar(' ');
}
return 0;
}