P2801 教主的魔法题解-526互联

一、题目描述：

　　给你一个长度为 $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 }