分块入门题，不错的，建议大家做一做

开始学习

这道题想让我们求区间[l,r]>=c的个数，然后我们可以看到“数列分块入门 2”是求区间[l,r]<c(忽略平方)的个数，即求c在区间[l,r]的排名。所以我们可以每一次查询c的排名，然后用区间长度减c的排名就可以达到答案了呢QAQ。

那么题目就被转移成了求区间[l,r]中c的排名

一看题目，咦，求[l,r]区间c的排名，马上就可以想到平衡树啦，可是平衡树这么难写，而且还不支持区间加，那怎么办？ 分块！

首先，我们一个一个步骤分着来看：

(1).操作操作和普通分块的操作一模一样，类个tag，我们先不理。

(2).查询如果一般查询排名，我们可以将这一段数截出来，排序，然后二分查找(lower_bound操作)就ok了。那我们可不可以先将每一个块的数都排好序，然后查找每一个块的时候就直接二分呢？ ofcause，当然可以！那零零散散的剩下的非整块的数就暴力找就可以了。

(3).排序操作我们查询需要先排序，那么我们排序也成为了一个操作。我们另外开一个数组ve[i]（ve[i]为vector，i表示第i个块）来存每个块排序的数据（这里我使用了vector）。到时候查询的时候直接二分ve[i]就可以了。那每一次零散修改操作都会修改数值（整块操作还是直接加tag），那么我们要对有修改数值的那个块重新进行块内排序。（额，好慢啊）

所以这道题的复杂度是O(msqrt(nlogn))

那么我们这个分块的基本思想就是这样了。还有很多小细节可以看看我的代码：

//P2801 教主的魔法

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int n,m,blo;

int v[1000005],bl[1000005],atag[1000005];

vector<int>ve[10001];

void reset(int x)                       //排序操作

{

    ve[x].clear();                      //先初始化

    for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++)

        ve[x].push_back(v[i]);          //将整个块的数值重新压进vector里

    sort(ve[x].begin(),ve[x].end());    //块内排序

}

ll read()                               //快读

{

    ll x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

void add(int a,int b,int c)             //修改操作

{

    for(int i=a;i<=min(bl[a]*blo,b);i++) v[i]+=c;   //零散操作

    reset(bl[a]);                       //重新块内排序

    if(bl[a]!=bl[b])

    {

        for(int i=(bl[b]-1)*blo+1;i<=b;i++) v[i]+=c;//零散操作

        reset(bl[b]);                   //重新块内排序

    }

    for(int i=bl[a]+1;i<=bl[b]-1;i++)

        atag[i]+=c;

}

int query(int a,int b,int c)            //查询操作

{

    int ans=0;//排名

    for(int i=a;i<=min(bl[a]*blo,b);i++)//零散暴力查询

    {

        if(v[i]+atag[bl[a]]<c)

        ans++;

    }

    if(bl[a]!=bl[b])

    {

        for(int i=(bl[b]-1)*blo+1;i<=b;i++)         //零散暴力查询

        {

            if(v[i]+atag[bl[b]]<c)

            ans++;

        }

    }

    for(int i=bl[a]+1;i<=bl[b]-1;i++)   //整块查询

    {

        int x=c-atag[i];                //注意：这里要先剪去这个块的atag，因为这整个块的所以数值都应该加了atag，所以我们二分找的数也要先剪atag

        ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin();    //注意：这里lower_bound操作返回的是地址，所以要想知道块内排名，要减块头的地址

    }   //不会用lower_bound可以直接写二分

    return ans;

}

int main()

{

    n=read();m=read();blo=sqrt(n);

    for(int i=1;i<=n;i++)v[i]=read();

    for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1,ve[bl[i]].push_back(v[i]);   //初始化ve[i]数组

    for(int i=1;i<=bl[n];i++)

    sort(ve[i].begin(),ve[i].end());    //排序

    for(int i=1;i<=m;i++)

    {

    	char f;cin>>f;

        int a=read(),b=read(),c=read();

        if(f=='M')add(a,b,c);

        if(f=='A')printf("%d\n",b-a+1-query(a,b,c));

    }

    return 0;

}

巴特西

题解 P2801 【教主的魔法】

开始学习

广告

分块学习blog

最新文章

热门文章