分块小讲

博主在三天的奋战后,终于AC这些题目
博主在最近仔细研磨了港台立言的分块课件,收获颇丰,现在来写一写

首先分块是什么,分块是暴力

我们来看一个例子,假设我们要写区间加的题目(没错就是线段树),然后我们要用分块的方法打,对于线段树我们是在一些节点上面打标记,然后询问时下放标记就好了….分块也差不多,首先顾名思义,分块是把一个数组分成好多块,我们对于一个操作,对于包含整个块的,我们打一个tag,对于边上的我们直接暴力…..
如果一共有n个数,我们分成k个块,那么复杂度为O(\frac{n}{k}+k),然后当我们k\sqrt{n}时,复杂度就变成了\sqrt{n},然后对于m次操作,然后总复杂度就是m\sqrt{n}….
然后你就学会了一种会TLE的线段树暴力写法….
(当然分块不是用来写这些的,但是会这些,你已经会写数列分块前几题了)

数列分块入门1传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,单点查值。
1 \leq n \leq 50000,- 2^{31} \leq other,ans \leq 2^{31} - 1

分析:

我们来看第一题,哇,线段树,然后你过了……
好吧我们来看分块,直接分块,然后像我上面说的例子,打tag就好了

代码:

这里有一个小tip:
1. 最好预先处理所有数字在哪一个块
2. 块最好从0开始,这样子对于块x,他的起始位置和终止位置就是k\times x+1k\times x+k

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,k,a[N],tag[N],m;
int block[N],tot;
int main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++)
    {
        block[i]=tot;
        if(i%k==0) tot++; 
    }
    for(int i=1;i<=n;i++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);
        if(opt==0)
        {
            int L=block[l],R=block[r];
            for(int j=L+1;j<R;j++) tag[j]+=c;
            if(block[l]==block[r]) for(int j=l;j<=r;j++) a[j]+=c;
            else 
            {
                for(int j=l;j<=block[l]*k+k;j++) a[j]+=c;
                for(int j=block[r]*k+1;j<=r;j++) a[j]+=c;
            }
        }
        else 
        {
            int R=r/k-(r%k==0?1:0);
            printf("%d\n",a[r]+tag[R]);
        }
    }
    return 0;
}

数列分块入门2传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,询问区间内小于某个值 x\times x 的元素个数。

分析:

这道题我们因为要算有多少个数字比询问的小,同时要维护加法,所以我们对于每一个块,维护一个单调递增的数列,对于一个块的加法,直接打tag因为,块内的所有数字都加上这个数字,他们的上升序列相对位置不边,对于两边的零散位置,直接暴力修改,改完直接重新排序就好了…
对于每一次询问,我们对于两边直接暴力\sqrt{n},对于块内的,二分位置….就好了….
博主在写这道题目的时候出了一点小意外,然后发现只分了一个块,然后每次询问都是暴力查询,复杂度变成n^2,然后松过了…..(一脸迷茫)

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; register LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,x[N],k;
int b[N],tot,tag[N];
int vec[N][250];
int siz[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]),vec[b[i]][++siz[b[i]]]=x[i];
    for(int i=0;i<=tot;i++) sort(vec[i]+1,vec[i]+siz[i]+1);
    for(int cas=1,opt,l,r,c;cas<=n;cas++)
    {
        read(opt);read(l),read(r),read(c);
        if(opt==0)
        {
            int L=b[l],R=b[r];
            for(register int i=L+1;i<R;i++) tag[i]+=c;
            if(b[l]==b[r]) 
            {   
                for(register int i=l;i<=r;i++) x[i]+=c;siz[L]=0;
                for(register int i=L*k+1;i<=min(L*k+k,n);i++) vec[L][++siz[L]]=x[i];
                sort(vec[L]+1,vec[L]+siz[L]+1);
            }
            else 
            {
                for(register int i=l;i<=L*k+k;i++) x[i]+=c;siz[L]=0;
                int h=min(L*k+k,n);
                for(register int i=L*k+1;i<=h;i++) vec[L][++siz[L]]=x[i];
                sort(vec[L]+1,vec[L]+siz[L]+1);
                for(register int i=R*k+1;i<=r;i++) x[i]+=c;siz[R]=0;
                h=min(R*k+k,n);
                for(register int i=R*k+1;i<=h;i++) vec[R][++siz[R]]=x[i];
                sort(vec[R]+1,vec[R]+siz[R]+1);
            }
        }
        else 
        {
            int L=b[l],R=b[r],ans=0;;
            if(L+2>=R)
            {
                for(register int i=l;i<=r;i++)
                    if(x[i]+tag[b[i]]<(LL)c*c)
                        ans++;
            }
            else
            {
                int h=(L+1)*k;
                for(register int i=l;i<=h;i++)
                    if(x[i]+tag[b[i]]<(LL)c*c)
                        ans++;
                if(R!=L)
                {
                    for(register int i=R*k+1;i<=r;i++)
                        if(x[i]+tag[b[i]]<(LL)c*c)
                            ans++;
                }
                for(register int i=L+1;i<=R-1;i++)
                {
                    register int ll=1,rr=siz[i],ret=0;
                    while(ll<=rr)
                    {
                        register int mid=(ll+rr)>>1;
                        if(vec[i][mid]+tag[i]>=(LL)c*c) rr=mid-1;
                        else ret=mid,ll=mid+1; 
                    }
                    ans+=ret;
                }
            }
            writeln(ans);
        }
    }
    return 0;
}

数列分块入门3传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,询问区间内小于某个值 x 的前驱(比其小的最大元素)。

分析:

这道题我感觉很假,我直接在上一题的代码上修改,把每次二分返回的位置,变成值,和ansmax就好了….

代码:



\#include<bits/stdc++.h> #define LL long long #define P pair<int,int> const LL N=1e5+10; const LL mod=1e9+7; const LL inf=1e17; using namespace std; template<typename tp> inline void read(tp &x) { x=0; char c=getchar(); bool f=0; for(;c<'0'||c>'9';f|=(c=='-'),c = getchar()); for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar()); if(f) x=-x; } template<typename tp> inline void write(tp x) { if (x==0) return (void) (putchar('0')); if (x<0) putchar('-'),x=-x; LL pr[20]; register LL cnt=0; for (;x;x/=10) pr[++cnt]=x%10; while (cnt) putchar(pr[cnt--]+'0'); } template<typename tp> inline void writeln(tp x) { write(x); putchar('\n'); } int n,x[N],k; int b[N],tot,tag[N]; int vec[N][350]; int siz[N]; signed main() { read(n);k=sqrt(n); for(int i=1;i<=n;i++) {b[i]=tot;if(i%k==0&&i!=n) tot++;} for(int i=1;i<=n;i++) read(x[i]),vec[b[i]][++siz[b[i]]]=x[i]; for(int i=0;i<=tot;i++) sort(vec[i]+1,vec[i]+siz[i]+1); for(int cas=1,opt,l,r,c;cas<=n;cas++) { read(opt);read(l),read(r),read(c); if(opt==0) { int L=b[l],R=b[r]; for(register int i=L+1;i<R;i++) tag[i]+=c; if(b[l]==b[r]) { for(register int i=l;i<=r;i++) x[i]+=c;siz[L]=0; for(register int i=L*k+1;i<=min(L*k+k,n);i++) vec[L][++siz[L]]=x[i]; sort(vec[L]+1,vec[L]+siz[L]+1); } else { for(register int i=l;i<=L*k+k;i++) x[i]+=c;siz[L]=0; int h=min(L*k+k,n); for(register int i=L*k+1;i<=h;i++) vec[L][++siz[L]]=x[i]; sort(vec[L]+1,vec[L]+siz[L]+1); for(register int i=R*k+1;i<=r;i++) x[i]+=c;siz[R]=0; h=min(R*k+k,n); for(register int i=R*k+1;i<=h;i++) vec[R][++siz[R]]=x[i]; sort(vec[R]+1,vec[R]+siz[R]+1); } } else { int L=b[l],R=b[r],ans=-1; if(L+2>R) { for(register int i=l;i<=r;i++) if(x[i]+tag[b[i]]<c) ans=max(ans,x[i]+tag[b[i]]); } else { int h=(L+1)*k; for(register int i=l;i<=h;i++) if(x[i]+tag[b[i]]<c) ans=max(ans,x[i]+tag[b[i]]); if(R!=L) { for(register int i=R*k+1;i<=r;i++) if(x[i]+tag[b[i]]<c) ans=max(ans,x[i]+tag[b[i]]); } for(register int i=L+1;i<=R-1;i++) { register int ll=1,rr=siz[i],ret=0; while(ll<=rr) { register int mid=(ll+rr)>>1; if(vec[i][mid]+tag[i]>=c) rr=mid-1; else ret=mid,ll=mid+1; } if(ret) ans=max(ans,vec[i][ret]+tag[i]); } } writeln(ans); } } return 0; }

数列分块入门4传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,区间求和。

分析:

然后这道题目,非常简单啊!只要对于每一个块多维护一个sum就好了,水一水就过了….

代码:

#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; register LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,x[N],k;
int b[N],tot,tag[N];
int vec[N],siz[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;siz[tot]++;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]),vec[b[i]]+=x[i];
    for(int cas=1,opt,l,r,c;cas<=n;cas++)
    {
        read(opt);read(l),read(r),read(c);
        if(opt==0)
        {
            int L=b[l],R=b[r];
            for(register int i=L+1;i<R;i++) tag[i]+=c;
            if(b[l]==b[r]) 
            {
                vec[b[l]]=0;
                for(register int i=l;i<=r;i++) x[i]+=c;
                for(int i=b[l]*k+1;i<=b[l]*k+k;i++)
                    vec[b[l]]+=x[i];
            }
            else 
            {
                vec[b[l]]=0;
                for(register int i=l;i<=L*k+k;i++) x[i]+=c;
                for(int i=b[l]*k+1;i<=b[l]*k+k;i++)
                    vec[b[l]]+=x[i];
                vec[b[r]]=0;
                for(register int i=R*k+1;i<=r;i++) x[i]+=c;
                for(int i=b[r]*k+1;i<=b[r]*k+k;i++)
                    vec[b[r]]+=x[i];
            }
        }
        else 
        {
            int L=b[l],R=b[r],ans=0;
            if(L+2>R)
            {
                for(register int i=l;i<=r;i++)
                    ans+=x[i]+tag[b[i]];
            }
            else
            {
                int h=(L+1)*k;
                for(register int i=l;i<=h;i++)
                    ans+=x[i]+tag[b[i]];
                if(R!=L)
                {
                    for(register int i=R*k+1;i<=r;i++)
                        ans+=x[i]+tag[b[i]];
                }
                for(register int i=L+1;i<=R-1;i++)
                    ans+=vec[i]+tag[i]*siz[i];
            }
            writeln(ans%(c+1));
        }
    }
    return 0;
}

数列分块入门5传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间开方,区间求和。

分析:

妈的,区间开方怎么写,博主刚刚看到这道题目的时候,想打人,这个东西完全不会啊,求和怎么写啊…..
然后弃疗…..
然后想了想,我们可以发现一个数字凯放最多20次(可能没有那么多),那么这么多次以后,数字就变成一了,然后我就对每一个块维护了一个数字不唯一的vector,每次对于块打tag,然后询问时一起开方,这样子复杂度是O(n\sqrt{n}+20\times n)的,过了….

代码:

#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int b[N],siz[N],tot,tag[N],sum[N];
deque<int> vec[N];
void Sqrt(int &a,int b){while(b&&a>1) b--,a=sqrt(a);}
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;siz[tot]++;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) {read(x[i]),sum[b[i]]+=x[i]; if(x[i]>1) vec[b[i]].push_back(i);}
    for(int cas=1;cas<=n;cas++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);
        if(opt==0)
        {
            int L=b[l],R=b[r];
            for(int i=L+1;i<R;i++) tag[i]+=1;
            if(b[l]==b[r]) 
            {   
                for(int i=l;i<=r;i++) x[i]=sqrt(x[i]);
                vec[L].clear();sum[L]=0;
                for(int i=L*k+1;i<=min(L*k+k,n);i++) 
                {
                    sum[L]+=x[i];
                    if(x[i]>1) vec[L].push_back(i);
                }
            }
            else 
            {
                for(int i=l;i<=L*k+k;i++) x[i]=sqrt(x[i]);
                vec[L].clear();sum[L]=0;
                for(int i=L*k+1;i<=min(L*k+k,n);i++) 
                {
                    sum[L]+=x[i];
                    if(x[i]>1) vec[L].push_back(i);
                }
                for(int i=R*k+1;i<=r;i++) x[i]=sqrt(x[i]);
                vec[R].clear();sum[R]=0;
                for(int i=R*k+1;i<=min(R*k+k,n);i++) 
                {
                    sum[R]+=x[i];
                    if(x[i]>1) vec[R].push_back(i);
                }
            }
        }
        else 
        {
            int L=b[l],R=b[r],ans=0;;
            if(L+2>=R)
            {
                for(int i=L*k+1;i<=min(n,R*k+k);i++) Sqrt(x[i],tag[b[i]]);
                for(int i=l;i<=r;i++) ans+=x[i];
                for(int i=L;i<=R;i++)
                {
                    vec[i].clear();sum[i]=0;tag[i]=0;
                    for(int j=i*k+1;j<=min(i*k+k,n);j++) {sum[i]+=x[j];if(x[j]>1) vec[i].push_back(j);}
                }
            }
            else
            {
                if(tag[L])
                {
                    deque<int> de;
                    while(!vec[L].empty())
                    {
                        int now=vec[L].front();vec[L].pop_front();
                        sum[L]-=x[now];Sqrt(x[now],tag[L]);
                        sum[L]+=x[now];
                        if(x[now]>1) de.push_back(now);
                    }tag[L]=0;
                    while(!de.empty()) vec[L].push_back(de.front()),de.pop_front();
                }
                for(int i=l;i<=L*k+k;i++) ans+=x[i];
                if(tag[R])
                {
                    deque<int> de;
                    while(!vec[R].empty())
                    {
                        int now=vec[R].front();vec[R].pop_front();
                        sum[R]-=x[now];Sqrt(x[now],tag[R]);
                        sum[R]+=x[now];
                        if(x[now]>1) de.push_back(now);
                    }tag[R]=0;
                    while(!de.empty()) vec[R].push_back(de.front()),de.pop_front();
                }
                for(int i=R*k+1;i<=r;i++) ans+=x[i];
                for(int i=L+1;i<=R-1;i++)
                {
                    if(tag[i])
                    {
                        deque<int> de;
                        while(!vec[i].empty())
                        {
                            int now=vec[i].front();vec[i].pop_front();
                            sum[i]-=x[now];Sqrt(x[now],tag[i]);
                            sum[i]+=x[now];
                            if(x[now]>1) de.push_back(now);
                        }
                        while(!de.empty()) vec[i].push_back(de.front()),de.pop_front();
                        tag[i]=0;
                    }
                    ans+=sum[i];
                }
            }
            writeln(ans);
        }
    }
    return 0;
}

(哎呀呀好像代码格式崩了,嘤嘤嘤)

数列分块入门6传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及单点插入,单点询问,数据随机生成。

分析:

诶,我靠,这他妈怎么还单点插入的啊,要死啊,博主刚看题时的心里想法…..
我们知道数列分块在分完块以后,然后对于一个块,我们已经确定了他的大部分信息,插入点是插不进去了(大佬算了,你们爱怎么写怎么写),那么什么东西可以做到单点插入呢…没错是链表….
然后,我们对于一个链,记录他的头和大小,每次询问和,插入先跳到对应的链再跳到对应的点,进行O(1)插入和询问….这是有一个要点,对于一个链如果他大于2\times k时,我们要进行重建以保证复杂度….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+10;
const LL mod=1e9+7;
const LL inf=1e17;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N],cnt;
struct Node{int next,cost;}node[N*2],top[N];
int siz[N],tot;
signed main()
{
    read(n);k=sqrt(n);cnt=n;
    for(int i=1;i<=n;i++) 
    {   
        siz[tot]++;
        if(i%k==1) top[tot].cost=i,top[tot].next=tot+1;
        if(i%k==0&&i!=n) tot++;
    }
    top[tot].next=0;
    for(int i=1;i<=n;i++) read(x[i]),node[i].cost=x[i];
    for(int i=1;i<=n;i++) if(i%k!=0&&i!=n) node[i].next=i+1;
    for(int cas=1;cas<=n;cas++)
    {
        int opt,l,r,c,flag=0,now=0,sum=0,zz;
        read(opt),read(l),read(r),read(c);
        if(opt==0)
        {
            while(sum+siz[now]<l) sum+=siz[now],now=top[now].next; zz=now;
            now=top[now].cost;
            if(l-sum==1) flag=1;
            while(l-sum-2>0) l--,now=node[now].next;
            if(flag)
            {
                node[++cnt].cost=r;
                node[cnt].next=now;
                top[zz].cost=cnt;
                siz[zz]++;
            }
            else
            {
                node[++cnt].cost=r;
                node[cnt].next=node[now].next;
                node[now].next=cnt;
                siz[zz]++;
            }
            if(siz[zz]==2*k)
            {
                now=top[zz].cost;
                int tiao=siz[zz];
                while(tiao>k+1) tiao--,now=node[now].next;
                top[++tot].next=top[zz].next;
                top[zz].next=tot;
                top[tot].cost=node[now].next;
                node[now].next=0;
                siz[zz]=siz[zz]-k;
                siz[tot]=k;
            }
        }
        else 
        {
            while(sum+siz[now]<r) sum+=siz[now],now=top[now].next; zz=now;
            now=top[now].cost;
            while(r-sum-1>0) r--,now=node[now].next;
            printf("%d\n",node[now].cost);
        }
    }
    return 0;
}

数列分块入门7传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间乘法,区间加法,单点询问。

分析:

对于这个题目,我们可以分类讨论,打两个tag,一个表示乘法,一个表示加法,最终答案为x[i]\times time[block[i]] + tag[block[i]],所以对于一次加法,对于一个块我们直接加到tag上门,然后对于零散的,要先下放整个块的乘法标记,在暴力加….对于一次乘法,我们对于两个tag,直接乘上这个值就好了,零散的也是要先下放….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=1e4+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int b[N],siz[N],tot,tag[N],times[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=0;i<=tot;i++) times[i]=1;
    for(int i=1;i<=n;i++) read(x[i]),x[i]%=mod;
    for(int cas=1;cas<=n;cas++)
    {
        int opt,l,r,c;
        read(opt),read(l),read(r),read(c);c%=mod;
        int L=b[l],R=b[r];
        if(opt==0)
        {
            for(int i=L+1;i<=R-1;i++) (tag[i]+=c)%=mod;
            for(int i=k*L+1;i<=k*L+k;i++) 
            {
                (x[i]=x[i]*times[L])%=mod;
                if(i>=l&&i<=r) (x[i]+=c)%=mod;
            }
            times[L]=1;
            if(R!=L) 
            {
                for(int i=R*k+1;i<=R*k+k;i++)
                {
                    (x[i]=x[i]*times[R])%=mod;
                    if(i>=l&&i<=r) (x[i]+=c)%=mod;
                }
                times[R]=1;
            }
        }
        else if(opt==1)
        {
            for(int i=L+1;i<=R-1;i++) (times[i]*=c)%=mod,(tag[i]*=c)%=mod;
            for(int i=k*L+1;i<=k*L+k;i++) 
            {
                (x[i]=x[i]*times[L]+tag[L])%=mod;
                if(i>=l&&i<=r) (x[i]*=c)%=mod;
            }
            times[L]=1;tag[L]=0;
            if(R!=L) 
            {
                for(int i=R*k+1;i<=R*k+k;i++)
                {
                    (x[i]=x[i]*times[R]+tag[R])%=mod;
                    if(i>=l&&i<=r) (x[i]*=c)%=mod;
                }
                times[R]=1;tag[R]=0;
            }
        }
        else printf("%d\n",(x[r]*times[b[r]]+tag[b[r]])%mod);
    }
    return 0;
}

数列分块入门8传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及区间询问等于一个数 c 的元素,并将这个区间的所有元素改为 c

分析:

这道题目,我还是有一个tag,tag0时,块内的数就是当前值,反之就是tag上门的值….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=1e4+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int b[N],tot,tag[N],siz[N];
map<int,int> Map[N];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {b[i]=tot;siz[tot]++;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]),Map[b[i]][x[i]]++;
    for(int cas=1;cas<=n;cas++)
    {
        int l,r,c,ans=0;
        read(l),read(r),read(c);
        int L=b[l],R=b[r];
        if(L+2>=R)
            for(int i=l;i<=r;i++) 
            {
                if(tag[b[i]]==c) ans++;
                else if(!tag[b[i]]) ans+=(x[i]==c);
            }
        else 
        {
            for(int i=L+1;i<=R-1;i++) if(!tag[i]) ans+=Map[i][c]; else ans+=(tag[i]==c)*siz[i];
            for(int i=l;i<=min(r,L*k+k);i++) if(!tag[L]) ans+=(x[i]==c); else ans+=(tag[L]==c);
            if(R!=L) for(int i=R*k+1;i<=r;i++) if(!tag[R]) ans+=(x[i]==c); else ans+=(tag[R]==c);
        }
        printf("%d\n",ans);
        for(int i=L+1;i<=R-1;i++) tag[i]=c;
        Map[L].clear();
        for(int i=L*k+1;i<=L*k+k;i++)
        {
            if(tag[L]) x[i]=tag[L]; if(i>=l&&i<=r) x[i]=c;
            Map[L][x[i]]++;
        }tag[L]=0;
        if(R!=L)
        {
            Map[R].clear();
            for(int i=R*k+1;i<=R*k+k;i++)
            {
                if(tag[R]) x[i]=tag[R]; if(i>=l&&i<=r) x[i]=c;
                Map[R][x[i]]++;
            }
            tag[R]=0;
        }
    }
    return 0;
}

数列分块入门9传送门

给出一个长为 n 的数列,以及 n 个操作,操作涉及询问区间的最小众数。

分析:

哇,莫队,哇不会!!!!!!
怎么办啊,好吧我们分块算了,分块复杂度一样,还tm是在线的,分块牛逼
这个东西,我们要先tm的哈希,因为这些数字太大了,然后我维护了zhong[i][j]表示i块到j块的最小众数,vec[i]表示i块的数字集合,num[i][j]表示到第i个块的j数字个数的前缀和…
然后对于一次询问,我们已经知道中间块的众数,然后依次加入两边的零散部分去更新答案就好了…

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=2e5+10;
const LL mod=1e4+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
   x=0; char c=getchar(); bool f=0;
   for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
   for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
   if(f) x=-x;
}
template<typename tp> inline void write(tp x)
{
    if (x==0) return (void) (putchar('0'));
    if (x<0) putchar('-'),x=-x;
    LL pr[20]; LL cnt=0;
    for (;x;x/=10) pr[++cnt]=x%10;
    while (cnt) putchar(pr[cnt--]+'0');
}
template<typename tp> inline void writeln(tp x)
{
    write(x);
    putchar('\n');
}
int n,k,x[N];
int block[N],tot,ha,to[N];
map<int,int> Hash;
int num[400][N],flag[N];
P zhong[400][400];
vector<int> vec[400];
signed main()
{
    read(n);k=sqrt(n);
    for(int i=1;i<=n;i++) {block[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) {read(x[i]);Hash[x[i]]=1;}
    for(auto v:Hash)  Hash[v.first]=++ha,to[ha]=v.first;
    for(int i=1;i<=n;i++) x[i]=Hash[x[i]];
    for(int i=0;i<=tot;i++)
    {
        zhong[i][i].second=0;
        for(int j=i*k+1;j<=min(k*i+k,n);j++) flag[x[j]]++;
        for(int j=1;j<=ha;j++)  
        {
            if(flag[j]>zhong[i][i].second) zhong[i][i].first=j,zhong[i][i].second=flag[j];
            if(flag[j]>0) vec[i].push_back(j);
            num[i][j]=num[i-1][j]+flag[j],flag[j]=0;
        }
    }
    for(int i=0;i<=tot;i++)
        for(int j=i+1;j<=tot;j++)
        {
            zhong[i][j]=zhong[i][j-1];
            int siz=vec[j].size();
            for(int kk=0;kk<siz;kk++)
            {
                int x=vec[j][kk],y=num[j][x]-num[i-1][x];
                if(zhong[i][j].second<y||(zhong[i][j].second==y&&zhong[i][j].first>x)) 
                    zhong[i][j].first=x,zhong[i][j].second=y;
            }
        }
    for(int i=1;i<=n;i++) 
    {
        int l,r;
        read(l),read(r);
        int L=block[l],R=block[r];
        if(L+2>=R)
        {
            P ans;ans.second=0;
            for(int i=l;i<=r;i++)
            {
                flag[x[i]]++;
                if(flag[x[i]]>ans.second||(ans.second==flag[x[i]]&&ans.first>x[i]))
                    ans.first=x[i],ans.second=flag[x[i]];
            }
            for(int i=l;i<=r;i++) flag[x[i]]--;
            printf("%d\n",to[ans.first]);
        }
        else
        {
            P ans=zhong[L+1][R-1];
            for(int i=l;i<=L*k+k;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]];
                flag[x[i]]++;
                if(flag[x[i]]>ans.second||(ans.second==flag[x[i]]&&ans.first>x[i]))
                    ans.first=x[i],ans.second=flag[x[i]];
            }
            for(int i=k*R+1;i<=r;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]];
                flag[x[i]]++;
                if(flag[x[i]]>ans.second||(ans.second==flag[x[i]]&&ans.first>x[i]))
                    ans.first=x[i],ans.second=flag[x[i]];
            }
            for(int i=l;i<=L*k+k;i++) flag[x[i]]=0;
            for(int i=k*R+1;i<=r;i++) flag[x[i]]=0;
            printf("%d\n",to[ans.first]);
        }
    }
    return 0;
}

[2009国家集训队]小Z的袜子(hose)传送门

###Description
作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1N编号,然后从编号LR(尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择。

Input

输入文件第一行包含两个正整数NMN为袜子的数量,M为小Z所提的询问的数量。接下来一行包含N个正整数C_i,其中C_i表示第i只袜子的颜色,相同的颜色用相同的数字表示。再接下来M行,每行两个正整数LR表示一个询问。

Output

包含M行,对于每个询问在一行中输出分数\frac{A}{B}表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出\frac{0}{1},否则输出的\frac{A}{B}必须为最简分数。(详见样例)

分析:

这道题和上门那个众数的题目很想,也是要维护前缀和,就是维护答案的地方有一些小技巧,如果中间块的答案已知,现在枚举两边的零散部分,x_i,这个值在块中出现过,那么我们求出块中出现的次数num,答案先减去\frac{num\times (num-1)}{2},最后统计完了一起加上就好了….

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=5e4+10;
const LL mod=1e4+7;
const LL inf=0x3f3f3f3f;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,k;
int x[N],block[N],tot;
int num[250][N],flag[N];
LL anss[250][250],vis[N];
signed main()
{
    read(n),read(m);k=sqrt(n);
    for(int i=1;i<=n;i++){block[i]=tot;if(i%k==0&&i!=n) tot++;}
    for(int i=1;i<=n;i++) read(x[i]);
    for(int i=0;i<=tot;i++)
    {
        for(int j=i*k+1;j<=min(n,i*k+k);j++) flag[x[j]]++;
        for(int j=0;j<=n;j++) 
        {
            if(flag[j]) anss[i][i]+=flag[j]*(flag[j]-1)/2;
            num[i][j]=(i-1>=0?num[i-1][j]+flag[j]:flag[j]);
        }
        for(int j=i*k+1;j<=min(n,i*k+k);j++) flag[x[j]]--;
    }
    for(int i=0;i<=tot;i++)
    {
        for(int j=i+1;j<=tot;j++)
        {
            anss[i][j]=anss[i][j-1];
            for(int l=k*j+1;l<=min(n,k*j+k);l++)
                if(!vis[x[l]])
                {
                    vis[x[l]]=1;
                    int zz=num[j-1][x[l]]-(i-1>-1?num[i-1][x[l]]:0);
                    int mdzz=num[j][x[l]]-(i-1>-1?num[i-1][x[l]]:0);
                    anss[i][j]+=mdzz*(mdzz-1)/2-zz*(zz-1)/2;
                }
            for(int l=k*j+1;l<=min(n,k*j+k);l++) vis[x[l]]=0;
        }
    }
    memset(flag,0,sizeof(flag));
    for(int cas=1;cas<=m;cas++)
    {
        int l,r,ans=0;
        read(l),read(r);
        int L=block[l],R=block[r];
        if(L+2>=R)
        {
            for(int i=l;i<=r;i++) flag[x[i]]++;
            for(int i=l;i<=r;i++) if(!vis[x[i]]){vis[x[i]]=1;ans+=flag[x[i]]*(flag[x[i]]-1)/2;}
            for(int i=l;i<=r;i++) vis[x[i]]=0,flag[x[i]]--;
        }
        else 
        {
            ans=anss[L+1][R-1];
            for(int i=l;i<=L*k+k;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]],
                    ans-=flag[x[i]]*(flag[x[i]]-1)/2;
                flag[x[i]]++;
            }
            for(int i=R*k+1;i<=r;i++)
            {
                if(!flag[x[i]]) flag[x[i]]=num[R-1][x[i]]-num[L][x[i]],ans-=flag[x[i]]*(flag[x[i]]-1)/2;
                flag[x[i]]++;
            }
            for(int i=l;i<=L*k+k;i++) if(!vis[x[i]]){vis[x[i]]=1;ans+=flag[x[i]]*(flag[x[i]]-1)/2;}
            for(int i=R*k+1;i<=r;i++) if(!vis[x[i]]){vis[x[i]]=1;ans+=flag[x[i]]*(flag[x[i]]-1)/2;}
            for(int i=l;i<=L*k+k;i++) vis[x[i]]=flag[x[i]]=0;
            for(int i=R*k+1;i<=r;i++) vis[x[i]]=flag[x[i]]=0;
        }
        if(ans==0) printf("0/1\n");
        else 
        {
            int zz=r-l+1; zz=zz*(zz-1)/2;
            int mdzz=__gcd(ans,zz);
            printf("%lld/%lld\n",ans/mdzz,zz/mdzz);
        }
    }
    return 0;
}

最后%%%hzwer大佬…然后讲完了,欢迎提问!!!

发表评论

电子邮件地址不会被公开。 必填项已用*标注