chunking
A mindset that optimizes violence.
This is usually done by dividing the original data into appropriate chunks (typically\(\sqrt{n}\)), preprocessing each chunk of data, which in turn achieves a better time complexity than violence.
delineation
Determine the length of the block, generally need to open two arrays to store the right boundary of each piece with the original data belongs to the block serial number, more convenient for subsequent operations.
int sq=sqrt(n);
for(int i=1;i<=sq;i++) ed[i]=n/sq*i;
ed[sq]=n;// put all the rest into the last block
for(int i=1;i<=n;i++)
for(int j=ed[i-1]+1;j<=ed[i];j++)
bl[j]=i;
Interval Search
Query an interval\(\left[L,R\right]\) Inside information, there are two main categories:
- The queried intervals lie within a block, and direct violence is sufficient, with a worst-case complexity of\(sq\)；
- The query interval spans multiple blocks and is solved in three parts:\(\left[L,ed_{bl_{L}}\right]\), middle full block statistics, and last\(\left[ed_{bl_R-1},R\right]\), with a worst-case complexity of\(\frac{n}{sq}+sq\) 。
In the usual case take\(sq=\sqrt{n}\) When the single query complexity is at worst all\(\sqrt{n}\)。
As an example of interval summation, there exists interval modification to process each block of sum in advance, the code is as follows:
int Query(int l,int r)
{
int ans=0;
if(bl[l]==bl[r])
{
for(int i=l;i<=r;i++) ans+=a[i]+lazy[bl[i]];
return ans;
}
for(int i=l;bl[i]==bl[l];i++) ans+=a[i]+lazy[bl[i]];
for(int i=bl[l]+1;i<bl[r];i++) ans+=sum[i];
for(int i=r;bl[i]==bl[r];i--) ans+=a[i]+lazy[bl[i]];
return ans;
}
Interval Modification
The situation is the same as the query and is divided into two types:
- Within the same piece, direct violent modification;
- Not in the same block, brute force modification of incomplete blocks at the beginning and end, complete blocks in the middle are marked with lazy.
The complexity is still\(\sqrt{n}\)。
The code is as follows:
void modify(int l,int r,int k)
{
if(bl[l]==bl[r])
{
for(int i=l;i<=r;i++) a[i]+=k,sum[bl[i]]+=k;
return;
}
for(int i=l;bl[i]==bl[l];i++) a[i]+=k,sum[bl[i]]+=k;
for(int i=bl[l]+1;i<bl[r];i++) lazy[i]+=k,sum[i]+=k*sq;
for(int i=r;bl[i]==bl[r];i--) a[i]+=k,sum[bl[i]]+=k;
}
Mo team (sports)
An offline algorithm, implemented based on the chunking idea.
The premise behind the use of mo queues is that, for interval query problems, it is possible to use the\(\mathcal{O(1)}\) The complexity of the interval from the known\(\left[l,r\right]\) The answer to this question leads to\(\left[l-1,r\right]\)，\(\left[l+1,r\right]\)，\(\left[l,r-1\right]\)，\(\left[l,r+1\right]\) The answer to this question can then be found in the\(\mathcal{O(n\sqrt{n})}\) to find the answers to all queries within the complexity of the
Inquiry pre-processing
To make each step as efficient as possible, i.e., without significant redundancy, we need to sort the disordered queries in advance.
Typically, the sorting criterion is ascending order with the block belonging to the left boundary as the first keyword and the right boundary as the second keyword, and the optimality proof is shown below.
In some very special cases, we can further optimize the complexity by parity sorting, etc., which is usually not necessary.
complexity analysis
Excerpted from OI-wiki.
realization
HH's necklace (this question)\(10^6\) (the data over the root is really quite extreme, quoted here just because it's simpler and more relevant to Team Mo's thinking)
The intervals are solved for different kinds of numbers, and the query preprocessing is left out, only the important parts:
void add(int x)
{
cnt[a[x]]++;
if(cnt[a[x]]==1) ans++;
}
void del(int x)
{
cnt[a[x]]--;
if(!cnt[a[x]]) ans--;
}
int main()
{
/*code*/
for(int i=1;i<=m;i++)
{
while(l<q[i].l) del(l++);
while(l>q[i].l) add(--l);
while(r>q[i].r) del(r--);
while(r<q[i].r) add(++r);
answer[q[i].id]=ans;
}
for(int i=1;i<=m;i++) printf("%d\n",answer[i]);
return 0;
}
Roll back the Mocs.
Mo team of an extended form, applicable to increase or delete the operation of one of the bad maintenance of the situation, mainly divided into the non-increase Mo team and do not delete the Mo team.
As an example of a non-deletion mo team, a typical example problem is to find the number of numbers that occur the most times in a given interval.
ideology
The original sequence is first chunked and the queries are sorted.
Recording a variable\(las\), stores the block where the left boundary of the previous query is located, or if different from the current one, the\(l\) The pointer moves to one after the right boundary of the block where the left boundary of the current query is located.\(r\) The pointer is moved to the right boundary of the block where the left boundary of the current query is located, ensuring that it is currently the empty set.
If within the same block then solve violently and restore after solving.
Otherwise, the\(r\) Jump right to the right border of the inquiry.Update the counting array and the answer at the same time。
After that, create a new pointer\(l_1\)The initial value is\(l\)and record the answer tmp at this point; then move the pointer to the left\(l_1\) to the left border of the inquiry.Update the counting array and the answer at the same time, at which point the answer to the current query is obtained and recorded; and finally the\(l_1\) The pointer moves right back to\(l\) position, at which point theOnly the count array is updated not the answersIf the answer is assigned to tmp, a query operation is completed.
Note that the order of the second and third steps can not be switched, because in moving the left boundary of the query interval in the block when this operation that may be the same piece of the query, we need to empty the counting array before solving the answer.
realization
Take a typical example problem, again showing only the key parts of the code:
void add(int x)
{
cnt[a[x]]++;
if(cnt[a[x]]>answer) answer=cnt[a[x]];
}
void del(int x)
{
cnt[a[x]]--;
}
int main()
{
/*code*/
int l=ed[bl[q[1].l]]+1,r=ed[bl[q[1].l]],las=bl[q[1].l];
for(int i=1;i<=m;i++)
{
if(las!=bl[q[i].l])
{
while(r>ed[bl[q[i].l]]) del(r--);
while(r<ed[bl[q[i].l]]) add(++r);
while(l<ed[nl[q[i].l]]+1) del(l++);
answer=0,las=bl[q[i].l];
}
if(bl[q[i].l]==bl[q[i].r])
{
for(int j=q[i].l;j<=q[i].r;j++) cnt[a[j]]++,ans[q[i].id]=max(ans[q[i].id],cnt[a[j]]);
for(int j=q[i].l;j<=q[i].r;j++) cnt[a[j]]--;
continue;
}
while(r<q[i].r) add(++r);
int l1=l,tmp=answer;
while(l1>q[i].l) add(--l1);
ans[q[i].id]=answer;
while(l1<l) del(l1++);
answer=tmp;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
opera role of old man
Different data structures have their own advantages, but also have something in common, we should learn where each idea is really advantageous, some of the more troublesome can be solved by conversion methods (so did not write with the Shumo team).
This article code all online hand-typed, there are problems please point out, thank you for your support.
"Finished" and "Sprinkled".