虽然本题打着线段树的标签，但 \(10^5\) 的数据范围令我想到了简单粗暴的分块。
- 操作 \(1\)
首先考虑暴力判断并修改每个位置的值，然而这样做会被卡到 \(O(nm)\)。但实际上，需要修改的位置可能不多，也就是会做大量的无用判断。这个时候，我们就可以充分利用分块的特性，记录每个块内 \(a_i \times b_i\) 的最小值，若该最小值比 \(k\) 大，则整个块都无需修改，直接跳过，否则暴力修改，并更新该块的信息。这样做效率得到了极大的提升，\(O(nm)\) 很难跑满。
注意，\(t=0\) 时并不会产生任何操作效果，因此直接忽略即可，运行效率可获得部分的提升。
- 操作 \(2\)
分块的基础操作。直接定位所在的块，暴力修改并更新该块的信息。单次操作时间复杂度为 \(O(\sqrt n)\)。
- 操作 \(3\)
也是分块的基础操作。利用先前已经维护好的信息，直接求和即可。单次操作时间复杂度为 \(O(\sqrt n)\)。
完整代码如下：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 200001
#define int long longusing namespace std;int n,a[N],b[N],tot,x[N],y[N],mi[N],s[N],id[N],ans,len,l,r,k,t,op,lt,rt;inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}return x*f;
}signed main()
{int T;cin >> n >> T;for( int i = 1 ; i <= n ; i ++ )a[i] = read();for( int i = 1 ; i <= n ; i ++ )b[i] = read();len = sqrt( n );l = 1;while( l <= n ){r = min( l + len - 1 , n );tot ++;x[tot] = l,y[tot] = r;mi[tot] = a[l] * b[l];id[l] = tot;s[tot] = a[l] + b[l];for( int i = l + 1 ; i <= r ; i ++ )mi[tot] = min( mi[tot] , a[i] * b[i] ),id[i] = tot,s[tot] += a[i] + b[i];l = r + 1;}while( T -- ){op = read();if( op == 1 ){l = read(),r = read(),k = read(),t = read();if( t == 0 ) continue;lt = id[l];rt = id[r];for( int i = lt ; i <= rt ; i ++ ){if( mi[i] > k ) continue; for( int j = max( x[i] , l ) ; j <= min( y[i] , r ) ; j ++ ){if( a[j] * b[j] <= k ){a[j] += t;b[j] += t;s[i] += t * 2;}}mi[i] = a[x[i]] * b[x[i]];for( int j = x[i] + 1 ; j <= y[i] ; j ++ )mi[i] = min( mi[i] , a[j] * b[j] );}}if( op == 2 ){k = read(),l = read(),r = read();s[id[k]] = s[id[k]] - a[k] + l - b[k] + r;;a[k] = l,b[k] = r;mi[id[k]] = a[x[id[k]]] * b[x[id[k]]];for( int i = x[id[k]] + 1 ; i <= y[id[k]] ; i ++ )mi[id[k]] = min( mi[id[k]] , a[i] * b[i] );}if( op == 3 ){l = read(),r = read();lt = id[l];rt = id[r];ans = 0;for( int i = lt ; i <= rt ; i ++ ){if( l <= x[i] && y[i] <= r ){ans += s[i];continue;}for( int j = max( x[i] , l ) ; j <= min( y[i] , r ) ; j ++ )ans += a[j] + b[j];}printf( "%lld\n" , ans );}}return 0;
}