[COCI2010-2011#7] UPIT 分块

· · 题解

[COCI2010-2011#7] UPIT 分块

题目链接：COCI2010-2011#7

​ 比较常规的分块维护信息的题目。

​ 对于操作一，简单的区间覆盖。

​ 对于操作二。散块的话暴力修改。整块中增加的值构成一个等差数列，所以整块区间和可以通过等差数列公式进行维护。然后再开两个数组记录这块左端点增加的值和等差数列的差值，这样我们如果查询散块时下传标记可以用这两个数组更新。

​ 对于操作二的整块修改及下传标记的局部代码如下：

void remake(int k)
{
    ll d=num[k];
    for(Re int i=0;i<vec[k].size();++i)
    {
        if(tag[k]) vec[k][i]=tag[k];//人为规定覆盖的标记优先级较大，类似于乘法标记和加法标记的关系。
        vec[k][i]+=d;
        d+=add[k];
    }
    add[k]=num[k]=tag[k]=0;
}
//---分割线---
//下面是一个不完整的函数，用来更新整块
for(Re int i=le+1;i<ri;++i)
    {
        add[i]+=x;num[i]+=x*(tot+1);//（tot+1）*x为这个块左端增加的值，求法可见完整代码
        sum[i]+=x*(tot*2ll+1+vec[i].size())*vec[i].size()/2;
        tot+=vec[i].size();
    }

​ 对于操作三，可能是一个重头戏，这也是为什么我们选择分块的原因。我们可以每块维护一个 \text{vector}，插入直接在位置所在块的 \text{vector} 中插入，由于一个块长为 O(\sqrt{n})，所以插入操作也是 O(\sqrt{n}) 的。但是我们知道，如果数据重复插入一个块，我们这种做法会导致某一个块长长度过大从而使得我们分块的时间复杂度退化。所以我们可以在某一块的长度大于 2\times\sqrt{n} 的时候重构整个数组。重构一次复杂度是 O(n) 。但是由于起码插入 \sqrt{n} 个数之后才会重构一次整个数组，所以我们的时间复杂度仍旧是 O(n\times\sqrt{n})。

​ 重构整个数组的局部代码如下：

void rebuild()
{
    int tot=0,len=sqrt(n);
    for(Re int i=1;tot<n;++i)
    {
        remake(i);
        for(Re int j=0;j<vec[i].size();++j)
            a[++tot]=vec[i][j];
        vec[i].clear();
        tag[i]=add[i]=sum[i]=num[i]=0;
    }
    for(Re int i=1;i<=tot;++i)
    {
        vec[(i-1)/len+1].push_back(a[i]);
        sum[(i-1)/len+1]+=a[i];
    }
}

​ 操作四是一个简单的区间和查询，算是分块的基本操作。如上文所说，散块暴力，顺便维护整块的和就可以在 O(\sqrt{n}) 的时间内查询出答案。

​ 值得注意的是，这题由于我们使用 \text{vector} 封装一个整块，而且题目中也有插入操作。所以在获取左右端点 l,r 所在块的编号中不能通过预处理然后 O(1) 获取。所以我们遍历每一个块进行获取，这个操作也是 O(\sqrt{n}) 的复杂度，并不会超时。

​ 那么综上所述，时间复杂度就为 O(n\times \sqrt{n})。

​ 全部代码如下：

#pragma GCC optimize(2) 
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline-small-functions")
//观察可知这题是要我们写一个数据结构
//观察可知，操作一是区间修改，操作二是区间修改，操作三是插入，操作四是区间查询 
//所以有一个结论。如果 a+b==a+b那么a+b==a+b。
//我们可以用这个结论维护分块。 
//然后再用分块维护答案。 
//O(FAST)的分块/se 
#include<bits/stdc++.h>
#define ll long long
#define Re register
using namespace std;
const int MAXN = 1e5+5;
int n,q;
ll a[MAXN<<1],tag[MAXN],add[MAXN],num[MAXN],sum[MAXN];
vector <ll> vec[MAXN];
void Make_Group()
{
    int len=sqrt(n);
    for(Re int i=1;i<=n;++i)
    {
        vec[(i-1)/len+1].push_back(a[i]);
        sum[(i-1)/len+1]+=a[i];
    }
}
void remake(int k)
{
    ll d=num[k];
    for(Re int i=0;i<vec[k].size();++i)
    {
        if(tag[k]) vec[k][i]=tag[k];
        vec[k][i]+=d;
        d+=add[k];
    }
    add[k]=num[k]=tag[k]=0;
}
void rebuild()
{
    int tot=0,len=sqrt(n);
    for(Re int i=1;tot<n;++i)
    {
        remake(i);
        for(Re int j=0;j<vec[i].size();++j)
            a[++tot]=vec[i][j];
        vec[i].clear();
        tag[i]=add[i]=sum[i]=num[i]=0;
    }
    for(Re int i=1;i<=tot;++i)
    {
        vec[(i-1)/len+1].push_back(a[i]);
        sum[(i-1)/len+1]+=a[i];
    }
}
void modify(int l,int r,ll x)
{
    int tot=0,le,ri,L,R;
    for(Re int i=1;tot<n;++i)
    {
        if(tot+vec[i].size()>=l&&tot<l) le=i,L=l-tot-1;
        if(tot+vec[i].size()>=r&&tot<r) ri=i,R=r-tot-1;
        tot+=vec[i].size();
    }
    if(le==ri)
    {
        remake(le);
        for(Re int i=L;i<=R;++i)
        {
            sum[le]+=x-vec[le][i];
            vec[le][i]=x;
        }
    }
    else
    {
        for(Re int i=le+1;i<ri;++i)
        {
            add[i]=0;num[i]=0;
            sum[i]=1ll*vec[i].size()*x;
            tag[i]=x;
        }
        remake(le);remake(ri);
        for(Re int i=L;i<vec[le].size();++i)
            sum[le]+=x-vec[le][i],vec[le][i]=x;
        for(Re int i=0;i<=R;++i)
            sum[ri]+=x-vec[ri][i],vec[ri][i]=x;
    }
}
void upd(int l,int r,ll x)
{
    int tot=0,le,ri,L,R,tmp=0;
    for(Re int i=1;tot<n;++i)
    {
        if(tot+vec[i].size()>=l&&tot<l) le=i,L=l-tot-1;
        if(tot+vec[i].size()>=r&&tot<r) ri=i,R=r-tot-1;
        tot+=vec[i].size();
    }
    tot=vec[le].size()-L;
    if(le==ri)
    {
        remake(le);
        for(Re int i=L;i<=R;++i)
            vec[le][i]+=x*(i-L+1),sum[le]+=x*(i-L+1);
    }
    else
    {
        for(Re int i=le+1;i<ri;++i)
        {
            add[i]+=x;num[i]+=x*(tot+1);
            sum[i]+=x*(tot*2ll+1+vec[i].size())*vec[i].size()/2;
            tot+=vec[i].size();
        }
        remake(le);remake(ri);
        for(Re int i=L;i<vec[le].size();++i)
            vec[le][i]+=x*(i-L+1),sum[le]+=x*(i-L+1);
        for(Re int i=0;i<=R;++i)
            vec[ri][i]+=x*(tot+i+1),sum[ri]+=x*(tot+i+1);
    }
}
void insert(int pos,ll x)
{
    for(Re int i=1;pos;++i)
    {
        if(!vec[i].size())
        {
            vec[i].push_back(x);
            sum[i]+=x;
            break;
        }
        if(pos<=vec[i].size())
        {
            remake(i);
            vector<ll>::iterator it=vec[i].begin()+pos-1;
            vec[i].insert(it,x);
            sum[i]+=x;
            if(vec[i].size()>2*sqrt(n)) rebuild();
            break; 
        }
        pos-=vec[i].size();
    }
}
ll query(int l,int r)
{
    int tot=0,le,ri,L,R;
    for(Re int i=1;tot<n;++i)
    {
        if(tot+vec[i].size()>=l&&tot<l) le=i,L=l-tot-1;
        if(tot+vec[i].size()>=r&&tot<r) ri=i,R=r-tot-1;
        tot+=vec[i].size();
    }
    ll ans=0;
    if(le==ri)
    {
        remake(le);
        for(Re int i=L;i<=R;++i)
            ans+=vec[le][i];
    }
    else
    {
        for(Re int i=le+1;i<ri;++i)
            ans+=sum[i];
        remake(le);remake(ri);
        for(Re int i=L;i<vec[le].size();++i)
            ans+=vec[le][i];
        for(Re int i=0;i<=R;++i)
            ans+=vec[ri][i];
    }
    return ans;
}
int main()
{
    scanf("%d %d",&n,&q);
    for(Re int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    Make_Group();
    while(q--)
    {
        int opt,a,b,c;ll x;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d %d %lld",&a,&b,&x);
            modify(a,b,x);
        }
        else if(opt==2)
        {
            scanf("%d %d %lld",&a,&b,&x);
            upd(a,b,x);
        }
        else if(opt==3)
        {
            scanf("%d %lld",&c,&x);
            insert(c,x);
            ++n;
        }
        else
        {
            scanf("%d %d",&a,&b);
            printf("%lld\n",query(a,b));
        }
    }
    return 0;
}