https://www.luogu.org/PRoblem/show?pid=2801#sub 思路就是分块嘛； 第一次分块题啊，那讲的细一点吧； 首先堆这些数分块； 这里我的长度是sqrt(n); 分块的长度根据题目而定； 往往推出一个公式，然后根据这个公式求出最优的长度； 这个就是数学范畴； 我的strcut l，r是区间范围，len是长度（在这一题里无用），tag是加法标记
struct kuai{ int l,r,len,tag;}c[1010];分块的思想拉，就是区间内包含整个块的就整个块地操作， 不是整个快的最多就两个部分，操作区间的左右两端，直接暴力；
我的主程序 a[]是原始数列，不改变； b[]是分块序列，所有操作都在b[]进行；
int a[1000001],b[1000001];int ll,n,m,x,y,z,ans;char cc;int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; fenkuai(); while(m--){ cin>>cc; scanf("%d%d%d",&x,&y,&z); if(cc=='A')outit(x,y,z);else change(x,y,z); }}这种复杂的题目，主程序轻巧一点，而且一定要写好一个模块就调试一遍，千万要小心，不然全打好了调试得要死；
我的分块函数 ll就是快的数量
void fenkuai(){ int k=sqrt(n); int l=1; while(l<=n){ c[++ll].l=l; c[ll].r=min(n,l+k-1); c[ll].len=c[ll].r-c[ll].l+1; sort(b+c[ll].l,b+c[ll].r+1); l+=k; }}我们将每个块都排序；这样就方便二分找答案； findans的函数 就是把x,y分为左中右三个区间
void outit(int x,int y,int z){ int ans=0; for(int i=1;i<=ll;i++) if(x<=c[i].l&&c[i].r<=y)ans+=er(i,z);else if(c[i].l<=x&&x<=c[i].r)ans+=BL(i,x,c[i].r,z);else if(c[i].l<=y&&y<=c[i].r)ans+=BL(i,c[i].l,y,z); printf("%d/n",ans);}二分
int er(int num,int z){ int l=c[num].l,r=c[num].r,ans=1e9; while(r>=l){ int mid=(l+r)/2; if(b[mid]+c[num].tag>=z){//要加上 c[num].tag ans=min(ans,mid);r=mid-1; }else l=mid+1; } if(ans==1e9)return 0;//这个特判容易忘 return c[num].r-ans+1;}暴力 暴力部分要在a数组里找
int BL(int num,int x,int y,int z){ int ans=0; for(int i=x;i<=y;i++)if(a[i]+c[num].tag>=z)ans++; return ans;}然后就是改变部分
void change(int x,int y,int z){ for(int i=1;i<=ll;i++) if(x<=c[i].l&&c[i].r<=y)c[i].tag+=z;else if(c[i].l<=x&&x<=c[i].r)BLchange(i,x,c[i].r,z);else if(c[i].l<=y&&y<=c[i].r)BLchange(i,c[i].l,y,z);}void BLchange(int num,int x,int y,int z){ for(int i=c[num].l;i<=c[num].r;i++){ b[i]=a[i]+c[num].tag; if(x<=i&&i<=y)b[i]+=z; } sort(b+c[num].l,b+c[num].r+1);}总得来说，复杂的题目要小心，思路明确，打好一个模块调试一个； 代码
#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define Ll unsigned long longusing namespace std;struct kuai{ int l,r,len,tag;}c[1010];int a[1000001],b[1000001];int ll,n,m,x,y,z,ans;char cc;void fenkuai(){ int k=sqrt(n); int l=1; while(l<=n){ c[++ll].l=l; c[ll].r=min(n,l+k-1); c[ll].len=c[ll].r-c[ll].l+1; sort(b+c[ll].l,b+c[ll].r+1); l+=k; }}int er(int num,int z){ int l=c[num].l,r=c[num].r,ans=1e9; while(r>=l){ int mid=(l+r)/2; if(b[mid]+c[num].tag>=z){//要加上 c[num].tag ans=min(ans,mid);r=mid-1; }else l=mid+1; } if(ans==1e9)return 0;//这个特判容易忘 return c[num].r-ans+1;}int BL(int num,int x,int y,int z){ int ans=0; for(int i=x;i<=y;i++)if(a[i]+c[num].tag>=z)ans++; return ans;}void outit(int x,int y,int z){ int ans=0; for(int i=1;i<=ll;i++) if(x<=c[i].l&&c[i].r<=y)ans+=er(i,z);else if(c[i].l<=x&&x<=c[i].r)ans+=BL(i,x,c[i].r,z);else if(c[i].l<=y&&y<=c[i].r)ans+=BL(i,c[i].l,y,z); printf("%d/n",ans);}void BLchange(int num,int x,int y,int z){ for(int i=c[num].l;i<=c[num].r;i++){ b[i]=a[i]+c[num].tag; if(x<=i&&i<=y)b[i]+=z; } sort(b+c[num].l,b+c[num].r+1);}void change(int x,int y,int z){ for(int i=1;i<=ll;i++) if(x<=c[i].l&&c[i].r<=y)c[i].tag+=z;else if(c[i].l<=x&&x<=c[i].r)BLchange(i,x,c[i].r,z);else if(c[i].l<=y&&y<=c[i].r)BLchange(i,c[i].l,y,z);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i]; fenkuai(); while(m--){ cin>>cc; scanf("%d%d%d",&x,&y,&z); if(cc=='A')outit(x,y,z);else change(x,y,z); }}新闻热点
疑难解答
