洛谷 P2801 教主的魔法 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置。

题目链接:https://www.luogu.org/problem/show?pid=2801

题目描述

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

5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4

输出样例#1:

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。

分析:

题目看起来很简单,但是一百万的数据量,暴力写的话绝对超时。

TLE怎么办?区间修改询问用分块~

AC代码:.(感谢@WZY大佬提供题解程序供博主学习...)

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 inline void read(int &x)
  6 {//快速读入
  7     char ch = getchar();char c;x = 0;
  8     while(ch >‘9‘ || ch < ‘0‘)    c = ch,ch = getchar();
  9     while(ch >= ‘0‘ && ch <= ‘9‘)    x = x*10 +ch-‘0‘,ch = getchar();
 10     if(c == ‘-‘) x = -x;
 11 }
 12 inline void put(int x)
 13 {//快速输出
 14     if (x < 0)x = ~x + 1, putchar(‘-‘);
 15     if (x > 9) put(x / 10);putchar(x % 10 + 48);
 16 }
 17 const int MAXN = 1000008;
 18 const int SN = 1008;
 19 int num[MAXN],s[MAXN],belong[MAXN],flag[MAXN],block,size;
 20 //    原始···   块内··   归属····   加法标记··   块数 ·每块的大小
 21 int L[MAXN],R[MAXN];
 22 //L[i]:块i的左端点下标  R[i]:块i的右端点下标
 23
 24 int res(int x)
 25 {//对第x个块进行排序
 26     int l = L[x],r = R[x];
 27     for(register int i = l;i <= r;i ++)
 28         s[i] = num[i];
 29     std::sort(s+l,s+r+1);
 30 }
 31
 32 int find(int x,int k)
 33 {//二分查找第x个块,并找出大于k的部分
 34     int l = L[x],r = R[x];
 35     int last = r;
 36     int mid;
 37     while(l <= r)
 38     {
 39         mid = (l + r) >> 1;
 40         if(s[mid] < k) l = mid + 1;
 41         else r = mid - 1;
 42     }
 43     return last - l + 1;
 44 }
 45
 46 inline void modify(int l,int r,int k)
 47 {//区间修改
 48     if(belong[l] == belong[r])
 49     {
 50         for(register int i = l;i <= r;i ++)
 51             num[i] = num[i] + k;
 52         res(belong[l]);
 53         return;
 54     }
 55
 56     register int ll = belong[l],rr = belong[r];
 57     if(L[ll] < l)
 58     {
 59         for(register int i = l;i <= R[ll];i ++)
 60             num[i] += k;
 61         res(belong[l]);
 62         ++ ll;
 63     }
 64     if(R[rr] > r)
 65     {
 66             for(register int i = L[rr];i <= r;i ++)
 67                 num[i] += k;
 68             res(belong[r]);
 69             -- rr;
 70     }
 71     for(register int i = ll;i <= rr;++ i)
 72         flag[i] += k;
 73 }
 74
 75 int ask(int l,int r,int k)
 76 {//区间询问
 77     register int ans = 0;
 78     if(belong[l] == belong[r])
 79     {
 80         for(int i = l;i <=r;++ i)
 81             if(num[i] + flag[belong[i]] >= k)
 82                 ans ++;
 83         return ans;
 84     }
 85     register int ll = belong[l],rr = belong[r];
 86     if(L[ll] < l)
 87     {
 88         for(register int i = ll;i <= R[ll];i ++)
 89             if(num[i] + flag[belong[i]] >= k)
 90                 ans ++;
 91         ++ ll;
 92     }
 93     if(R[rr] > r)
 94     {
 95         for(register int i = L[rr];i <= r;++ i)
 96             if(num[i] + flag[belong[i]] >= k)
 97                 ans ++;
 98             -- rr;
 99     }
100     for(register int i = ll;i <= rr;++ i)
101         ans = ans + find(i,k - flag[i]);
102     return ans;
103 }
104 int main()
105 {
106     int n,q;
107     read(n),read(q);
108     register char c;
109     register int l,r,x;
110 /*------------------------------------------------*/
111 //初始化各个块
112     block = sqrt(n);
113     if(n % block)    size = n/block + 1;
114     else    size = n/block;
115
116     for(register int i = 1;i <= n;++ i)
117     {
118         read(num[i]);
119         belong[i] = (i - 1)/block + 1;
120         s[i] = num[i];
121     }
122     for(register int i = 1;i <= size;++ i)
123     {
124         L[i] = (i  -1) * block + 1;
125         R[i] = i * block;
126     }
127     if(R[size] > n)    R[size] = n;
128     for(register int i = 1;i <= size;++ i)
129         res(i);
130 /*------------------------------------------------*/
131 //处理修改和询问操作
132     for(register int i = 1;i <= q; ++ i)
133     {
134         c = getchar();
135             while(c < 30)    c = getchar();
136         read(l),read(r),read(x);
137         if(c == ‘A‘)
138             put(ask(l,r,x)),putchar(‘\n‘);
139         else
140             modify(l,r,x);
141     }
142     return 0;
143 }

洛谷这道题的数据比较弱,所以容易AC

时间: 07-04

洛谷 P2801 教主的魔法 题解的相关文章

洛谷 P2801 教主的魔法

题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W.(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高) CYZ.光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高

BZOI——3343: 教主的魔法 || 洛谷—— P2801 教主的魔法

http://www.lydsy.com/JudgeOnline/problem.php?id=3343  ||  https://www.luogu.org/problem/show?pid=2801 题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全

洛谷1133 教主的花园

洛谷1133 教主的花园 本题地址:http://www.luogu.org/problem/show?pid=1133 题目描述 教主有着一个环形的花园,他想在花园周围均匀地种上n棵树,但是教主花园的土壤很特别,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值. 教主最喜欢3种树,这3种树的高度分别为10,20,30.教主希望这一圈树种得有层次感,所以任何一个位置的树要比它相邻的两棵树的高度都高或者都低,并且在此条件下,教主想要你设计出一套方案,使得观赏价值之和最

洛谷P1133 教主的花园 动态规划

洛谷P1133 教主的花园动态规划 这里是环状的,但是我们并不用将他破环成链 只要枚举第一个点 根据第一个点选择最后一个选择什么就行了 然后我们进行DP注意如果当前是 2 的话要分情况 上一次是上升 1 还是下降 0 F1[ i ] 表示 第 i 位置的种第 1 种树所能获得的最大价值 F2[ i ][ 0 ] 表示 第 i 位置的 种第 2 种树 且上次是下降 1 #include <bits/stdc++.h> 2 #define For(i,j,k) for(int i=j;i<=

BZOJ3343 &amp; 洛谷2801:教主的魔法——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=3343 https://www.luogu.org/problemnew/show/2801 题目描述 教主最近学会了一种神奇的魔法,能够使人长高.于是他准备演示给XMYZ信息组每个英雄看.于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1.2.…….N. 每个人的身高一开始都是不超过1000的正整数.教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整

洛谷 P1106 删数问题 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:https://www.luogu.org/problem/show?pid=1106 题目描述 键盘输入一个高精度的正整数N,去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的正整数.编程对给定的N和k,寻找一种方案使得剩下的数字组成的新数最小. 输出应包括所去掉的数字的位置和组成的新的正整数.(N不超过250位) 输入数据均不需判错. 输入输出格式 输入格式: n (高精度的正整数) k (需要删除的数字

【基础练习】【背包DP】洛谷1164 小A点菜题解

洛谷的题目又有那令人···的悲剧格式= = 洛谷1164 小A点菜 本题地址:http://www.luogu.org/problem/show?pid=1164 题目背景 uim神犇拿到了uoi的ra(镭牌)后,立刻拉着基友小A到了一家--餐馆,很低端的那种. uim指着墙上的价目表(太低级了没有菜单),说:"随便点". 题目描述 不过uim由于买了一些辅(e)辅(ro)书,口袋里只剩M元(M<=10000). 餐馆虽低端,但是菜品种类不少,有N种(N<=100),第i种

洛谷 P1022 计算器的改良 题解

此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置. 题目链接:https://www.luogu.org/problem/show?pid=1022 题目背景 NCL是一家专门从事计算器改良与升级的实验室,最近该实验室收到了某公司所委托的一个任务:需要在该公司某型号的计算器上加上解一元一次方程的功能.实验室将这个任务交给了一个刚进入的新手ZL先生. 题目描述 为了很好的完成这个任务,ZL先生首先研究了一些一元一次方程的实例: 4+3x=8 6a-5+1=2-2a -5+12y=

洛谷3953:逛公园——题解

https://www.luogu.org/problemnew/show/P3953 策策同学特别喜欢逛公园.公园可以看成一张n个点m条边构成的有向图,且没有自环和重边.其中1号点是公园的入口,n号点是公园的出口,每条边有一个非负权值,代表策策经过这条边所要花的时间. 策策每天都会去逛公园,他总是从1号点进去,从n号点出来. 策策喜欢新鲜的事物,他不希望有两天逛公园的路线完全一样,同时策策还是一个特别热爱学习的好孩子,他不希望每天在逛公园这件事上花费太多的时间.如果1号点到n号点的最短路长为d