segment tree beats 练习题

数据结构白学了 补习一下吉司机线段树 这是一道简单的segmenttreebeats入门题 >区间加 >区间对一个数字取max >求一个数字的值是多少以及历史上改变了多少次值 维护区间最小值和区间次小值，打一个神奇的标记表示这个区间的最小值曾经改变过多少次 做区间取max操作按照吉司机线段树的方式进行剪枝 注意一下几点 保证次小值和最小值是不同的 打两个标记，一个是加法标记另一个是取max标记，新增标记的时候不要偷懒 为了避免各种各样的故障，每个点保存一下区间的最小值来自左孩子还是右孩子，这样第3个标记才能下传 ```C #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;typedef long long ll; const ll inf=(1LL<<60);const ll low_inf=(1LL<<50); int n;int m;ll cur;//int TOT; struct linetree { struct data { ll val;int fr; friend bool operator <(data a,data b){return a.val<b.val;} void operator +=(ll del){val+=del;} }mi[N<<2];ll nmi[N<<2]; int v[N<<2];int splb[N<<2];ll to_mi[N<<2];ll add[N<<2]; inline void appadd(int p,ll del) { add[p]+=del;mi[p]+=del;nmi[p]+=del;to_mi[p]+=del; } inline void appmx(int p,ll lim) { mi[p].val=max(lim,mi[p].val); nmi[p]=max(nmi[p],lim);to_mi[p]=max(to_mi[p],lim); } inline void ins(int p,ll val) { // if(val!=0&&val<low_inf)printf("ins %lld %lld %lld\n",val,mi[p].val,nmi[p]); if(mi[p].val>=val) { if(mi[p].val!=val)nmi[p]=mi[p].val; mi[p].val=val; } else if(nmi[p]>=val)nmi[p]=val; } inline void ud(int p,int p1,int p2) { mi[p].val=mi[p1].val;nmi[p]=nmi[p1]; // ll qu[4]={mi[p1].val,nmi[p1],mi[p2].val,nmi[p2] // mi[p].val=qu[0];nmi[p]=qu[1]; ins(p,mi[p2].val);ins(p,nmi[p2]); // if(nmi[p]<low_inf)printf("mi=%lld,nmi=%lld\n",mi[p].val,nmi[p]); if(mi[p].val==mi[p1].val&&mi[p].val==mi[p2].val) mi[p].fr=2; else if(mi[p].val==mi[p1].val)mi[p].fr=0; else mi[p].fr=1; } inline void pd(int p,int p1,int p2) { if(splb[p]) { switch(mi[p].fr) { case 0:{splb[p1]+=splb[p];break;} case 1:{splb[p2]+=splb[p];break;} case 2:{splb[p1]+=splb[p];splb[p2]+=splb[p];break;} }splb[p]=0; } if(add[p]) appadd(p1,add[p]),appadd(p2,add[p]),add[p]=0; if(to_mi[p]>-low_inf) appmx(p1,to_mi[p]),appmx(p2,to_mi[p]),to_mi[p]=-inf; } inline void stadd(int p,int l,int r,int dl,int dr,ll del) { if(l==dl&&r==dr){appadd(p,del);v[p]++;return;} int mid=(l+r)>>1;pd(p,p<<1,p<<1|1); if(dl<mid)stadd(p<<1,l,mid,dl,min(dr,mid),del); if(mid<dr)stadd(p<<1|1,mid,r,max(dl,mid),dr,del); ud(p,p<<1,p<<1|1); } inline void stmx(int p,int l,int r,int dl,int dr,ll lim) { if(l==dl&&dr==r) { // if(nmi[p]==54421679)printf("%d %d,mi=%lld,nmi=%lld,lim=%lld\n",l,r,mi[p].val,nmi[p],lim); if(lim<=mi[p].val)return; if(lim<nmi[p]){splb[p]++;appmx(p,lim);return;} //printf("mi=%lld,nmi=%lld,lim=%lld\n",mi[p].val,nmi[p],lim); //TOT++; } int mid=(l+r)>>1;pd(p,p<<1,p<<1|1); if(dl<mid)stmx(p<<1,l,mid,dl,min(dr,mid),lim); if(mid<dr)stmx(p<<1|1,mid,r,max(dl,mid),dr,lim); ud(p,p<<1,p<<1|1); } inline int qry(int p,int l,int r,int pos) { if(r-l==1) { // printf("%lld ",mi[p].val); cur=mi[p].val; return v[p]+splb[p]; } int mid=(l+r)>>1;pd(p,p<<1,p<<1|1); if(pos<=mid)return v[p]+qry(p<<1,l,mid,pos); else return v[p]+qry(p<<1|1,mid,r,pos); } inline void build(int p,int l,int r,ll* a) { to_mi[p]=-inf; if(r-l==1) { mi[p].val=a[r];nmi[p]=low_inf;return; } int mid=(l+r)>>1; build(p<<1,l,mid,a);build(p<<1|1,mid,r,a); ud(p,p<<1,p<<1|1); } }lt; ll a[N];char mde[N]; ll ans1[N];int ans2[N];int CNT; int main() { //freopen("tst","r",stdin);freopen("my","w",stdout); // freopen("seq3.out","r",stdin); // ++CNT; // while(scanf("%lld%d",&ans1[CNT],&ans2[CNT])!=-1)++CNT; // fclose(stdin);CNT=1; // freopen("seq3.in","r",stdin); //freopen("mtst.txt","w",stdout); freopen("seq.in","r",stdin);freopen("seq.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); lt.build(1,0,n,a); scanf("%d",&m); for(int i=1,l,r,del;i<=m;i++) { //if(i%1000==0)printf("i=%d,ratio=%.3lf\n",i,(double)TOT/i); scanf("%s",mde+1); switch(mde[1]) { case 'A': { scanf("%d%d%d",&l,&r,&del); if(del!=0)lt.stadd(1,0,n,l-1,r,del); // if(i>=5700)printf("Add\n"); break; } case 'M': { scanf("%d%d%d",&l,&r,&del); lt.stmx(1,0,n,l-1,r,del); // if(i>=5700)printf("stmx %d %d %d\n",l,r,del); break; } case 'Q': { scanf("%d",&l); int cur2=lt.qry(1,0,n,l); printf("%lld %d\n",cur,cur2); // if(cur!=ans1[CNT]||cur2!=ans2[CNT]) // { // printf("%lld %d %lld %d\n",cur,cur2,ans1[CNT],ans2[CNT]); // printf("i=%d,m=%d,l=%d,a[l]=%d,Wrong Answer\n",i,m,l,a[l]); //// // return 0;}//int k;while(1)k++;} // ++CNT; break; } } // if(i>=5700) // { // int cur2=lt.qry(1,0,n,7216); // printf("%lld %d\n",cur,cur2); // } } return 0; } ```