称序列${a_{1},a_{2},…,a_{n}}$的答案为$min_{0le ile n-k}(max_{i<jle i+k}a_{j})$（特别的，若$n<k$则为$infty$）
将序列按$k$分段，每一段长度为$k$（最后一段长度可以小于$k$），那么恰有$lceilfrac{n}{k}ceil$段
考虑维护第$i$段和第$i+1$段拼接成的序列的答案，那么如果相邻两段都全在修改或查询区间内，直接再维护一棵线段树即可（支持区间加和区间取$min$），并对剩下$o(1)$个暴力计算即可（单点修改）
关于如何”暴力计算”，做法如下：
问题即选择第$i$段的一个后缀和第$i+1$段的一个前缀（都可以为空），长度和为$k$并最小化两者的最大值
（另外，如果是查询，还会对其长度有一定限制，但并不影响下面的做法）
显然两者随长度的增长单调不下降，因此即需要找到最短的后缀使得其对应的前缀（长度和为$k$）最大值小于后缀最大值（类似地找到最短的后缀），那么答案即这两个位置
简单的做法即二分+线段树做到$o(log^{2}n)$，但注意到可以对每一段都建一棵线段树，且让两者形态相同（将最后一段长度补至$k$），那么就可以在两棵线段树上一起二分，时间复杂度降为$o(log n)$
最终，总复杂度为$o(qlog n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 3000005 4 #define oo 0x3f3f3f3f 5 #define mid (l+r>>1) 6 int t,n,m,q,p,l,r,x; 7 namespace VAL{ 8 int V,Rt,ls[N],rs[N],tag[N],f[N]; 9 unordered_map<int,int>rt; 10 void init(){ 11 V=Rt=0; 12 rt.clear(); 13 } 14 int New(){ 15 int k=++V; 16 ls[k]=rs[k]=tag[k]=f[k]=0; 17 return k; 18 } 19 void upd(int &k,int x){ 20 if (!k)k=New(); 21 tag[k]+=x,f[k]+=x; 22 } 23 void up(int k){ 24 f[k]=max(f[ls[k]],f[rs[k]])+tag[k]; 25 } 26 void down(int k){ 27 if (!tag[k])return; 28 upd(ls[k],tag[k]); 29 upd(rs[k],tag[k]); 30 tag[k]=0; 31 } 32 void update(int &k,int l,int r,int x,int y,int z){ 33 if ((l>y)||(x>r))return; 34 if (!k)k=New(); 35 if ((x<=l)&&(r<=y)){ 36 upd(k,z); 37 return; 38 } 39 update(ls[k],l,mid,x,y,z); 40 update(rs[k],mid+1,r,x,y,z); 41 up(k); 42 } 43 void get_tag(int k,int l,int r,int x){ 44 if (!k)return; 45 if (l==r){ 46 upd(rt[x],tag[k]),tag[k]=0; 47 return; 48 } 49 down(k); 50 if (x<=mid)get_tag(ls[k],l,mid,x); 51 else get_tag(rs[k],mid+1,r,x); 52 up(k); 53 } 54 int query(int k,int l,int r,int x,int y){ 55 if ((l>y)||(x>r))return -oo; 56 if ((!k)||(x<=l)&&(r<=y))return f[k]; 57 return max(query(ls[k],l,mid,x,y),query(rs[k],mid+1,r,x,y))+tag[k]; 58 } 59 int find(int k1,int k2,int l,int r,int x,int y){ 60 if (l==r)return l; 61 down(k1),down(k2); 62 int xx=max(x,f[rs[k1]]),yy=max(y,f[ls[k2]]); 63 if (xx>=yy)return find(rs[k1],rs[k2],mid+1,r,x,yy); 64 return find(ls[k1],ls[k2],l,mid,xx,y); 65 } 66 void update(int pos,int l,int r,int x){ 67 if (l<=r){ 68 if (!pos)update(Rt,1,n/m,l,r,x); 69 else update(rt[pos],1,m,l,r,x); 70 } 71 } 72 int query(int pos,int l,int r){ 73 if (l>r)return oo; 74 get_tag(Rt,1,n/m,pos),get_tag(Rt,1,n/m,pos+1); 75 l=min(max(find(rt[pos],rt[pos+1],1,m,-oo,-oo),l),r); 76 int ans=max(query(rt[pos],1,m,l,m),query(rt[pos+1],1,m,1,l-1)); 77 if (l<r)ans=min(ans,max(query(rt[pos],1,m,l+1,m),query(rt[pos+1],1,m,1,l))); 78 return ans; 79 } 80 }; 81 namespace ANS{ 82 int V,rt,ls[N],rs[N],tag[N],f[N]; 83 void init(){ 84 V=rt=0; 85 } 86 int New(){ 87 int k=++V; 88 ls[k]=rs[k]=tag[k]=f[k]=0; 89 return k; 90 } 91 void upd(int &k,int x){ 92 if (!k)k=New(); 93 tag[k]+=x,f[k]+=x; 94 } 95 void up(int k){ 96 f[k]=min(f[ls[k]],f[rs[k]])+tag[k]; 97 } 98 void down(int k){ 99 if (!tag[k])return; 100 upd(ls[k],tag[k]); 101 upd(rs[k],tag[k]); 102 tag[k]=0; 103 } 104 void update(int &k,int l,int r,int x,int y){ 105 if (!k)k=New(); 106 if (l==r){ 107 tag[k]=0,f[k]=y; 108 return; 109 } 110 down(k); 111 if (x<=mid)update(ls[k],l,mid,x,y); 112 else update(rs[k],mid+1,r,x,y); 113 up(k); 114 } 115 void update(int &k,int l,int r,int x,int y,int z){ 116 if ((l>y)||(x>r))return; 117 if (!k)k=New(); 118 if ((x<=l)&&(r<=y)){ 119 upd(k,z); 120 return; 121 } 122 update(ls[k],l,mid,x,y,z); 123 update(rs[k],mid+1,r,x,y,z); 124 up(k); 125 } 126 int query(int k,int l,int r,int x,int y){ 127 if ((l>y)||(x>r))return oo; 128 if ((!k)||(x<=l)&&(r<=y))return f[k]; 129 return min(query(ls[k],l,mid,x,y),query(rs[k],mid+1,r,x,y))+tag[k]; 130 } 131 void update(int pos,int x){ 132 update(rt,1,n/m,pos,x); 133 } 134 void update(int l,int r,int x){ 135 if (l<=r)update(rt,1,n/m,l,r,x); 136 } 137 int query(int l,int r){ 138 if (l>r)return oo; 139 return query(rt,1,n/m,l,r); 140 } 141 }; 142 int bl(int k){ 143 return (k+m-1)/m; 144 } 145 int st(int k){ 146 return (k-1)*m+1; 147 } 148 int ed(int k){ 149 return k*m; 150 } 151 void update(int l,int r,int x){ 152 int ll=bl(l),rr=bl(r); 153 if (ll==rr)VAL::update(ll,l-st(ll)+1,r-st(ll)+1,x); 154 else{ 155 VAL::update(0,ll+1,rr-1,x); 156 VAL::update(ll,l-st(ll)+1,m,x); 157 VAL::update(rr,1,r-st(rr)+1,x); 158 ANS::update(ll+1,rr-2,x); 159 } 160 if (ll>1)ANS::update(ll-1,VAL::query(ll-1,1,m)); 161 if (ll<n/m)ANS::update(ll,VAL::query(ll,1,m)); 162 if (ll<rr-1)ANS::update(rr-1,VAL::query(rr-1,1,m)); 163 if ((ll<rr)&&(rr<n/m))ANS::update(rr,VAL::query(rr,1,m)); 164 } 165 int query(int l,int r){ 166 int ll=bl(l),rr=bl(r+1),ans=ANS::query(ll+1,rr-2); 167 if (ll+1==rr)return min(ans,VAL::query(ll,l-st(ll)+1,r-st(rr)+2)); 168 return min(ans,min(VAL::query(ll,l-st(ll)+1,m),VAL::query(rr-1,1,r-st(rr)+2))); 169 } 170 int main(){ 171 scanf("%d",&t); 172 while (t--){ 173 scanf("%d%d%d",&n,&m,&q); 174 n=(n+m-1)/m*m; 175 VAL::init(),ANS::init(); 176 for(int i=1;i<=q;i++){ 177 scanf("%d%d%d",&p,&l,&r); 178 if (p==1){ 179 scanf("%d",&x); 180 update(l,r,x); 181 } 182 if (p==2)printf("%d ",query(l,r)); 183 } 184 } 185 return 0; 186 }
View Code