本文主要是介绍P2801 教主的魔法 [分块]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
整块打tag , 单块暴力修改
另外开一个数组b 为一块内的a排序后的数组
显然整块修改不会影响排序 , 查询时加上tag就可以
暴力修改a数组 然后重新赋值再排序 , 这样是O()的
查询时块外暴力 , 块内二分就可以了
#include<bits/stdc++.h>
#define N 1000050
#define LL long long
using namespace std;
int read(){int cnt=0; char ch=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}
int n,q,a[N],tot; LL b[N],tag[N];
int pos[N],l[N],r[N];
void build(){int siz = sqrt(n);for(int i=1;i<=n;i++) pos[i] = (i-1)/siz + 1;for(int i=1;i<=n;i+=siz){l[++tot] = i; r[tot] = i + siz - 1;if(i + siz - 1 > n) r[tot] = n;sort(b+l[tot],b+r[tot]+1);}
}
void Modify(int L,int R,int val){int p1 = pos[L] , p2 = pos[R];if(p1==p2){for(int i=L;i<=R;i++) a[i] += val;for(int i=l[p1];i<=r[p1];i++) b[i] = a[i];sort(b+l[p1],b+r[p1]+1);}else if(p1==p2-1){for(int i=L;i<=R;i++) a[i] += val;for(int i=l[p1];i<=r[p2];i++) b[i] = a[i];sort(b+l[p1],b+r[p1]+1);sort(b+l[p2],b+r[p2]+1);}else{for(int i=L;i<=r[p1];i++) a[i] += val;for(int i=l[p2];i<=R;i++) a[i] += val;for(int i=l[p1];i<=r[p1];i++) b[i] = a[i];for(int i=l[p2];i<=r[p2];i++) b[i] = a[i];for(int i=p1+1;i<p2;i++) tag[i] += val;sort(b+l[p1],b+r[p1]+1);sort(b+l[p2],b+r[p2]+1);}
}
int calc(int x,int val){int L=l[x],R=r[x];while(L<R){int mid = (L+R) >> 1;if(b[mid] + tag[x] >= val) R = mid;else L = mid + 1;}if(b[L]+tag[x]<val) return 0;return r[x] - L + 1;
}
int Quary(int L,int R,int val){int p1 = pos[L] , p2 = pos[R];int ans = 0;if(p1==p2){for(int i=L;i<=R;i++)if(b[i] + tag[p1] >= val) ans++;return ans;}else if(p1==p2-1){for(int i=L;i<=r[p1];i++) if(b[i] + tag[p1] >= val) ans++;for(int i=l[p2];i<=R;i++) if(b[i] + tag[p2] >= val) ans++;return ans;}else{for(int i=L;i<=r[p1];i++) if(b[i] + tag[p1] >= val) ans++;for(int i=l[p2];i<=R;i++) if(b[i] + tag[p2] >= val) ans++;for(int i=p1+1;i<p2;i++) ans += calc(i,val);return ans;}
}
int main(){n=read(),q=read();for(int i=1;i<=n;i++) a[i]=b[i]=read();build(); char s[3];while(q--){scanf("%s",s); int x=read(),y=read(),val=read();if(s[0]=='M') Modify(x,y,val);if(s[0]=='A') printf("%d\n",Quary(x,y,val));}return 0;
}
这篇关于P2801 教主的魔法 [分块]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
