1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
| class SegTree{ long[]tree=new long[100050]; long[]lazyadd=new long[100050]; long[]lazymut=new long[100050]; long[]lazyset=new long[100050]; int n; long NINF=-0x3f3f3f3f3f3f3f3fL; void init(int n_){ this.n=1; while(n<n_){ n*=2; } Arrays.fill(tree, 0); Arrays.fill(lazyadd, 0); Arrays.fill(lazymut, 1); Arrays.fill(lazyset, NINF); } void pushdown(int num,int l,int r){ if(lazyset[num]!=NINF){ tree[num*2+1]=lazyset[num]; tree[num*2+2]=lazyset[num]; lazyset[num*2+1]=lazyset[num]; lazyset[num*2+2]=lazyset[num]; lazyadd[num*2+1]=0; lazyadd[num*2+2]=0; lazymut[num*2+1]=1; lazymut[num*2+2]=1; lazyset[num]=NINF; } if(lazymut[num]!=1){ tree[num*2+1]*=lazymut[num]; tree[num*2+2]*=lazymut[num]; lazymut[num*2+1]*=lazymut[num]; lazymut[num*2+2]*=lazymut[num]; lazyadd[num*2+1]*=lazymut[num]; lazyadd[num*2+2]*=lazymut[num]; lazymut[num]=1; } if(lazyadd[num]!=0){ tree[num*2+1]+=lazyadd[num]; tree[num*2+2]+=lazyadd[num]; lazyadd[num*2+1]+=lazyadd[num]; lazyadd[num*2+2]+=lazyadd[num]; lazyadd[num]=0; } } void regadd(int l,int r,long add){ add(0,l,r,add,0,n); } void regmut(int l,int r,long mut){ mut(0,l,r,mut,0,n); } void regset(int l,int r,long set){ set(0,l,r,set,0,n); } long regquery(int l,int r){ return query(0,l,r,0,n); } long query(int num,int l,int r,int x,int y){ if(r<=x||l>=y)return NINF; if(l<=x&&r>=y){ return tree[num]; } pushdown(num,x,y); long left=query(num*2+1,l,r,x,(x+y)/2); long right=query(num*2+2,l,r,(x+y)/2,y); return Math.max(left, right); } void mut(int num,int l,int r,long mut,int x,int y){ if(r<=x||l>=y) return; if(l<=x&&r>=y){ tree[num]=tree[num]*mut; if(lazyadd[num]!=0)lazyadd[num]=lazyadd[num]*mut; lazymut[num]=lazymut[num]*mut; return; } pushdown(num,x,y); mut(num*2+1,l,r,mut,x,(x+y)/2); mut(num*2+2,l,r,mut,(x+y)/2,y); tree[num]=Math.max(tree[num*2+1],tree[num*2+2]); } void add(int num,int l,int r,long add,int x,int y){ if(r<=x||l>=y)return; if(l<=x&&r>=y){ tree[num]=tree[num]+add; lazyadd[num]=lazyadd[num]+add; return; } pushdown(num,x,y); add(num*2+1,l,r,add,x,(x+y)/2); add(num*2+2,l,r,add,(x+y)/2,y); tree[num]=Math.max(tree[num*2+1],tree[num*2+2]); } void set(int num,int l,int r,long set,int x,int y){ if(r<=x||l>=y)return; if(l<=x&&r>=y){ tree[num]=set; lazyadd[num]=0; lazymut[num]=1; lazyset[num]=set; return; } pushdown(num,x,y); set(num*2+1,l,r,set,x,(x+y)/2); set(num*2+2,l,r,set,(x+y)/2,y); tree[num]=Math.max(tree[num*2+1],tree[num*2+2]); } }
|