一、题目描述:
给你一个长度为 $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