P6578 magic girl website
Given a sequence with a length of \ (n \), the sub interval of the interval \ ([l,r] \) is defined as all intervals in the form of \ ([l',r'] \), which satisfies that \ (l',r' \) is an integer and \ (L \ Le L '\ Le R' \ Le R \).
There are \ (m \) operations:
- 1 x y: change the value of the position \ (x \) to \ (Y \).
- 2 l r x: query how many sub intervals in the interval \ ([l,r] \) have the maximum value less than or equal to \ (x \).
\(1 \leq n,m\leq 3\times 10^5 \), time limit \ (3.50\text{s} \), space limit \ (64\text{MB} \).
sol
The tenth.
Difficulty score: \ (6 \).
For the query, considering the contribution, it is easy to find. Let \ (b[i]=(a[i] \leq x) \), then our problem now is to ask the sum of \ (\ frac{siz \times(siz+1)}{2} \) of all extremely long subintervals of \ (b \) in the interval.
Then consider how to maintain this extremely long sub interval.
Because \ (x \) will change at any time, it is equivalent to that we will modify some points \ (0 \to 1 \) or \ (1 \to 0 \) every time.
For the case of \ (0 \to 1 \), we consider sorting the queries in ascending order of \ (x \), and then we find that the number satisfied will be more and more, and then discuss several cases by category:
- A single interval is added directly.
- On the left of an interval, add directly.
- On the right side of an interval, add directly.
- Connect the two sections and add them directly after modifying the section information.
However, for the case of \ (1 \to 0 \), which may occur during modification, it needs to be considered every time, and the complexity is obviously wrong.
Similar to the idea of rolling back Mo team, turn a thing into one that has not been deleted.
It is easy to find that \ (1 \to 0 \) only occurs in these \ (m \) operations. First empty the modified positions, and then insert these positions in each query, record the changed answers and the number of pointers, and then withdraw after the query. In this way, all these operations become to replace \ (0 \) with \ (0 \) or \ (1 \), which can be maintained.
However, we found that there are at most \ (m \) modified locations, which need to be modified every time, so the total time complexity is \ (\ mathcal O(m^2) \), which directly explodes.
Consider operation blocking: reconstruct the original sequence every \ (\ sqrt{m} \), and then do it together with the temporarily stored \ (\ sqrt{m} \) operations.
In this way, there are at most \ (\ sqrt{m} \) modified positions, which must be modified every time. Then the time complexity of a single operation block is \ (\ mathcal O(\sqrt{m} \times \sqrt m)=\mathcal O(m) \), and the total time complexity is \ (\ mathcal O(m \sqrt{n} \).
When querying, you can scan the bulk records one by one.
Therefore, the total time complexity is \ (\ mathcal O(n \sqrt n) \) and the total space complexity is \ (\ mathcal O(n) \).
Summary: the sequence is divided into blocks, the operation is divided into blocks, and the power card is often added.
\(\text{01-29 17:25:11 / 1.23min / 22.48MB / 5.82KB C++98 O2}\).
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define re register
namespace Fread
{
const int SIZE = 1 << 23;
char buf[SIZE], *S, *T;
inline char getchar()
{
if (S == T)
{
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite
{
const int SIZE = 1 << 23;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush()
{
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c)
{
*S++ = c;
if (S == T)
flush();
}
struct NTR
{
~NTR()
{
flush();
}
} ztr;
}
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
inline int read()
{
re int x = 0, f = 1;
re char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void write(re long long x)
{
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
inline int min(re const int &x, re const int &y)
{
return x < y ? x : y;
}
const int N = 3e5 + 1, S = 2e3 + 1;
struct Modify
{
int opt, pos, val;
} q1[S];
struct Query
{
int opt, l, r, x, id;
} q2[S];
int n, m, c1, c2, a[N];
long long calc[N];
bool seq[N];
int L[S], R[S], id[N], p[N], sum[S];
inline void clear()
{
memset(seq, 0, sizeof seq);
memset(p, 0, sizeof p);
memset(sum, 0, sizeof sum);
}
inline void init()
{
re int sqn = sqrt(n * 4 / 5 + 1);
for(re int i = 1, j, c = 1; i <= n; i = j + 1, ++c)
{
L[c] = i, R[c] = j = min(n, i + sqn);
for(re int t = L[c]; t <= R[c]; ++t)
id[t] = c;
}
}
int top;
struct Node
{
int id, ans, t1[4];
bool flg;
inline void clear()
{
t1[0] = t1[1] = t1[2] = t1[3] = flg = 0;
}
} sta[S], tmp;
inline void modify(re const int &pos, re bool flg)
{
p[pos] = pos, seq[pos] = 1, tmp.id = pos;
re const int lst = pos - 1, nxt = pos + 1, tmp_p = p[lst];
re const bool flg1 = (seq[lst] && L[id[pos]] != pos), flg2 = (seq[nxt] && R[id[pos]] != pos);
if(!flg1 && !flg2)
tmp.clear(), tmp.ans = 1;
else
{
tmp.flg = 1;
if(flg1 && flg2)
{
tmp.ans = (nxt - p[lst]) * (p[nxt] - lst);
tmp.t1[0] = p[lst], tmp.t1[1] = p[p[lst]], p[p[lst]] = p[nxt];
tmp.t1[2] = p[nxt], tmp.t1[3] = p[p[nxt]], p[p[nxt]] = tmp_p;
}
else
{
if(flg1)
{
tmp.ans = nxt - p[lst];
tmp.t1[0] = pos, tmp.t1[1] = p[pos], p[pos] = p[lst];
tmp.t1[2] = p[lst], tmp.t1[3] = p[p[lst]], p[p[lst]] = pos;
}
else
{
tmp.ans = p[nxt] - lst;
tmp.t1[0] = pos, tmp.t1[1] = p[pos], p[pos] = p[nxt];
tmp.t1[2] = p[nxt], tmp.t1[3] = p[p[nxt]], p[p[nxt]] = pos;
}
}
}
sum[id[pos]] += tmp.ans;
if(flg) sta[++top] = tmp;
}
inline void back()
{
while(top)
{
tmp = sta[top--], sum[id[tmp.id]] -= tmp.ans, seq[tmp.id] = 0;
if(tmp.flg)
{
p[tmp.t1[2]] = tmp.t1[3];
p[tmp.t1[0]] = tmp.t1[1];
}
}
}
inline long long query(const int &l, const int &r)
{
re long long ans = 0;
if(id[l] == id[r])
{
int cnt = 0;
for(re int i = l; i <= r; ++i)
if(seq[i])
cnt++;
else
ans += calc[cnt], cnt = 0;
return ans + calc[cnt];
}
re int c1 = 0, c2 = 0;
for(re int i = l; i <= R[id[l]]; ++i)
if(seq[i])
c1++;
else
ans += calc[c1], c1 = 0;
for(re int i = r; i >= L[id[r]]; --i)
if(seq[i])
c2++;
else
ans += calc[c2], c2 = 0;
re int tot = c1;
for(re int i = id[l] + 1; i <= id[r] - 1; ++i)
if(p[L[i]] == R[i])
tot += R[i] - L[i] + 1;
else
{
if(seq[L[i]])
{
tot += p[L[i]] - L[i] + 1, ans -= calc[p[L[i]] - L[i] + 1];
}
ans += calc[tot] + sum[i], tot = 0;
if(seq[R[i]])
{
tot += R[i] - p[R[i]] + 1, ans -= calc[R[i] - p[R[i]] + 1];
}
}
return ans + calc[tot + c2];
}
long long ans[S];
int cnt, head[N];
struct Edge
{
int to, nxt;
} G[N];
bool broke[N], use[N];
inline void add(const int &u, const int &v)
{
G[++cnt] = {v, head[u]};
head[u] = cnt;
}
inline bool cmp(const Query &x, const Query &y)
{
return x.x < y.x;
}
inline void solve()
{
clear();
for(re int i = 1; i <= c1; ++i)
broke[q1[i].pos] = 1;
for(re int i = 1; i <= n; ++i)
if(!broke[i])
add(a[i], i);
std::sort(q2 + 1, q2 + c2 + 1, cmp);
int pot = 1;
for(re int i = 1; i <= c2; ++i)
{
while(pot <= q2[i].x)
{
for(re int i = head[pot]; i; i = G[i].nxt)
modify(G[i].to, 0);
pot++;
}
for(re int j = c1; j >= 1; --j)
if(q1[j].opt < q2[i].opt && !use[q1[j].pos])
{
use[q1[j].pos] = 1;
if(q1[j].val <= q2[i].x)
modify(q1[j].pos, 1);
}
for(re int j = 1; j <= c1; ++j)
if(!use[q1[j].pos])
{
use[q1[j].pos] = 1;
if(a[q1[j].pos] <= q2[i].x)
modify(q1[j].pos, 1);
}
ans[q2[i].id] = query(q2[i].l, q2[i].r);
back();
for(re int j = 1; j <= c1; ++j)
use[q1[j].pos] = 0;
}
cnt = 0;
memset(head, 0, sizeof head);
for(re int i = 1; i <= c1; ++i)
broke[q1[i].pos] = 0;
}
signed main()
{
n = read(), m = read();
int sqm = sqrt(m * 11);
init();
for(re int i = 1; i <= n; ++i)
a[i] = read();
for(re int i = 1; i <= n; ++i)
calc[i] = 1ll * i * (i + 1) / 2;
for(re int i = 1, j; i <= m; i = j + 1)
{
j = min(m, i + sqm), c1 = c2 = 0;
for(re int t = i; t <= j; ++t)
if(read() == 1)
q1[++c1] = {t, read(), read()};
else
q2[++c2] = {t, read(), read(), read(), c2};
solve();
for(re int t = 1; t <= c2;++t)
write(ans[t]), putchar('\n');
for(re int t = 1; t <= c1; ++t)
a[q1[t].pos] = q1[t].val;
}
}