Skills For A Better Segment Tree

Part 1： Faster

1.非递归线段树

你可以不用zkw，只用每次单点操作时直接像打二分样写下去就好了

以单点求和为例

int Que(int p,int l,int r,int x){ if(l==r) return Sum[p]; int mid=(l+r)>>1; Down(p); if(x<=mid) return Que(p<<1,l,mid,x); else return Que(p<<1|1,mid+1,r,x); }//递归 int Que(int x){ int p=1,l=1,r=n,mid; while(l!=r) { mid=(l+r)>>1; if(x<=mid) r=mid,p=p<<1|1; else l=mid+1,p=p<<1; } return Sum[p]; }//非递归

当然你可以花一些时间之间去学zkw

2.标记永久化

当操作只有区间修改和单点查询时，可以用（事实上这是一种很有通用的技巧）

查询时直接将遇到的点的Sum值累和过来

void Upd(int p,int l,int r,int ql,int qr,int x){ if(l==ql&&r==qr) { Sum[p]+=(r-l+1)*x; tag[p]+=x; return; } Down(p); int mid=(l+r)>>1; if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x); else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x); else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x); Sum[p]=Sum[p<<1]+Sum[p<<1|1]; } int Que(int p,int l,int r,int x){ if(l==r) return Sum[p]; int mid=(l+r)>>1; Down(p); if(x<=mid) return Que(p<<1,l,mid,x); else return Que(p<<1|1,mid+1,r,x); } //普通标记法 void Upd(int p,int l,int r,int ql,int qr,int x){ if(l==ql&&r==qr) { Sum[p]+=(r-l+1)*x; return; } Down(p); int mid=(l+r)>>1; if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x); else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x); else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x); } void Que(int p,int l,int r,int x,int &res){ res+=Sum[p]; if(l==r) return; int mid=(l+r)>>1; if(x<=mid) Que(p<<1,l,mid,x,res); else Que(p<<1|1,mid+1,r,x,res); } //标记永久化 //注意不要Up

\[ \ \]

\[ \ \]

\[ \ \]

Part 2：Useful

(当你做了一道dp题,发现自己只会打暴力怎么办？线段树不就是了!)

1.区间取模操作

将一个区间\([L,R]\)的数对\(x\)取模

发现性质当\(a[i]>=x\)时,\(a[i] \ \ mod \ \ x \leq \frac {a[i]}2\)

因为当\(a[i] < x*2\)时，\(a[i] \ \ mod \ \ x= a[i]-x < a[i]/2\)

当\(a[i] \geq x*2\)时，\(a[i] \ \ mod \ \ x<=x<=\frac{a[i]}2\)

所以直接存一下最大值，大于等于x时就递归下去，复杂度\(log^2 n\)

void Upd(int p,int l,int r,int ql,int qr,int x) { if(l==r) { ma[p]%=x; s[p]=is[ma[p]]; return; } int mid=(l+r)>>1; if(ql==l&&qr==r) { if(ma[p<<1]>=x) Upd(p<<1,l,mid,ql,mid,x); if(ma[p<<1|1]>=x) Upd(p<<1|1,mid+1,r,mid+1,qr,x); } else { if(qr<=mid) Upd(p<<1,l,mid,ql,qr,x); else if(ql>mid) Upd(p<<1|1,mid+1,r,ql,qr,x); else Upd(p<<1,l,mid,ql,mid,x),Upd(p<<1|1,mid+1,r,mid+1,qr,x); } ma[p]=max(ma[p<<1],ma[p<<1|1]); s[p]=s[p<<1]+s[p<<1|1]; }

2.内外标记结合

当你的标记在线段树上不好处理时，可以选择在整个序列上操作，把标记存在外面

如\(Set(a[1..n])=x-a[1..n]\)

可以在整个序列外面记录，将整个序列符号取反，再加x

3.整体偏移大法

当你遇到这样一个dp

\[ dp[i][j]=dp[i-1][j-x]\]

如何搞？直接在序列外面记录偏移量\(d\)，保留线段树中原来节点的权值

其实这时一个映射的思想

初始情况下$i - > i $

偏移后\(i->i+x\)

但是偏移后值域改变？

不，你只用在刚开始时整体值域弄大一点就好了

真的不行我们还有动点线段树啊

事实上这只是一种简单的偏移，它还可以完成更多操作

如\(dp[i][j]=dp[i-1][x-j]\)

只用在偏移上乘上一个系数就好了

注意偏移后，查询\(L,R\)时，要带入系数算出原来的位置,解个方程就好了

是不是很\(easy\)!

HDU6728

这题我就是暴力搞过去的

const int N=3e3+10,K=230,P=1e9+7; const ll L=-1e11,R=1e11; int n; ll c[N]; int cnt; int s[N*K],t1[N*K],t2[N*K]; int ls[N*K],rs[N*K]; void Down(int p,ll l,ll r){ ll mid=(l+r)>>1; if(~t1[p]) { t1[rs[p]]=t1[p]; t1[ls[p]]=t1[p]; t2[ls[p]]=t2[rs[p]]=0; s[ls[p]]=1ll*t1[p]*((mid-l+1)%P)%P; s[rs[p]]=1ll*t1[p]*((r-mid)%P)%P; t1[p]=-1; } if(t2[p]) { (t2[rs[p]]+=t2[p])%=P; (t2[ls[p]]+=t2[p])%=P; (s[ls[p]]+=1ll*t2[p]*((mid-l+1)%P)%P)%=P; (s[rs[p]]+=1ll*t2[p]*((r-mid)%P)%P)%=P; t2[p]=0; } } void Set(int p,ll l,ll r,ll ql,ll qr,int x){ x%=P; if(ql>qr) return; if(l==ql&&r==qr){ s[p]=1ll*(r-l+1)%P*x%P; t1[p]=x; t2[p]=0; return; } if(!ls[p]) ls[p]=++cnt; if(!rs[p]) rs[p]=++cnt; Down(p,l,r); ll mid=(l+r)>>1; if(qr<=mid) Set(ls[p],l,mid,ql,qr,x); else if(ql>mid) Set(rs[p],mid+1,r,ql,qr,x); else Set(ls[p],l,mid,ql,mid,x),Set(rs[p],mid+1,r,mid+1,qr,x); s[p]=(s[ls[p]]+s[rs[p]])%P; } void Upd(int p,ll l,ll r,ll ql,ll qr,int x){ if(ql>qr) return; if(l==ql&&r==qr){ (s[p]+=(r-l+1)%P*x%P)%=P; (t2[p]+=x)%=P; return; } if(!ls[p]) ls[p]=++cnt; if(!rs[p]) rs[p]=++cnt; Down(p,l,r); ll mid=(l+r)>>1; if(qr<=mid) Upd(ls[p],l,mid,ql,qr,x); else if(ql>mid) Upd(rs[p],mid+1,r,ql,qr,x); else Upd(ls[p],l,mid,ql,mid,x),Upd(rs[p],mid+1,r,mid+1,qr,x); s[p]=(s[ls[p]]+s[rs[p]])%P; } ll Que(int p,ll l,ll r,ll ql,ll qr) { if(ql>qr) return 0; if(l==ql&&r==qr) return s[p]%=P; if(!ls[p]) ls[p]=++cnt; if(!rs[p]) rs[p]=++cnt; Down(p,l,r); ll mid=(l+r)>>1; if(qr<=mid) return Que(ls[p],l,mid,ql,qr); else if(ql>mid) return Que(rs[p],mid+1,r,ql,qr); else return (Que(ls[p],l,mid,ql,mid)+Que(rs[p],mid+1,r,mid+1,qr))%P; } int main(){ rep(kase,1,rd()) { cnt=1; memset(ls,0,sizeof ls); memset(rs,0,sizeof rs); memset(t2,0,sizeof t2); memset(t1,-1,sizeof t1); memset(s,0,sizeof s); n=rd(); rep(i,2,n) c[i]=rd(); Upd(1,L,R,1,R,1); ll fl=1,d=0; rep(i,2,n) { ll t1,t2; t1=(1-d)*fl,t2=(c[i]-d)*fl; ll sum; if(fl==1) sum=Que(1,L,R,t1,t2); else sum=Que(1,L,R,t2,t1); ll t=Que(1,L,R,t2,t2); ll tmp=-d/fl; Set(1,L,R,tmp,tmp,sum); t2=(c[i]-1-d)*fl; if(fl==1) { Set(1,L,R,L,tmp-1,0); Set(1,L,R,t2+1,R,0); } else { Set(1,L,R,L,t2-1,0); Set(1,L,R,tmp+1,R,0); } if(fl==1) { Upd(1,L,R,t1,t2,t); } else Upd(1,L,R,t2,t1,t); fl=-fl; d=c[i]-d; if(d>=R||d<=L) while(1); } ll ans=Que(1,L,R,L,R)%P; ans=(ans%P+P)%P; printf("%lld\n",ans); } }

转载于:https://www.cnblogs.com/chasedeath/p/11446631.html

相关资源：JAVA上百实例源码以及开源项目