ahead
sort of like puttingPrevious PitFill it out.
This article mainly contains the advanced application of MoT algorithms, such as MoT with repair, 2D MoT, etc. Before watching, please make sure you have mastered the basic MoT algorithm, if you don't know it, you can poke thehere are。
band of thaumaturgists
It is well known that normal mo queues do not support modification, because we need to take each query offline and disrupt the order in order to get a better time complexity.
But we can also add a one-dimensionaltime dimensionForce it to support modifications, where the time dimension in the title sense is the number of modifications that need to be made.
main idea
Originally we had only four transfers to the current\(\left[l,r\right]\) As an example, we can\(\mathcal{O(1)}\) Expand to:
-
\(\left[l-1,r\right]\)
-
\(\left[l+1,r\right]\)
-
\(\left[l,r-1\right]\)
-
\(\left[l,r+1\right]\)
If we add the last dimension of time, then we need to make six transfers:
-
\(\left[l-1,r,time\right]\)
-
\(\left[l+1,r,time\right]\)
-
\(\left[l,r-1,time\right]\)
-
\(\left[l,r+1,time\right]\)
-
\(\left[l,r,time-1\right]\)
-
\(\left[l,r,time+1\right]\)
It's just one more way to transfer, and it doesn't affect the complexity of our transfer.
The principle of offline query sorting, with the block where the left endpoint is located as the first keyword, the block where the right endpoint is located as the second keyword, and the time as the third keyword in ascending order.
Block length selection and time complexity
For block lengths, it is common to take\(\mathcal{n^{\frac{2}{3}}}\), the final complexity is\(\mathcal{O(n^{\frac{5}{3}})}\)。
An analysis on optimal block lengths:
Excerpted from OI-wiki.
realization
in order toP1903 Counting Colors/Maintaining Queues As an example.
With the Shumo team board question, the idea is the same as above, and the main point here is the transfer of the two time dimensions.
The idea is simple, when querying for a particular query\(q\) If the current time is less than that time, then the transfer is performed. If the point of a change happens to be within the current interval, the change operation is performed, the change operation can be regarded as a deletion and an addition, after the operation is completed, in order to facilitate the backward step back afterwards, we exchange the deleted element and the updated element.
Operational separation:
for(int i=1;i<=m;i++)
{
char op;int x,y;
cin>>op>>x>>y;
if(op=='Q')
q[++qcnt].id=qcnt,q[qcnt].time=rcnt,
q[qcnt].x=x,q[qcnt].y=y;
else
r[++rcnt].p=x,r[rcnt].x=y;
}
Transfer section:
void add(int x)
{
if(!mp[x]) anss++;
mp[x]++;
}
void del(int x)
{
mp[x]--;
if(!mp[x]) anss--;
}
int main()
{
/*code*/
int L=1,R=0,tim=0;
for(int i=1;i<=qcnt;i++)
{// Transfer principle：first expand and then reduce
while(L>q[i].x) add(a[--L]);
while(R<q[i].y) add(a[++R]);
while(L<q[i].x) del(a[L++]);
while(R>q[i].y) del(a[R--]);
while(tim<q[i].time)
{
tim++;
if(L<=r[tim].p&&r[tim].p<=R)
add(r[tim].x),del(a[r[tim].p]);
swap(a[r[tim].p],r[rim].x);
}
while(tim>q[i].time)
{
if(L<=r[tim].p&&r[tim].p<=R)
add(r[tim].x),del(a[r[tim].p]);
swap(a[r[tim].p],r[tim].x);
tim--;
}
ans[q[i].id]=anss;
}
}
2D Mo team
Ordinary mo queue algorithms deal with problems on sequences, and if we extend it to a plane so that there are four directions to choose from when transferring, we get a two-dimensional mo queue.
Two-dimensional MoTeam transfer operation each time to move the pointer to operate the number of rows or columns, the specific implementation is similar to the ordinary one-dimensional MoTeam.
Block length selection and time complexity
Excerpted from OI-wiki.
Briefly, let the matrix size be\(S\)The number of inquiries was\(q\)Our block length is usually chosen to be\(\frac{\sqrt S}{q^{\frac{1}{4}}}\)If the result of this calculation is less than 1, we just assign the value of 1 to it.
Ultimately, the time complexity in the solution part is\(\mathcal{O(S·q^{\frac{3}{4}})}\), the total time complexity is\(\mathcal{O(S·q^{\frac{3}{4}}+q\log q)}\)。
realization
Example: Given a variable of size\(n\times m\) of the matrix, followed by giving\(q\) queries, each asking for the weights of one submatrix at a time, with the weights defined as: if an element appears in a matrix with the\(k\) times, then it contributes\(k^2\)。
Structure definition:
Given the coordinates of the upper-left and lower-right corners of a rectangle, we sort them in ascending order of the blocks to which the upper-left horizontal coordinate, upper-left vertical coordinate, lower-right horizontal coordinate, and lower-right vertical coordinate belong.
struct Que
{
int lx,ly,rx,ry,id;
bool operator<(const Que &A)const
{
if(lx/B!=/B) return lx<;
if(ly/B!=/B) return ly<;
if(rx/B!=/B) return rx<;
return ry<;
}
}que[N];
Transfer section:
For rows and columns we use different functions
int a[N][N];// primitive matrix (math.)
int cnt[N];// distinctive
void mdfline(int id,int val,int u,int v)
{// rise/Delete a line
for(int i=u;i<=v;i++)
anss-=1ll*cnt[a[id][i]]*cnt[a[id][i]],
cnt[a[id][i]]+=val,
anss+=1ll*cnt[a[id][i]]*cnt[a[id][i]];
}
void mdfcolumn(int id,int val,int u,int v)
{
for(int i=u;i<=v;i++)
anss-=1ll*cnt[a[i][id]]*cnt[a[i][id]],
cnt[a[i][id]]+=val,
anss+=1ll*cnt[a[i][id]]*cnt[a[i][id]];
}
int main()
{
/*code*/
B=pow(n*m,0.5)/pow(q,0.25);
if(B<1) B=1;
sort(que+1,que+1+q);
int lx=1,ly=1,rx=0,ry=0;
for(int i=1;i<=q;i++)
{
while(lx>que[i].lx) mdfline(--lx,1,ly,ry);
while(rx<que[i].rx) mdfline(++rx,1,ly,ry);
while(ly>que[i].ly) mdfcolumn(--ly,1,lx,rx);
while(ry<que[i].ry) mdfcolumn(++ry,1,lx,rx);
while(lx<que[i].lx) mdfline(lx++,-1,ly,ry);
while(rx>que[i].rx) mdfline(rx--,-1,ly,ry);
while(ly<que[i].ly) mdfcolumn(ly++,-1,lx,rx);
while(ry>que[i].ry) mdfcolumn(ry--,-1,lx,rx);
ans[que[i].id]=anss;
}
for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
return 0;
}
opera role of old man
These more or less improved algorithms are more or less optimized for different types of problems, and their application is more limited. But these optimized ideas are still very helpful to us, and we should still try to understand each algorithm in case we need it someday.
This article code all online hand-typed, there are problems please point out, thank you for your support.
"Finished" and "Sprinkled".