第十分块。
看到题第一反应肯定是想把询问按 \(x\) 排序。
但是有修改。
假设能较快地支持一次修改，那么如果直接暴力类似带修莫队在上一次询问的基础上转移的话，复杂度是 \(O(m^2)\) 的。
这启发我们什么？
莫队。
然而，虽然它是标算，但我还不会（
所以把操作分块。每 \(O(\sqrt m)\) 个操作处理一次。
于是现在需要支持较快地修改。
假如没有额外的修改操作，我们需要支持的就是维护一个 \(01\) 序列，支持把 \(0\) 变成 \(1\)，询问区间内所有极长 \(1\) 的连续段的子区间个数之和。
考虑分块。
这个分块相对比较简单：只需要考虑维护所有块内的极长连续段，在左端点处记录右端点，右端点处记录左端点，并记录块内的答案。
这里为了便于区间询问，记录块内答案时不记录在块的边界上的连续段的贡献。
然后区间询问就是一个经典 PJ 操作。
这个分块不难实现 \(O(1)\) 修改 \(O(\sqrt n)\) 询问，而同时也应当注意到我们的修改次数大致是 \(O(m \sqrt m)\)，所以这里达成了一种平衡。
下一个问题：额外的修改可能把 \(1\) 变成 \(0\)，怎么办呢？
注意到最多只有 \(O(\sqrt m)\) 次本质不同的额外的修改，然后又发现这个分块容易支持撤销上一次操作。
于是可以得到这样一个想法：在一般地按照权值把 \(0\) 变成 \(1\) 的过程中，不考虑被修改的位置；在处理询问时暴力判断每个被修改的位置是否需要变为 \(1\)，回答询问后撤回。
这样就可以了。
时间复杂度 \(O(n \sqrt n)\)，视 \(n,m\) 同阶（其实是懒得算了吧）。
然而卡常力度略微有点大。
感谢松式基排，它实在是太香了！
代码： 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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}
const int N = 3e5;
const int BLK = 700;
const int CNT = N / BLK + 1;
const int LIM = 2500;
int n,m;
int block,lim;
int a[N + 5],pos[N + 5];
int vis[N + 5];
vector<int> modified;
struct note
{
int x,v;
} b[N + 5];
struct s_change
{
int x,v;
} chg[LIM + 5];
struct s_query
{
int l,r,v,id,t;
} qry[LIM + 5];
int chg_tot,qry_tot;
long long ans[LIM + 5];
namespace BLOCK
{
int a[N + 5],w[N + 5];
long long sum[CNT + 5];
int tot;
struct note
{
int x,l,r;
long long s;
} temp[LIM + 5];
inline void update(int x,int flag = 0)
{
register const int p = pos[x],L = (p - 1) * block + 1,R = min(p * block,n);
register const int l = L < x && w[x - 1] ? w[x - 1] : x,r = R > x && w[x + 1] ? w[x + 1] : x;
flag && (temp[++tot] = (note){x,l,r,sum[p]},1);
a[x] = 1;
L < x && (w[x - 1] = 0),x < R && (w[x + 1] = 0),
w[l] = r,w[r] = l,
L < l && (sum[p] -= (long long)(x - l) * (x - l + 1) >> 1),
R > r && (sum[p] -= (long long)(r - x) * (r - x + 1) >> 1),
L < l && R > r && (sum[p] += (long long)(r - l + 1) * (r - l + 2) >> 1);
}
inline void cancel()
{
for(;tot;--tot)
{
register const int x = temp[tot].x,l = temp[tot].l,r = temp[tot].r;
register const int p = pos[x],L = (p - 1) * block + 1,R = min(p * block,n);
w[x] = a[x] = 0,
l < x && (w[l] = x - 1,w[x - 1] = l),
r > x && (w[r] = x + 1,w[x + 1] = r),
sum[p] = temp[tot].s;
}
}
inline long long query(int l,int r)
{
long long ret = 0;
register int cur = 0;
for(register int i = l;i <= min(pos[l] * block,r);++i)
a[i] && !cur && (cur = i),
!a[i] && cur && (ret += (long long)(i - cur) * (i - cur + 1) >> 1,cur = 0);
if(pos[l] ^ pos[r])
{
for(register int p = pos[l] + 1,L,R,x;p < pos[r];++p)
{
L = (p - 1) * block + 1,R = min(p * block,n);
ret += sum[p];
if(w[L] ^ R)
!a[L] && cur && (ret += (long long)(L - cur) * (L - cur + 1) >> 1),
a[L] && cur && (ret += (long long)(w[L] - cur + 1) * (w[L] - cur + 2) >> 1),
a[L] && !cur && (ret += (long long)(w[L] - L + 1) * (w[L] - L + 2) >> 1),
cur = w[R];
else
!cur && (cur = L);
}
for(register int i = (pos[r] - 1) * block + 1;i <= r;++i)
a[i] && !cur && (cur = i),
!a[i] && cur && (ret += (long long)(i - cur) * (i - cur + 1) >> 1,cur = 0);
}
cur && (ret += (long long)(r - cur + 1) * (r - cur + 2) >> 1);
return ret;
}
inline void clear()
{
memset(a,0,sizeof a),memset(w,0,sizeof w),memset(sum,0,sizeof sum);
}
}
namespace SORT
{
const int B = 9;
const int W = 1 << B;
int a[N + 5],b[N + 5];
int c[W + 5];
template<class T>
inline void sort(T *w,int n)
{
T temp[N + 5];
int *x = a,*y = b;
for(register int i = 1;i <= n;++i)
x[i] = i,temp[i] = w[i];
for(register int r = 0;1 << (r * B) <= N;++r)
{
for(register int i = 0;i < W;++i)
c[i] = 0;
for(register int i = 1;i <= n;++i)
++c[(w[x[i]].v >> (r * B)) & (W - 1)];
for(register int i = 1;i < W;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
y[c[(w[x[i]].v >> (r * B)) & (W - 1)]--] = x[i];
swap(x,y);
}
for(register int i = 1;i <= n;++i)
w[i] = temp[x[i]];
}
}
void solve()
{
register int cnt = 0;
for(register int i = 1;i <= n;++i)
!vis[i] && (b[++cnt] = (note){i,a[i]},1);
SORT::sort(b,cnt),SORT::sort(qry,qry_tot);
register int t = 0;
for(register int i = 1,j = 1;i <= qry_tot;++i)
{
for(;j <= cnt && b[j].v <= qry[i].v;++j)
BLOCK::update(b[j].x);
for(;t < qry[i].t;)
++t,swap(a[chg[t].x],chg[t].v);
for(;t > qry[i].t;)
swap(a[chg[t].x],chg[t].v),--t;
for(register int x : modified)
a[x] <= qry[i].v && (BLOCK::update(x,1),1);
ans[qry[i].id] = BLOCK::query(qry[i].l,qry[i].r);
BLOCK::cancel();
}
for(;t < chg_tot;)
++t,swap(a[chg[t].x],chg[t].v);
for(register int i = 1;i <= qry_tot;++i)
printf("%lld\n",ans[i]);
}
int main()
{
read(n),read(m),block = BLK,lim = LIM;
for(register int i = 1;i <= n;++i)
read(a[i]),pos[i] = (i - 1) / block + 1;
int op,x,y,k;
for(register int i = 1;i <= m;++i)
{
read(op),read(x),read(y);
if(op == 2)
read(k),qry[++qry_tot] = (s_query){x,y,k,qry_tot,chg_tot};
else
chg[++chg_tot] = (s_change){x,y},!vis[x] && (modified.push_back(x),vis[x] = 1);
if(!(i % lim) || i == m)
solve(),
qry_tot = chg_tot = 0,memset(vis,0,sizeof vis),BLOCK::clear(),modified.clear();
}
}