P3373 【模板】线段树 2
题目要求支持区间加，区间乘，所以就打两个 \(lazy\_tag\) ，然后 \(push\_down\) 的时候先乘后加即可。
然后注意乘法的 \(lazy\_tag\) 初始值为 \(1\) 即可。
\(code:\)
ll n,m,mod,w[100005],x,y,k;int tmp;
struct tree{
ll w,lazy1,lazy2,l,r;//lazy1表示加法懒标记，lazy2表示乘法懒标记
};tree a[400005];
void build(ll p,ll l,ll r){
a[p].lazy2=1;a[p].l=l;a[p].r=r;
if(l==r)
a[p].w=w[r]%mod;
else{
ll mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
a[p].w=(a[p*2].w+a[p*2+1].w)%mod;
}
}
void use_lazy(ll p){
a[p*2].w=((a[p*2].w*a[p].lazy2)%mod+((a[p*2].r-a[p*2].l+1)*a[p].lazy1)%mod)%mod;//先乘后加
a[p*2+1].w=((a[p*2+1].w*a[p].lazy2)%mod+((a[p*2+1].r-a[p*2+1].l+1)*a[p].lazy1)%mod)%mod;//先乘后加
a[p*2].lazy2=(a[p*2].lazy2*a[p].lazy2)%mod;
a[p*2+1].lazy2=(a[p*2+1].lazy2*a[p].lazy2)%mod;
a[p*2].lazy1=(a[p].lazy1+(a[p].lazy2*a[p*2].lazy1)%mod)%mod;//因为后加的数不能再乘，所以乘前加的数
a[p*2+1].lazy1=(a[p].lazy1+(a[p].lazy2*a[p*2+1].lazy1)%mod)%mod;//因为后加的数不能再乘，所以乘前加的数
a[p].lazy1=0;a[p].lazy2=1;
}
void add(ll p,ll l,ll r,ll w){
if(a[p].l>=l&&a[p].r<=r){
a[p].w=(a[p].w+(a[p].r-a[p].l+1)*w)%mod;
a[p].lazy1=(a[p].lazy1+w)%mod;
return ;
}
use_lazy(p);
ll mid=(a[p].l+a[p].r)>>1;//注意mid是线段树的中点，而不是修改区间的中点（下同）
if(mid>=l)
add(p*2,l,r,w);
if(mid<r)
add(p*2+1,l,r,w);
a[p].w=(a[p*2].w+a[p*2+1].w)%mod;
}
void c(ll p,ll l,ll r,ll w){
if(a[p].l>=l&&a[p].r<=r){
a[p].w=(a[p].w*w)%mod;
a[p].lazy2=(a[p].lazy2*w)%mod;
a[p].lazy1=(a[p].lazy1*w)%mod;//因为后加的数不能再乘，所以乘前加的数
return ;
}
use_lazy(p);
ll mid=(a[p].l+a[p].r)>>1;
if(mid>=l)
c(p*2,l,r,w);
if(mid<r)
c(p*2+1,l,r,w);
a[p].w=(a[p*2].w+a[p*2+1].w)%mod;
}
ll ask(ll p,ll l,ll r){
ll re=0;
if(a[p].l>=l&&a[p].r<=r){
re=(re+a[p].w)%mod;
return re;
}
use_lazy(p);
ll mid=(a[p].l+a[p].r)>>1;
if(mid>=l)
re=(re+ask(p*2,l,r))%mod;
if(mid<r)
re=(re+ask(p*2+1,l,r))%mod;
return re;
}
P1471 方差
平均数只需要求出区间和然后除以区间长度即可，但是方差不好直接维护，可以考虑转化。
设平均数为 \(mid\) ，方差为 \(s^2\) ，则：
所以只需要维护区间和，区间平方和即可。
void use_lazy(ll u){
p2[u*2].w+=2*p2[u].lazy*p1[u*2].w+p2[u].lazy*p2[u].lazy*(p2[u*2].r-p2[u*2].l+1);
p2[u*2+1].w+=2*p2[u].lazy*p1[u*2+1].w+p2[u].lazy*p2[u].lazy*(p2[u*2+1].r-p2[u*2+1].l+1);
p2[u*2].lazy+=p2[u].lazy;p2[u*2+1].lazy+=p2[u].lazy;
p2[u].lazy=0;
p1[u*2].w+=p1[u].lazy*(p1[u*2].r-p1[u*2].l+1);
p1[u*2+1].w+=p1[u].lazy*(p1[u*2+1].r-p1[u*2+1].l+1);
p1[u*2].lazy+=p1[u].lazy;p1[u*2+1].lazy+=p1[u].lazy;
p1[u].lazy=0;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lf",&a[i]);
build(1,1,n);
for(int i=1;i<=m;++i){
scanf("%lld",&tmp);
if(tmp==1){
scanf("%lld%lld%lf",&x,&y,&k);
add(1,x,y,k);
}
else if(tmp==2){
scanf("%lld%lld",&x,&y);
printf("%.4lf\n",ask1(1,x,y)/((y-x+1)*1.0));//ask1询问区间和
}
else{
scanf("%lld%lld",&x,&y);
double ans1=ask1(1,x,y);
printf("%.4lf\n",ask2(1,x,y)/((y-x+1)*1.0)-ans1/((y-x+1)*1.0)*ans1/((y-x+1)*1.0));//ask2询问区间平方和
}
}
return 0;
}
P4145 上帝造题的七分钟 2 / 花神游历各国
通过计算器发现， \(1e12\) 的数，最多开六次方就能到 \(1\) ，所以每次只需要暴力开方，然后等开到 \(1\) 时就打上标记，此后开方不再管这个节点。
\(code:\)
void sqrtt(ll u,ll l,ll r){
if(p[u].l==p[u].r){
p[u].w=sqrt(p[u].w);
if(p[u].w==0||p[u].w==1)
p[u].ok=1;
return ;
}
if(p[u].ok)
return ;
ll mid=(p[u].l+p[u].r)>>1;
if(p[u*2].ok==0&&l<=mid)
sqrtt(u*2,l,r);
if(p[u*2+1].ok==0&&mid<r)
sqrtt(u*2+1,l,r);
if(p[u*2].ok&&p[u*2+1].ok)
p[u].ok=1;
p[u].w=p[u*2].w+p[u*2+1].w;
}
CF438D The Child and Sequence
取模有一个性质：①若 \(p<=x\) ，则 \(x\%p<x/2\) ；②若 \(p>x\) ，则 \(x\%p=x\)
因此，我们可以维护区间最大值，当最大值小于模数时，整个区间的值就不会改变；否则，暴力修改这个区间。根据上面的结论，一个区间最多被修改 \(log(x)\) 次，因此复杂度有了保证。
\(code:\)
void use_mod(ll u,ll l,ll r,ll w){
if(p[u].l>=l&&p[u].r<=r&&p[u].maxx<w)
return ;
if(p[u].l>=l&&p[u].r<=r&&p[u].l==p[u].r){
p[u].maxx%=w;p[u].w%=w;
return ;
}
ll mid=(p[u].l+p[u].r)>>1;
if(mid>=l)
use_mod(u*2,l,r,w);
if(mid<r)
use_mod(u*2+1,l,r,w);
p[u].w=p[u*2].w+p[u*2+1].w;
p[u].maxx=max(p[u*2].maxx,p[u*2+1].maxx);
}
P4513 小白逛公园
经典的区间最大子段和问题。
先考虑考虑区间最大子段和怎么维护。设一个区间的最大子段和为 \(maxn\) ，包括左端点的最大子段和为 \(lmax\) ，包含右端点的最大子段和为 \(rmax\) ，区间和为 \(sum\) 。那么 \(maxn([l,r])=max\{maxn([l,mid]),maxn([mid+1,r]),rmax([l,mid])+lmax([mid+1,r])\}\)
那么一个区间的包括左端点或右端点的最大子段和怎么维护？我们以左端点为例。 \(lmax([l,r])=max\{lmax[l,mid],sum[l,mid]+lmax(mid+1,r)\}\) ，右端点同理。
综上，我们需要对区间维护 \(sum,maxn,lmax,rmax\) 四个值。
再考虑询问区间的最大子段和。
我们递归处理。如果当前节点的某个儿子代表的区间包含了询问区间，就递归处理该儿子；否则，就分别处理两个儿子，然后再把两个儿子的信息按照修改的方式合并即可。
\(code:\)
void update(int u){
t[u].w=t[u*2].w+t[u*2+1].w;
t[u].lmax=max(t[u*2].lmax,t[u*2].w+t[u*2+1].lmax);
t[u].rmax=max(t[u*2+1].rmax,t[u*2+1].w+t[u*2].rmax);
t[u].mmax=max(t[u*2].mmax,max(t[u*2+1].mmax,t[u*2].rmax+t[u*2+1].lmax));
return ;
}
node ask(int u,int l,int r){
if(t[u].l>=l&&t[u].r<=r)
return t[u];
int mid=(t[u].l+t[u].r)>>1;
if(mid>=l&&mid<r){
node p=ask(u*2,l,r),q=ask(u*2+1,l,r),s;
s.lmax=max(p.lmax,p.w+q.lmax);
s.rmax=max(q.rmax,q.w+p.rmax);
s.mmax=max(p.mmax,max(q.mmax,p.rmax+q.lmax));
s.w=p.w+q.w;
return s;
}
else if(mid>=l)
return ask(u*2,l,r);
else
return ask(u*2+1,l,r);
}
多倍经验：
P4344 脑洞治疗仪 （代码实现的细节与本题有一些区别，但本质思路一样。）
GSS1 - Can you answer these queries I （本题简化版）
GSS3 - Can you answer these queries III （与本题一模一样）
GSS5 - Can you answer these queries V（多了个分类讨论，其余与本题一模一样）
Fast Matrix Operations
因为行数很小，不多于20行，所以可以开20棵线段树，然后维护区间推平，区间加，区间加，区间最值即可。
void push_down(int u,int ul,int ur){
int mid=(ul+ur)>>1;
if(p[u].lazy2){
p[p[u].l].w=(mid-ul+1)*p[u].lazy1;
p[p[u].l].maxn=p[p[u].l].minn=p[u].lazy1;
p[p[u].r].w=(ur-mid)*p[u].lazy1;
p[p[u].r].maxn=p[p[u].r].minn=p[u].lazy1;
p[p[u].l].lazy1=p[p[u].r].lazy1=p[u].lazy1;
p[p[u].l].lazy2=p[p[u].r].lazy2=1;//这句话必须写在if里边，而不是外边！！！
}
else{
p[p[u].l].w+=(mid-ul+1)*p[u].lazy1;
p[p[u].l].maxn+=p[u].lazy1;p[p[u].l].minn+=p[u].lazy1;
p[p[u].r].w+=(ur-mid)*p[u].lazy1;
p[p[u].r].maxn+=p[u].lazy1;p[p[u].r].minn+=p[u].lazy1;
p[p[u].l].lazy1+=p[u].lazy1;p[p[u].r].lazy1+=p[u].lazy1;
}
p[u].lazy1=p[u].lazy2=0;
}
经验：XOR on Segment （区间异或，可以开20棵线段树，第 \(i\) 棵树表示的是每个数字二进制下第 \(i\) 位是0或1）
P3569 [POI2014] KAR-Cards
首先考虑卡牌只有一面。如果我们维护好了 \([l,mid]\) 和 \([mid+1,r]\) 的信息，那么只需要判断 \(a[mid]\) 与 \(a[mid+1]\) 之间的关系，就能判断 \([l,r]\) 是否能形成单调不降的序列。
再考虑卡牌两面的情况。不妨设 \(ok[0/1][0/1]\) 分别表示某个区间的左端点为上面或下面，右端点为上面或下面时，能不能形成单调上升的序列。
这样更新时只需要分类讨论四种情况即可。
\(code:\)
void push_up(int u){
p[u].a[0]=p[u<<1].a[0];
p[u].a[1]=p[u<<1].a[1];
p[u].b[0]=p[u<<1|1].b[0];
p[u].b[1]=p[u<<1|1].b[1];
p[u].ok[0][0]=p[u].ok[0][1]=p[u].ok[1][0]=p[u].ok[1][1]=0;
if(p[u<<1].b[0]<=p[u<<1|1].a[0]){
p[u].ok[0][0]|=p[u<<1].ok[0][0]&p[u<<1|1].ok[0][0];
p[u].ok[1][0]|=p[u<<1].ok[1][0]&p[u<<1|1].ok[0][0];
p[u].ok[0][1]|=p[u<<1].ok[0][0]&p[u<<1|1].ok[0][1];
p[u].ok[1][1]|=p[u<<1].ok[1][0]&p[u<<1|1].ok[0][1];
}
if(p[u<<1].b[0]<=p[u<<1|1].a[1]){
p[u].ok[0][0]|=p[u<<1].ok[0][0]&p[u<<1|1].ok[1][0];
p[u].ok[1][0]|=p[u<<1].ok[1][0]&p[u<<1|1].ok[1][0];
p[u].ok[0][1]|=p[u<<1].ok[0][0]&p[u<<1|1].ok[1][1];
p[u].ok[1][1]|=p[u<<1].ok[1][0]&p[u<<1|1].ok[1][1];
}
if(p[u<<1].b[1]<=p[u<<1|1].a[0]){
p[u].ok[0][0]|=p[u<<1].ok[0][1]&p[u<<1|1].ok[0][0];
p[u].ok[1][0]|=p[u<<1].ok[1][1]&p[u<<1|1].ok[0][0];
p[u].ok[0][1]|=p[u<<1].ok[0][1]&p[u<<1|1].ok[0][1];
p[u].ok[1][1]|=p[u<<1].ok[1][1]&p[u<<1|1].ok[0][1];
}
if(p[u<<1].b[1]<=p[u<<1|1].a[1]){
p[u].ok[0][0]|=p[u<<1].ok[0][1]&p[u<<1|1].ok[1][0];
p[u].ok[1][0]|=p[u<<1].ok[1][1]&p[u<<1|1].ok[1][0];
p[u].ok[0][1]|=p[u<<1].ok[0][1]&p[u<<1|1].ok[1][1];
p[u].ok[1][1]|=p[u<<1].ok[1][1]&p[u<<1|1].ok[1][1];
}
}
P4198 楼房重建
考虑维护每个位置与 \((0,0)\) 的连线的斜率，答案就是：在 \([1,n]\) 内，选上第一项，每个大于前一项的必须选，否则不选，得到的不减序列长度。
每个区间维护两个值，一个为上述的序列长度（记为 \(len\) ），另一个为区间最大值（记为 \(maxn\) ）。此时的难点是 \(push\_up\) 。
在 \(push\_up\) 时，显然左儿子的不减序列一定在整个区间的不减序列内部，所以只需找到右儿子中第一个大于 \(lson.maxn\) 的数值（记它出现的位置为 \(pos\) ），即可得到答案：\([l,r].len=lson.len+[pos,r].len\)。
\(code:\)
int push_up(int u,double w){
if(p[u].maxn<=w)
return 0;
if(p[u].l==p[u].r)
return p[u].maxn>w;
if(p[u<<1].maxn>w)
return p[u].len-p[u<<1].len+push_up(u<<1,w);
else
return push_up(u<<1|1,w);
}
/*区间更新时这样写：
p[u].maxn=max(p[u<<1].maxn,p[u<<1|1].maxn);
p[u].len=p[u<<1].len+push_up(u<<1|1,p[u<<1].maxn);
*/
P2824 [HEOI2016/TJOI2016] 排序
一个思路特别巧妙的题。
因为对值域为 \([1,n]\) 的区间进行排序比较困难，所以不妨先思考对值域为 \([0,1]\) 的区间进行排序应该如何处理。以升序为例，首先找到区间中 \(1\) 的个数，记为 \(cnt\) ，然后将 \([l,r-cnt]\) 的数推平为 \(0\) ，\([r-cnt+1,r]\) 的数推平为 \(1\) 。接下来考虑将 \([1,n]\) 的数转化为 \([0,1]\) 的数。
二分答案，设当前二分的值为 \(mid\) ，将 \([1,mid-1]\) 的数设为 \(0\) ，将 \([mid,n]\) 的数设为 \(1\) 。在 \(m\) 次操作以后，查询被询问的位置是否为 \(1\) 。如果为 \(1\) ，二分右区间，否则二分左区间。