[Solution] P6707 [COCI 2010/2011 #7] UPIT

cherry2010 · 2025-04-25 15:30:58 · 题解

分块。

将不同操作分开分析，每个操作都是分块的一个经典应用。

• 操作一：区间赋值。

  • 对整块打赋值标记，散块暴力处理。

• 操作二：区间加等差数列。

  • 考虑到相邻位置增量差值相同，考虑差分，对整块打两个标记，分别表示当前块第一个元素应该增加的数和等差数列的公差。第一个标记也相当于是等差数列的首项。散块暴力处理。
  • 等差数列的懒标记也可以累加。

• 操作三：单点插入。

  • 使用 vector 的插入操作处理。由于这个操作的时间复杂度是 O(n) 的，所以需要使用定期重构来保证时间复杂度。
  • 具体的，当一个块的大小超过某个范围时，就需要将这个块拆分。为方便实现，直接将整个序列重新分块。
  • 因为每个 vector 的大小不同且不断地在更新，所以不能用数组记录每个点对应的块，而是在需要时重新找到对应的块和块内的对应位置。

• 操作四：区间求和。

  • 维护整块的块内元素总和，散块暴力处理。

• 时间复杂度 O(n\sqrt n)。

• 代码细节还是很多的，下面总结一些容易出错的点。

  • 空间需要开两倍。
  • vector 的下标是从 0 开始的，如果嫌不舒服也可以在最初重构的时候在下标 0 的位置插入一个占位置的数。
  • 赋值标记需要初始化为 -1。虽然实测测试点中并没有赋值为 0 的操作，赋值为 0 也可以通过。
  • 重构、修改散块、查询散块操作之前都需要先处理对应块的懒标记。
  • 赋值操作会覆盖加法操作，整块打赋值操作标记的时候需要将加等差数列的懒标记清空。
  • 在单点插入时也需要更新块内元素总和。

参考代码如下。

#include <bits/stdc++.h> //分块 
using namespace std;

namespace Cherry {
    const int N=2e5+10;
    int n,q,B,cnt;
    long long a[N],sum[N],cov[N],al[N],ad[N];
    vector<long long> p[N];

    pair<int,int> get_block(int x) { //找到x对应的块和块内位置 
        int cur=1;
        while(cur<=cnt&&(int)p[cur].size()<x) x-=p[cur++].size();
        return make_pair(cur,x-1); //注意vector从0开始 
    }
    void reset(int x) { //处理块内的tag 
        if(cov[x]!=-1) {
            for(int i=0;i<(int)p[x].size();i++) p[x][i]=cov[x];
            cov[x]=-1;
        }
        if(al[x]||ad[x]) {
            for(int i=0;i<(int)p[x].size();i++) p[x][i]+=al[x]+i*ad[x];
            al[x]=ad[x]=0;
        }
    }
    void rebuild() { //重构 
        n=0;
        for(int i=1;i<=cnt;i++) {
            reset(i);
            for(auto j:p[i]) a[++n]=j;
            p[i].clear();
        }
        B=sqrt(n),cnt=(n-1)/B+1;
        for(int i=1;i<=cnt;i++) sum[i]=al[i]=ad[i]=0,cov[i]=-1;
        for(int i=1;i<=n;i++) sum[(i-1)/B+1]+=a[i],p[(i-1)/B+1].push_back(a[i]);
    }
    void change1(int l,int r,long long x) { //区间赋值 
        auto L=get_block(l),R=get_block(r);
        int bl=L.first,pl=L.second,br=R.first,pr=R.second;
        if(bl==br) {
            reset(bl);
            for(int i=pl;i<=pr;i++) sum[bl]+=x-p[bl][i],p[bl][i]=x;
            return;
        }
        reset(bl),reset(br);
        for(int i=pl;i<(int)p[bl].size();i++) sum[bl]+=x-p[bl][i],p[bl][i]=x;
        for(int i=0;i<=pr;i++) sum[br]+=x-p[br][i],p[br][i]=x;
        for(int i=bl+1;i<=br-1;i++) sum[i]=p[i].size()*x,cov[i]=x,al[i]=ad[i]=0; //注意等差数列加法标记会清空 
    }
    void change2(int l,int r,long long x) { //区间加等差数列 
        auto L=get_block(l),R=get_block(r);
        int bl=L.first,pl=L.second,br=R.first,pr=R.second;
        if(bl==br) {
            reset(bl);
            for(int i=pl,j=1;i<=pr;i++,j++) sum[bl]+=j*x,p[bl][i]+=j*x;
            return;
        }
        reset(bl),reset(br);
        int now=1; 
        for(int i=pl;i<(int)p[bl].size();i++,now++) sum[bl]+=now*x,p[bl][i]+=now*x;
        for(int i=bl+1;i<=br-1;now+=p[i].size(),i++) {
            long long start=now*x,end=start+(p[i].size()-1)*x;
            sum[i]+=(start+end)*p[i].size()/2;
            al[i]+=start,ad[i]+=x;
        }
        for(int i=0;i<=pr;i++,now++) sum[br]+=now*x,p[br][i]+=now*x;
    }
    void change3(int x,int y) { //单点插入 
        auto L=get_block(x);
        int bl=L.first,pl=L.second;
        reset(bl),p[bl].insert(p[bl].begin()+pl,y),sum[bl]+=y; 
        if((int)p[bl].size()>10*B) rebuild();
    }
    long long query(int l,int r) { //区间求和 
        auto L=get_block(l),R=get_block(r);
        int bl=L.first,pl=L.second,br=R.first,pr=R.second;
        long long res=0;
        if(bl==br) {
            reset(bl);
            for(int i=pl;i<=pr;i++) res+=p[bl][i];
            return res;
        }
        reset(bl),reset(br);
        for(int i=pl;i<(int)p[bl].size();i++) res+=p[bl][i];
        for(int i=0;i<=pr;i++) res+=p[br][i];
        for(int i=bl+1;i<=br-1;i++) res+=sum[i];
        return res;
    }

    int main() {
        scanf("%d%d",&n,&q);
        B=sqrt(n),cnt=(n-1)/B+1;
        for(int i=1;i<=n;i++) {
            scanf("%lld",&a[i]);
            sum[(i-1)/B+1]+=a[i];
            p[(i-1)/B+1].push_back(a[i]);
        }
        for(int i=1;i<=cnt;i++) cov[i]=-1;
        while(q--) {
            int opt,l,r;
            long long x;
            scanf("%d%d%d",&opt,&l,&r);
            if(opt==1) scanf("%lld",&x),change1(l,r,x);
            else if(opt==2) scanf("%lld",&x),change2(l,r,x);
            else if(opt==3) change3(l,r);
            else printf("%lld\n",query(l,r));
        }

        return 0;
    }
}

int main() {
    Cherry::main();

    return 0;
}

• 然而，通过每次都插入在序列的末尾，实测上面的代码会被卡得很惨。考虑对操作三的插入操作，使用 块状链表 代替 vector 维护。

  • 只需要使用数组而非 vector 维护块内的元素，重构时也只需要将单块分裂为两块而不用整个序列重构。
  • 注意块长不能设置为 \sqrt n，因为如果 n 初始很小而插入操作很多，可能会导致最后块长过小而超时。

• 时间复杂度 O(n\sqrt n)。

参考代码如下。

#include <bits/stdc++.h> //分块（块状链表） 
using namespace std;

namespace Cherry {
    const int N=2e5+10,M=1605;
    int n,q,B,cnt;

    struct chain { //块状链表 
        int len,nextt;
        long long sum,cov,al,ad;
        long long a[M];
    }p[M];
    pair<int,int> get_block(int x) { //找到x对应的块和块内位置 
        int cur=1;
        while(p[cur].nextt&&p[cur].len<x) x-=p[cur].len,cur=p[cur].nextt;
        return make_pair(cur,x);
    }
    void reset(int x) { //处理块内的tag 
        if(p[x].cov) {
            for(int i=1;i<=p[x].len;i++) p[x].a[i]=p[x].cov;
            p[x].cov=0;
        }
        if(p[x].al||p[x].ad) {
            for(int i=1;i<=p[x].len;i++) p[x].a[i]+=p[x].al+(i-1)*p[x].ad;
            p[x].al=p[x].ad=0;
        }
    }
    void rebuild(int x) { //重构（分裂） 
        cnt++;
        reset(x); //注意要先处理完tag 
        for(int i=B+1;i<=p[x].len;i++) {
            p[cnt].a[++p[cnt].len]=p[x].a[i];
            p[x].sum-=p[x].a[i],p[cnt].sum+=p[x].a[i]; //注意更新总和 
        }
        p[x].len=B,p[cnt].nextt=p[x].nextt,p[x].nextt=cnt;
    }
    void change1(int l,int r,long long x) { //区间赋值 
        auto L=get_block(l),R=get_block(r);
        int bl=L.first,pl=L.second,br=R.first,pr=R.second;
        if(bl==br) {
            reset(bl);
            for(int i=pl;i<=pr;i++) p[bl].sum+=x-p[bl].a[i],p[bl].a[i]=x;
            return;
        }
        reset(bl),reset(br);
        for(int i=pl;i<=p[bl].len;i++) p[bl].sum+=x-p[bl].a[i],p[bl].a[i]=x;
        for(int i=1;i<=pr;i++) p[br].sum+=x-p[br].a[i],p[br].a[i]=x;
        for(int i=p[bl].nextt;i!=br;i=p[i].nextt) p[i].sum=p[i].len*x,p[i].cov=x,p[i].al=p[i].ad=0; //注意等差数列加法标记会清空 
    }
    void change2(int l,int r,long long x) { //区间加等差数列 
        auto L=get_block(l),R=get_block(r);
        int bl=L.first,pl=L.second,br=R.first,pr=R.second;
        if(bl==br) {
            reset(bl);
            for(int i=pl,j=1;i<=pr;i++,j++) p[bl].sum+=j*x,p[bl].a[i]+=j*x;
            return;
        }
        reset(bl),reset(br);
        int now=1; 
        for(int i=pl;i<=p[bl].len;i++,now++) p[bl].sum+=now*x,p[bl].a[i]+=now*x;
        for(int i=p[bl].nextt;i!=br;now+=p[i].len,i=p[i].nextt) {
            long long start=now*x,end=start+(p[i].len-1)*x;
            p[i].sum+=(start+end)*p[i].len/2;
            p[i].al+=start,p[i].ad+=x;
        }
        for(int i=1;i<=pr;i++,now++) p[br].sum+=now*x,p[br].a[i]+=now*x;
    }
    void change3(int x,int y) { //单点插入 
        auto L=get_block(x);
        int bl=L.first,pl=L.second;
        reset(bl);
        p[bl].len++,p[bl].sum+=y;
        for(int i=p[bl].len;i>=pl+1;i--) p[bl].a[i]=p[bl].a[i-1];
        p[bl].a[pl]=y;
        if(p[bl].len>=2*B) rebuild(bl);
    }
    long long query(int l,int r) { //区间求和 
        auto L=get_block(l),R=get_block(r);
        int bl=L.first,pl=L.second,br=R.first,pr=R.second;
        long long res=0;
        if(bl==br) {
            reset(bl);
            for(int i=pl;i<=pr;i++) res+=p[bl].a[i];
            return res;
        }
        reset(bl),reset(br);
        for(int i=pl;i<=p[bl].len;i++) res+=p[bl].a[i];
        for(int i=1;i<=pr;i++) res+=p[br].a[i];
        for(int i=p[bl].nextt;i!=br;i=p[i].nextt) res+=p[i].sum;
        return res;
    }

    int main() {
        scanf("%d%d",&n,&q);
        B=800,cnt=(n-1)/B+1;
        for(int i=1;i<=n;i++) {
            int x;
            scanf("%d",&x);
            int bl=(i-1)/B+1;
            p[bl].sum+=x;
            p[bl].a[++p[bl].len]=x;
        }
        for(int i=1;i<=cnt;i++) p[i].nextt=(i<cnt)?i+1:0;
        while(q--) {
            int opt,l,r;
            long long x;
            scanf("%d%d%d",&opt,&l,&r);
            if(opt==1) scanf("%lld",&x),change1(l,r,x);
            else if(opt==2) scanf("%lld",&x),change2(l,r,x);
            else if(opt==3) change3(l,r);
            else printf("%lld\n",query(l,r));
        }

        return 0;
    }
}

int main() {
    Cherry::main();

    return 0;
}

附数据生成器。

#include <bits/stdc++.h>
using namespace std;

namespace Cherry {
    const int N=15;
    int n,q;
    int main() {
        srand(time(NULL)); 
        n=rand()%N+2,q=rand()%N+1;
        printf("%d %d\n",n,q);
        for(int i=1;i<=n;i++) {
            int x=rand()%N+1;
            printf("%d ",x);
        }
        printf("\n");
        while(q--) {
            int opt,l,r,x;
            opt=rand()%4+1,l=rand()%(n-1)+1,r=rand()%(n-l),x=rand()%N+1;
            printf("%d ",opt);
            if(opt==1) printf("%d %d %d\n",l,l+r,x);
            if(opt==2) printf("%d %d %d\n",l,l+r,x);
            if(opt==3) {
                n++,l=rand()%n+1,x=rand()%N+1;
                printf("%d %d\n",l,x);
            }
            if(opt==4) printf("%d %d\n",l,l+r);
        }

        return 0;
    }
}

int main() {
    freopen("data.in","w",stdout);
    Cherry::main();

    return 0;
}