[分块] 数列分块入门 1~9 && BZOJ -1s 蒲公英

Author Avatar
ajcxsu 2018年04月14日
  • 67 次阅读

gayyyyyyyyyy

原题解:http://hzwer.com/8053.html
联动:https://acxblog.site/archives/TLEBA.html

T1

naive

T2

二分
这就引进了第二个数组和块内实施保持有序的操作
还得记得打标记

T3

一样
二分查找

T4

加上了区间修改
对完整的块和不完整的块分别统计就行

T5

从本题开始复杂度变成$O(玄学/能过)$
本题操作骚
每个数最多被开方4次
如果某个块被开方成了全部都是0/1的玩意,就可以跳过它
然后暴力就行

T6

插入
教你怎么暴力重构
vector大法吼啊

T7

加上了区间乘法
则加两个lazy标记
对不完整块进行改动时,需要pushdown

等等,我串戏了,这好像不是线段树。

事实上跟线段树确实挺像。不如说,通过线段树是一个很好的思考怎么分块的方式。尤其是对于lazytag的更新和下放。
我瞎扯淡信不信随您啦hhh

Code

// Code by ajcxsu
// Problem: entrance 7
#include<iostream>
#include<cstdio>
#include<cmath>
#define MOD (10007ll)
using namespace std;
typedef long long ll;

const int N=1e5+10, M=700;
ll v[N],tag[M],tag2[M];
int pos[N],bl[M],br[M];

inline void inc(ll &x, ll y) { x=(x+y)%MOD; }
inline void pl(ll &x, ll y) { x=(x*y)%MOD; }

void updblock(int x) {
    for(int i=bl[x];i<=br[x];i++)
        v[i]=(v[i]*tag2[x]+tag[x])%MOD;
    tag[x]=0, tag2[x]=1;
}

void add(int l,int r,ll c) {
    updblock(pos[l]);
    for(int i=l;i<=br[pos[l]] && i<=r;i++)
        inc(v[i],c);
    if(pos[l]!=pos[r]) {
        updblock(pos[r]);
        for(int i=r;i>=bl[pos[r]] && i>=l;i--)
            inc(v[i],c);
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        inc(tag[i],c);
}

void pl(int l,int r,ll c) {
    updblock(pos[l]);
    for(int i=l;i<=br[pos[l]] && i<=r;i++)
        pl(v[i],c);
    if(pos[l]!=pos[r]) {
        updblock(pos[r]);
        for(int i=r;i>=bl[pos[r]] && i>=l;i--)
            pl(v[i],c);
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        pl(tag[i],c), pl(tag2[i],c);
}

int main() {
    int n,unit,m;
    cin>>n;
    unit=sqrt(n), m=(n-1)/unit+1;
    for(int i=1;i<=n;i++) pos[i]=(i-1)/unit+1;
    for(int i=1;i<=m;i++) bl[i]=(i-1)*unit+1, br[i]=i*unit, tag2[i]=1;
    br[m]=n;
    for(int i=1;i<=n;i++) cin>>v[i];

    ll opt,a,b,c;
    for(int i=1;i<=n;i++) {
        cin>>opt>>a>>b>>c;
        if(opt==0) add(a,b,c);
        else if(opt==1) pl(a,b,c);
        else if(opt==2) cout<<(v[b]*tag2[pos[b]]+tag[pos[b]])%MOD<<endl;
    }

    return 0;
}

T8

判断块里的颜色是不是相等
然后暴力统计就行了

区间修改的话,本题同样需要使用pushdown

早就说了复杂度是玄学(摊手)

T9

最劲爆的题
在BZOJ由于被-1s看不到

首先$O(n\sqrt{n})$处理f[i][j]代表块i到块j的众数

然后用$O(logn)$的时间快速查询区间$[l,r]$的数的个数,原理就是把每个数离散化之后,坐标按顺序塞到vector里,之后如果要查某个数,则把对应的区间塞到那个数的坐标vector里二分。也就是说要两遍二分。

之后我们查询块时,完整块就可以直接找f[i][j]惹 但是大小还是可能会变,因此还得查一遍$[l,r]$中f[i][j]的数量。 然后对于不完整的块,把里面数的数量都查一遍就OK了,取个最大值。 查询的复杂度最坏是$O(4\sqrt{n}logn)$

由于降智打击2,在下做了许多傻逼常数优化,结果发现自己是代码写错了

常数优化也不知道有没有用,反正总共跑了1s多的样子?

Code UPD - 2018.09.12

我写了假的离散化..
假的LOJ和假的初始化...

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

const int N=1e6+10,M=700;
int pos[N],bl[M],br[M];
int f[M][M],fc[M][M];
int v[N];
int lis[N];

vector<int> p[N];
int tot[N];
int tim[N],rem[N],ntim;

int cnt(int l,int r,int x) {
    assert(x<N);
    if(ntim>tim[x]) tim[x]=ntim;
    else return rem[x];
    return rem[x]=upper_bound(p[x].begin(), p[x].end(), r) - lower_bound(p[x].begin(), p[x].end(), l);
}

int query(int l,int r) {
    ntim++;
    int ret=f[pos[l]+1][pos[r]-1], times=fc[pos[l]+1][pos[r]-1], nt=0;
    for(int i=l;i<=br[pos[l]] && i<=r;i++) {
        nt=cnt(l,r,v[i]);
        if((nt==times && v[i]<ret) || nt>times) times=nt, ret=v[i];
    }
    if(pos[l]!=pos[r]) {
        for(int i=r;i>=bl[pos[r]] && i>=l;i--) {
            nt=cnt(l,r,v[i]);
            if((nt==times && v[i]<ret) || nt>times) times=nt, ret=v[i];
        }
    }
    return ret;
}

inline void gn(int &x) {
    x=0;
    int t=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') t=(ch=='-'?-1:1), ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=t;
}

char str[100];
inline void pn(int x) {
    register int i=0;
    while(x) str[i++]=x%10+'0', x/=10;
    while((--i)>=0) putchar(str[i]);
    putchar('\n');
}

int main() {
    int n,unit,m,q;
    gn(n), gn(q);
    unit=sqrt(n);
    m=(n-1)/unit+1;
    for(int i=1;i<=n;i++) gn(v[i]), pos[i]=(i-1)/unit+1, lis[i]=v[i];
    for(int i=1;i<=m;i++) bl[i]=br[i-1]+1, br[i]=i*unit;
    br[m]=n;
    int k;
    sort(lis+1,lis+1+n), k=unique(lis+1, lis+1+n)-lis;
    for(int i=1;i<=n;i++) v[i]=lower_bound(lis+1, lis+k, v[i])-lis;
    for(int i=1;i<=n;i++) p[v[i]].push_back(i);
    for(int i=1;i<=m;i++) {
        memset(tot,0,sizeof(tot));
        for(int j=i;j<=m;j++) {
            fc[i][j]=fc[i][j-1], f[i][j]=f[i][j-1];
            for(int k=bl[j];k<=br[j];k++) {
                tot[v[k]]++;
                if(tot[v[k]]>fc[i][j] || (tot[v[k]]==fc[i][j] && v[k]<f[i][j])) f[i][j]=v[k], fc[i][j]=tot[v[k]];
            }
        }
    }
    int l,r, lst=0;
    for(int i=1;i<=q;i++) {
        gn(l), gn(r), l=(l+lst-1)%n+1, r=(r+lst-1)%n+1;
        if(l>r) swap(l,r);
        printf("%d\n", lst=lis[query(l,r)]);
    }
    return 0;
}

本文链接:https://acxblog.site/archives/TLEBA-B.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。