【Ynoi2019】魔法少女网站

Author Avatar
mrsrz 6月 02, 2020

操作分块，分块套链表。

题目大意：

给定一个序列，你要支持：

  1. 单点修改。
  2. 给定区间 $[l,r]$ 和 $x$，问有多少子区间的最大值小于等于 $x$。

题解：

去年写的东西现在啥都不会了

第十分块。

这题是个操作分块套序列分块。正解复杂度为 $O(n\sqrt n)$（$n$ 与 $m$ 同阶），所以分析时块大小默认为 $\sqrt n$。实际取值时要考虑常数因子的影响。

操作分块，即把每 $\sqrt n$ 次操作一起处理。这些操作中，有 $O(\sqrt n)$ 次修改和 $O(\sqrt n)$ 次查询。

对询问，按照 $x$ 从小到大排序。维护一个 01 序列表示每个位置是否小于等于 $x$。每次把新的符合条件的位置改成 $1$。不考虑排序，这里总复杂度 $O(n)$。

对于那些修改操作，一个显然的套路就是插入后按顺序撤销。

我们需要设计这样一个数据结构，支持 $O(1)$ 把一个位置的 0 变成 1，$O(\sqrt n)$ 查询一段区间的极长连续 1 区间长度的平方和（与平方有关的信息）。还要支持 $O(1)$ 按顺序撤销。

序列分块。考虑对每个极长连续 1 区间，在开头处记录其结尾位置，在结尾记录其开头位置。则新插入一个 0 的时候，可以 $O(1)$ 将这个点的左右（如果存在）进行合并。再用一个数组记录一下各个块的答案即可。

对于撤销操作，由于每次插入只影响了两个点的值，所以记录下原来的值及其位置，询问结束后暴力还原即可。

查询的时候，我们记录当前极长连续 1 区间的左端点，边角扫描，对于整块，可以直接通过维护的值来得出这个块的前缀 1 区间长度和后缀 1 区间长度。将其前缀与之前的左端点计算贡献，新的左端点即为后缀的那个点。然后中间的部分，通过记录的块内答案减去两边要和其他块计算答案的部分的贡献即可。

这样就做到了每块操作 $O(n)$ 处理，则总时间复杂度 $O(n\sqrt n)$。

记得卡卡常。

Code：

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<utility>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const ULL WR=(1ULL<<32)-1,WL=WR<<32;
#define bel(x)((x-1)/siz+1)
const int siz=1024,N=3e5+5;
char buf[(int)1e8],*ss=buf;
char bwf[(int)3e7],*ww=bwf;
inline int init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';fclose(stdin);return 0;}
inline void write(LL x){if(x<10)*ww++=x^'0';else write(x/10),*ww++=x%10^'0';}
const int __START__=init();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
int n,m,a[N],L[560],R[560],blocks;
ULL b[N],Left[N],Right[N],tL,tR;
bool vis[N],val[N];
struct que{
    int l,r,x,id;
    inline int operator<(const que&rhs)const{return x<rhs.x;}
}vq[2005];
struct mdf{
    int x,y,tim;
}vm[2005];
int tvq; 
int tvm;
int ppos[N],tp;
ULL d[N];
int S[560],ps[560];
LL ans[N];
inline LL calc(int x){return(x+1LL)*x>>1;}
int mff[N];
void solve(){
    sort(vq+1,vq+tvq+1);
    memset(d,0,sizeof d),memset(val,0,sizeof val);
    memset(S,0,sizeof S);
    tp=0;
    for(int i=1;i<=tvm;++i)if(!vis[vm[i].x])vis[ppos[++tp]=vm[i].x]=1;
    int it=1;
    for(int I=1;I<=tvq;++I){
        const que&q=vq[I];
        while(it<=n&&q.x>=b[it]>>32){
            const int pos=(int)b[it];
            if(!vis[pos]){
                val[pos]=1;
                if(pos!=L[bel(pos)]&&val[pos-1]&&pos!=R[bel(pos)]&&val[pos+1]){
                    int ld=d[pos-1]>>32,rd=(int)d[pos+1];
                    (d[ld]&=WL)|=rd,(d[rd]&=WR)|=(ULL)ld<<32;
                    S[bel(ld)]+=(pos-ld+1)*(rd-pos+1);
                }else
                if(pos!=L[bel(pos)]&&val[pos-1]){
                    int ld=d[pos-1]>>32;
                    (d[pos]&=WR)|=(ULL)ld<<32,(d[ld]&=WL)|=pos,S[bel(ld)]+=pos-ld+1;
                }else
                if(pos!=R[bel(pos)]&&val[pos+1]){
                    int rd=(int)d[pos+1];
                    (d[pos]&=WL)|=rd,(d[rd]&=WR)|=(ULL)pos<<32,S[bel(rd)]+=rd-pos+1;
                }else d[pos]=(ULL)pos<<32|pos,++S[bel(pos)];
            }
            ++it;
        }
        memcpy(ps,S,sizeof S);
        for(int i=1;i<=tp;++i)mff[ppos[i]]=a[ppos[i]]<=q.x;
        for(int f=1;f<=tvm;++f)
        if(vm[f].tim<=q.id)mff[vm[f].x]=vm[f].y<=q.x;else break;
        static pair<ULL,int>sta[N];int top=0;
        for(int i=1;i<=tp;++i){
            const int pos=ppos[i];
            if(mff[pos]){
                val[pos]=1;
                if(pos!=L[bel(pos)]&&val[pos-1]&&pos!=R[bel(pos)]&&val[pos+1]){
                    int ld=d[pos-1]>>32,rd=(int)d[pos+1];
                    sta[++top]=make_pair(d[ld],ld),sta[++top]=make_pair(d[rd],rd);
                    (d[ld]&=WL)|=rd,(d[rd]&=WR)|=(ULL)ld<<32;
                    S[bel(ld)]+=(pos-ld+1)*(rd-pos+1);
                }else
                if(pos!=L[bel(pos)]&&val[pos-1]){
                    int ld=d[pos-1]>>32;
                    sta[++top]=make_pair(d[ld],ld),sta[++top]=make_pair(d[pos],pos);
                    (d[pos]&=WR)|=(ULL)ld<<32,(d[ld]&=WL)|=pos,S[bel(ld)]+=pos-ld+1;
                }else
                if(pos!=R[bel(pos)]&&val[pos+1]){
                    int rd=(int)d[pos+1];
                    sta[++top]=make_pair(d[pos],pos),sta[++top]=make_pair(d[rd],rd);
                    (d[pos]&=WL)|=rd,(d[rd]&=WR)|=(ULL)pos<<32,S[bel(rd)]+=rd-pos+1;
                }else sta[++top]=make_pair(d[pos],pos),d[pos]=(ULL)pos<<32|pos,++S[bel(pos)];
            }
        }
        const int bL=bel(q.l),bR=bel(q.r);
        LL&ans=::ans[q.id];
        if(bL==bR){
            int pr=q.l;
            for(int i=q.l;i<=q.r;++i)
            if(!val[i])ans+=calc(i-pr),pr=i+1;
            ans+=calc(q.r-pr+1);
        }else{
            int pr=q.l;
            for(int i=q.l;i<=R[bL];++i)
            if(!val[i])ans+=calc(i-pr),pr=i+1;
            for(int i=bL+1;i<bR;++i)
            if((int)d[L[i]]<R[i]){
                int fst=(int)d[L[i]]?(int)d[L[i]]+1:L[i],lst=(d[R[i]]>>32)?(d[R[i]]>>32)-1:R[i];
                ans+=S[i]+calc(fst-pr)-(calc(fst-L[i])+calc(R[i]-lst));
                pr=lst+1;
            }
            for(int i=L[bR];i<=q.r;++i)
            if(!val[i])ans+=calc(i-pr),pr=i+1;
            ans+=calc(q.r-pr+1);
        }
        for(int i=1;i<=tp;++i)val[ppos[i]]=mff[ppos[i]]=0;
        for(int i=top;i;--i)d[sta[i].second]=sta[i].first;
        memcpy(S,ps,sizeof S);
    }
    tL=tR=0;
    for(int i=1;i<=tvm;++i)a[vm[i].x]=vm[i].y;
    for(int i=1;i<=n;++i)
    if(!vis[(int)b[i]])Left[tL++]=b[i];else Right[tR++]=(ULL)a[(int)b[i]]<<32|((int)b[i]);
    for(int i=1;i<=tvm;++i)vis[vm[i].x]=0;
    sort(Right,Right+tR);
    int l1=0,l2=0,l3=0;
    while(l1!=tL&&l2!=tR)
    if(Left[l1]<Right[l2])b[++l3]=Left[l1++];else b[++l3]=Right[l2++];
    while(l1!=tL)b[++l3]=Left[l1++];
    while(l2!=tR)b[++l3]=Right[l2++];
}
int main(){
    n=readint(),m=readint();
    for(int i=1;i<=n;++i)b[i]=(ULL)(a[i]=readint())<<32|i;
    sort(b+1,b+n+1);
    blocks=bel(n);
    for(int i=1;i<=blocks;++i)L[i]=R[i-1]+1,R[i]=i*siz;R[blocks]=n;
    for(int i=1;i<=m;++i){
        int op=readint();
        if(op==1){
            int x=readint(),y=readint();
            vm[++tvm]=(mdf){x,y,i};
            ans[i]=-1;
        }else{
            int l=readint(),r=readint(),x=readint();
            vq[++tvq]=(que){l,r,x,i};
        }
        if(i%1024==0)solve(),tvq=tvm=0;
    }
    if(m%1024)solve();
    for(int i=1;i<=m;++i)if(ans[i]!=-1)write(ans[i]),*ww++='\n';
    fwrite(bwf,1,ww-bwf,stdout);
    return 0;
}
Powered by Hexo
Theme - Material