首页 > 其他分享 >P2801 教主的魔法 题解

P2801 教主的魔法 题解

时间:2023-06-15 15:25:59浏览次数:54  
标签:opt p1 val int 题解 P2801 魔法 mid sqrt

一、题目描述:

  给你一个长度为 $n$ 的序列 $a$ , 你需要进行 $m$ 次操作。

  $类型\ 1\ : 将区间\ l\ 到\ r\ 的数加\ x\ 。$

  $类型\ 2\ : 求区间\ l\ 到\ r\ 中有多少个数大于等于\ x\ 。$

  数据范围:$1 \le n \le 1\times 10^6,m \le 3\times 10^3$


 二、解题思路:

  分块:(思路当然不是我想出来的$qwq$)

  为了方便每个区间都能快速查找,首先对每个区间进行排序。

  于是二分查找即可。时间复杂度 $O(nlog_2^\sqrt{n}+m\sqrt{n}log_2^\sqrt{n})$


 三、完整代码:

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #define N 1000010
 5 using namespace std;
 6 char opt;
 7 int n,q,L,R,x,num,len;
 8 int lp[N],rp[N],pos[N],tag[N];
 9 struct Node{
10     int id,val;
11 }a[N];
12 bool cmp(Node d1,Node d2)
13 {
14     return d1.val<d2.val;
15 }
16 void pre_work()
17 {
18     len=sqrt(n);num=n/len;
19     for(int i=1;i<=num;i++)
20         lp[i]=(i-1)*len+1,rp[i]=i*len;
21     if(len*num<n)
22     {
23         num++;rp[num]=n;
24         lp[num]=(num-1)*len+1;
25     }
26     for(int i=1;i<=num;i++)
27         for(int j=lp[i];j<=rp[i];j++)
28             pos[j]=i;
29     for(int i=1;i<=num;i++)
30         sort(a+lp[i],a+rp[i]+1,cmp);
31 }
32 void update(int l,int r,int x)
33 {
34     int p1=pos[l],p2=pos[r];
35     if(p1==p2)
36     {
37         for(int i=lp[p1];i<=rp[p2];i++)
38             if(a[i].id<=r&&a[i].id>=l)
39                 a[i].val+=x;
40     }
41     else
42     {
43         for(int i=p1+1;i<=p2-1;i++)
44             tag[i]+=x;
45         update(l,rp[p1],x);
46         update(lp[p2],r,x);
47     }
48 }
49 int work(int l,int r,int x)
50 {
51     int ans=r+1,rr=r;x-=tag[pos[l]];
52     while(l<=r)
53     {
54         int mid=(l+r)>>1;
55         if(a[mid].val>=x)
56         {
57             ans=mid;
58             r=mid-1;
59         }
60         else    l=mid+1;
61     }
62     return rr-ans+1;
63 }
64 int query(int l,int r,int x)
65 {
66     int p1=pos[l],p2=pos[r],res=0;
67     if(p1==p2)
68     {
69         for(int i=lp[p1];i<=rp[p2];i++)
70             res+=(a[i].id<=r&&a[i].id>=l&&a[i].val+tag[p1]>=x);
71     }
72     else
73     {
74         for(int i=p1+1;i<=p2-1;i++)
75             res+=work(lp[i],rp[i],x);
76         res+=query(l,rp[p1],x);
77         res+=query(lp[p2],r,x);
78     }
79     return res;
80 }
81 int main()
82 {
83     ios::sync_with_stdio(false);
84     cin.tie(0);cout.tie(0);
85     cin>>n>>q;
86     for(int i=1;i<=n;i++)
87         cin>>a[i].val,a[i].id=i;
88     pre_work();
89     for(int i=1;i<=q;i++)
90     {
91         cin>>opt>>L>>R>>x;
92         if(opt=='M')    update(L,R,x);
93         if(opt=='A')    cout<<query(L,R,x)<<'\n';
94     }
95     return 0;
96 }

四、写题心得:

  大概这个排序不是很容易想到吧?分块第一题,做个纪念。也收获了一点经验:

  $1、分块的预处理方式\ => Exp++!$

  $2、sort(a,b)处理的范围是 [a,b) => Exp++!$

  $3、二分时如果使用\ l\ ,\ r\ 变量,注意它们的值会改变 ,应该新定义一个变量=> Exp++!$

  加油!拜拜!

标签:opt,p1,val,int,题解,P2801,魔法,mid,sqrt
From: https://www.cnblogs.com/yhy-trh/p/P2801.html

相关文章

  • JAVA面试题解惑系列(八)——聊聊基本类型(内置类型)
    关键字:java面试题基本类型intlongbooleanfloatdoublechar作者:臧圩人(zangweiren)基本类型,或者叫做内置类型,是JAVA中不同于类的特殊类型。它们是我们编程中使用最频繁的类型,因此面试题中也总少不了它们的身影,在这篇文章中我们将从面试中常考的几个方面来回顾一......
  • JAVA面试题解惑系列(四)——final、finally和finalize的区别
    关键字:java面试题finalfinallyfinalize作者:臧圩人(zangweiren)final、finally和finalize的区别是什么?这是一道再经典不过的面试题了,我们在各个公司的面试题中几乎都能看到它的身影。final、finally和finalize虽然长得像孪生三兄弟一样,但是它们的含义和用法却是......
  • AtCoder Beginner Contest 305 题解 A - F
    A-WaterStation题目大意找到离给定的数最近的一个\(5\)的倍数输出即可。解题思路我们取这个数对\(5\)的上下界,也就是整数除以\(5\)再乘以\(5\),以及这个数再加上一个\(5\),比较这两数和给定数的距离即可。ACCode#include<iostream>#include<algorithm>#includ......
  • 题解 ABC207F【Tree Patrolling】
    挺简单的树上背包,就是有点难写。设\({dp}_{u,i,x,y}\)表示仅考虑\(u\)的子树内,有\(i\)个节点被控制,\(x\)为节点\(u\)是否有警卫,\(y\)为节点\(u\)是否被控制。(其实所有\(x=1,y=0\)的状态都没用,但我懒得管了。)每个点\(u\)的初始值为\({dp}_{u,0,0,0}={dp}_{u,1,1......
  • 【题解】[六省联考 2017] 寿司餐厅
    题目描述:Kiana最近喜欢到一家非常美味的寿司餐厅用餐。每天晚上,这家餐厅都会按顺序提供\(n\)种寿司,第\(i\)种寿司有一个代号\(a_i\)和美味度\(d_{i,i}\),不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,Kiana也可以无限次取寿司来吃,但每种寿司每次只能......
  • 【题解】[JLOI2014]镜面通道
    题目描述:在一个二维平面上,有一个镜面通道,由镜面\(AC,BD\)组成,\(AC,BD\)长度相等,且都平行于\(x\)轴,\(B\)位于\((0,0)\)。通道中有\(n\)个外表面为镜面的光学元件,光学元件\(\alpha\)为圆形,光学元件\(\beta\)为矩形(这些元件可以与其他元件和通道有交集,具体看下图)。......
  • HarmonyOS在SDK9版本下FA模型geolocation无法定位问题解决
    问题描述已经在config.json中加入了ohos.permission.LOCATION权限声明,但是在实际开发中,我使用geolocation.getCurrentLocation().then((result)=>{this.locationInfo=JSON.stringify(result);this.blog.setTitle(this.locationInfo);});获取位置信息得不到结果我使用的......
  • POJ2117 Electricity 题解 tarjan点双连通分量 割点
    题目链接:http://poj.org/problem?id=2117题目大意:给定一个由\(n\)个点\(m\)条边构成的无向图,请你求出该图删除一个点之后,连通块最多有多少。解题思路:tarjan,判断\(u\)的子节点有几个\(v\)满足\(low[v]\gedfn[u]\)就是答案,但是同时如果\(u\)不是这个dfs树的根节......
  • CF1697F 题解
    题意传送门构造一个长度为\(n\)的数列\(a\),满足\(1\lea_i\lek\)且\(a\)不降,以及\(m\)个约束,有三种情况:1ix,表示\(a_i\nex\)2ijx,表示\(a_i+a_j\lex\)3ijx,表示\(a_i+a_j\gex\)无解输出\(-1\)。\(1\len,m\le2\times10^4,2\lek\le10\)。题......
  • 【Android】ListView与Button的共存问题解决
    【Android】ListView与Button的共存问题解决这两天在捣鼓ListViewwidget,为了在ListView中加入Button这类的有“点击”事件的widget,请教了不少高手,感谢LandMark对我的认真讲解,下面把解决过程描述一下。 ListView和其它能触发点击事件的widget无法一起正常工作的......