BZOJ 3343: 教主的魔法

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 N 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 1、2、……、N。
每个人的身高一开始都是不超过 1000 的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数 W。（虽然 L=R 时并不符合区间的书写规范，但我们可以认为是单独增加第 L（R）个英雄的身高）
CYZ、光哥和 ZJQ 等人不信教主的邪，于是他们有时候会问 WD 闭区间 [L, R] 内有多少英雄身高大于等于 C，以验证教主的魔法是否真的有效。
WD 巨懒，于是他把这个回答的任务交给了你。

Input

第 1 行为两个整数 N、Q。Q 为问题数与教主的施法数总和。 第 2 行有 N 个正整数，第 i 个数代表第 i 个英雄的身高。 第 3 到第 Q+2 行每行有一个操作： （1）若第一个字母为“M”，则紧接着有三个数字 L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上 W。 （2）若第一个字母为“A”，则紧接着有三个数字 L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于 C。

Output

对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于 C 的英雄数。

Sample Input

5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4

Sample Output

2
3

HINT

【输入输出样例说明】 原先 5 个英雄身高为 1、2、3、4、5，此时[1, 5]间有 2 个英雄的身高大于等于 4。教主施法后变为 1、2、4、5、6，此时[1, 5]间有 3 个英雄的身高大于等于 4。 【数据范围】 对 30%的数据，N≤1000，Q≤1000。 对 100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。

Solution

分块可以做，然而花式分块更快。。

在每个操作的端点处划分，共分为最多 $4Q$ 块，那么每个操作必会在一段连续块上。

处理每块时，遍历所有包含它的操作，若为修改，则 delta+=w，若为查询，则记录 c-delta，然后将询问按 c-delta 排序。
之后遍历该块中的数，二分+差分维护贡献。 时间复杂度 $O(Q^2\log Q+N\log Q)$。

Code

#include<bits/stdc++.h>

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline void repr(T &a,T b){if(a<b)a=b;}
template<typename T> inline void repl(T &a,T b){if(a>b)a=b;}
template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define lb(x) ((x)&(-(x)))
#define sqr(x) ((x)*(x))
#define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d)

int n,m,h[1000001],q[3000][4],bl[12010],ans[3000],tmp[3000];

struct yjq
{
    int x,id;
    inline bool operator <(const yjq &p)const
    {
        return x<p.x;
    }
}f[3000];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%d",h+i);
    int bc=2;
    bl[0]=n-1;
    bl[1]=-1;
    for(int i=0;i<m;i++)
    {
        char opt[2];
        scanf("%s%d%d%d",opt,&q[i][1],&q[i][2],&q[i][3]);
        q[i][1]--,q[i][2]--;
        q[i][0]=opt[0]=='A';
        bl[bc++]=q[i][1]-1;
        bl[bc++]=q[i][2];
    }
    std::sort(bl,bl+bc);
    bc=std::unique(bl,bl+bc)-bl;
    for(int i=1;i<bc;i++)
    {
        bl[i-1]++;
        int delta=0,fm=0;
        for(int j=0;j<m;j++)
            if(q[j][1]<=bl[i-1]&&q[j][2]>=bl[i])
            {
                if(q[j][0]==0)
                    delta+=q[j][3];
                else
                    f[fm].x=q[j][3]-delta,f[fm++].id=j;
            }
        std::sort(f,f+fm);
        memset(tmp,0,sizeof(tmp));
        for(int j=bl[i-1];j<=bl[i];j++)
        {
            if(f[0].x>h[j])continue;
            int l=0,r=fm;
            while(r-l>1)
            {
                if(f[(l+r)>>1].x>h[j])
                    r=(l+r)>>1;
                else
                    l=(l+r)>>1;
            }
            tmp[l]++;
        }
        for(int j=fm-1,t=0;j>=0;j--)
        {
            t+=tmp[j];
            ans[f[j].id]+=t;
        }
    }
    for(int i=0;i<m;i++)
        if(q[i][0]==1)
            printf("%d\n",ans[i]);
}

日期： 2016-11-15

标签： BZOJ 分块

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/76/ 查看。