分块入门9题
T1：
入门题，不写了
T2：区间加，区间求小于某数的元素个数
修改：大块打标记，小块先把块标记下传，然后再加，最后排序
查询：由于块内是排完序的，大块二分，小块暴力统计
T3：区间加，查前驱
两种写法
第一种：同2，排序+二分
修改：同2
查询：二分
第二种：用set维护
修改：大块标记，小块拿出来修改，注意删除操作要先查迭代器再删，以免直接删除一个值将所有的同值的所有数删除
查询：二分
T4：区间加，区间求和
非分块：线段树
分块：
整体跟1没区别
修改：同1
查询：大块直接加维护的数组，小块暴力加
T5：区间开根，区间查询
性质：发现 (1e9) 开五次就到了1，所以暴力下压的
非分块：线段树
分块：
修改：前几次暴力下压，直到块内都为1
查询：乱搞，有 (tag=1) 块贡献为块的 (size) ，否则暴力统计
带修的以后再补
T6:单点插值，单点查询
非分块：用链表直接搞
暴力分块：每个块开个vector，二分插入，能A
正解分块貌似是每查一个值调整每个块的左右边界
T7：区间乘区间加单点查
非分块：线段树
分块：区间加加强版，调起来比较费劲
开两个标记，乘和加都是大块都是打标记，小块要把所有标记下传
inline void Build(){
int maxe=sqrt(n+0.5);
for(register int i=1;i<=n;++i){
belong[i]=(i-1)/maxe+1;
if(!L[belong[i]])L[belong[i]]=i;
R[belong[i]]=i;sum[belong[i]]+=a[i];sum[belong[i]]%=mol;
size[belong[i]]++;
mul[belong[i]]=1;
maxs=max(maxs,belong[i]);
}
}
inline void modify1(int s,int t,int w){//mul
if(belong[s]!=belong[t]){
modify1(s,R[belong[s]],w),modify1(L[belong[t]],t,w);
for(int i=belong[s]+1;i<belong[t];i++){
sum[i]*=w,add[i]*=w,mul[i]*=w;
sum[i]%=mol,add[i]%=mol,mul[i]%=mol;
}
}else{
for(int i=L[belong[s]];i<=R[belong[s]];i++)a[i]=(1LL*a[i]*mul[belong[i]]%mol+add[belong[i]])%mol;
add[belong[s]]=0;mul[belong[s]]=1;
for(int i=s;i<=t;i++){
sum[belong[s]]-=a[i];a[i]*=w;sum[belong[s]]+=a[i];a[i]%=mol;
}
}
}
inline void modify2(int s,int t,int w){//add
if(belong[s]!=belong[t]){
modify2(s,R[belong[s]],w),modify2(L[belong[t]],t,w);
for(int i=belong[s]+1;i<belong[t];i++){
sum[i]+=w*size[i]%mol,add[i]+=w;
sum[i]%=mol;add[i]%=mol;
}
}else{
for(int i=L[belong[s]];i<=R[belong[s]];i++)a[i]=(1LL*a[i]*mul[belong[i]]%mol+add[belong[i]])%mol;
add[belong[s]]=0;mul[belong[s]]=1;
for(int i=s;i<=t;i++){
sum[belong[s]]-=a[i];a[i]+=w;sum[belong[s]]+=a[i];a[i]%=mol;
}
}
}
inline void query(register int s){
ans=(a[s]*mul[belong[s]]%mol+add[belong[s]])%mol;
}
T8：区间覆盖查元素个数
非分块：珂朵莉处理区间推平
分块：
暴力思路：对每个块开桶打标记，发现unorderedmap都只有三十分
正解：看题解了，暴力下压，时间复杂度是对的
——待续——