【bzoj3343】教主的魔法

2014年4月26日8092

Description

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给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。

题解

将区间分为sqrt(n)块每块排序，

修改：对于一块直接上add标记，二两端进行暴力修改

查询：对于一块用二分查找，对于单个则暴力

代码

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <queue>

#include <typeinfo>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//***************************

int b[];

int a[];

int block;

int n,m;

int add[];

int pos[];

void reset(int x){

   int l=(x-)*block+;

   int r=min(n,x*block);

   for(int  i=l;i<=r;i++)b[i]=a[i];

   sort(b+l,b+r+);

}

void update(int l,int r,int w)

{

    if(pos[l]==pos[r])

    {

        for(int i=l;i<=r;i++)a[i]=a[i]+w;

    }

    else {

        for(int i=l;i<=pos[l]*block;i++)a[i]=a[i]+w;

        for(int i=(pos[r]-)*block+;i<=r;i++)a[i]=a[i]+w;

    }

    reset(pos[l]);

    reset(pos[r]);

    for(int i=pos[l]+;i<pos[r];i++)

        add[i]=add[i]+w;

}

int ask(int l,int r,int c)

{int ans=;

    if(pos[l]==pos[r])

    {

        for(int i=l;i<=r;i++){

            if(a[i]+add[pos[i]]>=c)ans++;

        }

    }

    else {

        for(int i=l;i<=pos[l]*block;i++){

             if(a[i]+add[pos[i]]>=c)ans++;

            // cout<<

        }

        for(int i=(pos[r]-)*block+;i<=r;i++)

        {

             if(a[i]+add[pos[i]]>=c)ans++;

        }

    }

   // cout<<pos[l]+1<<" "<<pos[r]-1<<" fffff "<<ans<<endl;

    for(int i=pos[l]+;i<pos[r];i++)

    {

        int j=lower_bound(b+(i-)*block+,b+min(i*block,n)+,c-add[i])-b;//cout<<j<<" ggg ";

        ans+=(min(i*block,n)-j+);

    }

    return ans;

}

int main()

{

    int q;

    memset(add,,sizeof(add));

    cin>>n>>q;

    block=int(sqrt(n));

    for(int i=;i<=n;i++){

            cin>>a[i];

            pos[i]=(i-)/block+;

            b[i]=a[i];

    }

    if(n%block)m=n/block+;

    else m=n/block;

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

        reset(i);

    }

  //  for(int i=1;i<=n;i++)cout<<b[i]<<" ";

    int l,r,x,c;

    char ch;

    for(int i=;i<=q;i++){

            getchar();

       cin>>ch>>l>>r>>x;

        if(ch=='M'){

            update(l,r,x);

        }else {

          cout<<ask(l,r,x)<<endl;

        }

    }

    return ;

}

巴特西

【bzoj3343】教主的魔法分块

【bzoj3343】教主的魔法

Description

Input

Output

Sample Input

Sample Output

HINT

题解

代码

最新文章

热门文章

巴特西

【bzoj3343】教主的魔法 分块

【bzoj3343】教主的魔法

Description

Input

Output

Sample Input

Sample Output

HINT

题解

代码

最新文章

热门文章

【bzoj3343】教主的魔法分块