luogu P2801 教主的魔法
分块
7 分钟 读完 (大约 1018 个字) 0次访问

luogu P2801 教主的魔法

题目：P2801 教主的魔法

题目描述

教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。

每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）

CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。

WD巨懒，于是他把这个回答的任务交给了你。

输入格式

第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。

输出格式

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

输入输出样例

输入 #1
1
2
3
4
5
6
7
8
9
5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4
输出 #1
1
2
2
3

说明/提示

【输入输出样例说明】

原先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}$ 个区间，查询时，如果区间覆盖了一个块，则直接输出块的答案。显然这样做最多只有两个块需要单独操作。

查询：本题不是查询区间和，为方便查找大于 $c$ 的数目，再用另外一个数组 $t[]$ 对区间进行排序，查询时利用二分查找即可。

区间增加：对于一整个区间被覆盖的情况，用 $dlt[]$ 数组将整个区间加上 $w$。边界处暴力增加。

时间复杂度：$O(Q\sqrt{N}\log N)$。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
namespace iNx{
    const int N = 1e6 + 7 ;
    const int SQN = 1e3 + 7 ;
    int a[N],t[N],st[SQN],ed[SQN],belong[N],size[SQN],dlt[SQN];
    int n,q; 
    void SORT(int x){
        for(int i=st[x];i<=ed[x];i++) t[i]=a[i];
        sort(t+st[x],t+ed[x]+1);
    }
    void init(){
        int num=sqrt(n);
        int i,j;
        for(i=0;i<num;i++){
            st[i+1]=n/num * i + 1;
            ed[i+1]=n/num * (i+1);
        }
        ed[num]=n;
        for(i=1;i<=num;i++){
            SORT(i);
            for(j=st[i];j<=ed[i];j++) belong[j]=i;
            size[i]=ed[i]-st[i]+1;
        }
    }
    void modify(int l,int r,int c){
        int x=belong[l],y=belong[r],i;
        if(x==y){
            for(i=l;i<=r;i++)
                a[i]+=c;
            SORT(x);
            return ;
        }
        for(i=l;i<=ed[x];i++) a[i]+=c;
        for(i=st[y];i<=r;i++) a[i]+=c;
        for(i=x+1;i<y;i++) dlt[i]+=c;
        SORT(x);
        SORT(y);
    }
    int BF(int l,int r,int c,int x){
        int ans=r+1,L=l,R=r,mid;
        while(L<=R){
            mid=(L+R)>>1;
            if(t[mid]+dlt[x]>=c) ans=mid,R=mid-1;
            else L=mid+1;
        }
        return (r-ans+1);
    }
    int answer(int l,int r,int c){
        int i,ans=0;
        int x=belong[l],y=belong[r];
        if(x==y) return BF(l,r,c,x);
        ans+=BF(l,ed[x],c,x);
        ans+=BF(st[y],r,c,y);
        for(i=x+1;i<y;i++) ans+=BF(st[i],ed[i],c,i);
        return ans;
    }
    void work(){
        scanf("%d%d",&n,&q);
        int i,l,r,c;
        char ch;
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        init();
        for(i=1;i<=q;i++){
            ch=cin.peek();
            while(ch==' '||ch=='\n'||ch=='\r'){
                cin.get();
                ch=cin.peek();
            }
            ch=cin.get();
            if(ch=='A'){
                scanf("%d%d%d",&l,&r,&c);
                printf("%d\n",answer(l,r,c));
            }
            else if(ch=='M'){
                scanf("%d%d%d",&l,&r,&c);
                modify(l,r,c);
            }
        }
    }
}
int main(){
    iNx::work();
    return 0;
}
#

喜欢这篇文章？打赏一下作者吧

绝对值最值
KMP算法

评论

QQ和我联系
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×