Elegant violence - Team Mo's algorithm study notes

1. Problem introduction

When there is a question that asks you every time you have something in an interval, and this thing cannot be merged (not segment trees) and cannot be differentiated (not tree-like arrays) and it is difficult to merge/cannot be merged (not blocked), but it supports offline and any interval can get answers to other intervals through expansion and contraction, then this question can be used.

2. What is Team Mo

First, if there is a question where the interval can be expanded and contracted (no need to support offline), can you first find the answer to the first interval, and then find the answer to the other intervals through the expansion and contraction of the left and right endpoints, but you will find the worst time complexity and violence.$O(qn)$The same, but at this time the magical thing comes. We will ask it offline, and then through a magical sort, its time complexity becomes$O((q+n) \sqrt n)$Now! What is this magical sort?$1$arrive$n$All points of the chunk are divided into blocks, and then sort them first according to$l$The blocks are sorted from small to large, if there are two$l$Equal, follow$r$sorted from small to large.

3. How to prove the time complexity of Team Mo

First of all, you will find that if the left pointer is in the same block, the time complexity of the single move is$O(\sqrt n)$, because the size of a block is at most$\sqrt n$, and the left pointer cannot move out of this block, and then if it is a different block, because each time it moves at most$O(\sqrt n)$step, so the time complexity of single move is$O(\sqrt n)$, and then start thinking about the total movement, you will find that the time complexity is$O(q \sqrt n+n)$，$O(q\sqrt n)$is the total complexity of moving within the same block (because it needs to move$q$So, so$O(q \times \sqrt n) = O(q \sqrt n)$),Then$O(n)$Refers to the total time complexity of movement of a different block, because this happens only$O(\sqrt n)$times, so the total time complexity is$O(\sqrt n \times \sqrt n) = O(n)$, and then consider the right pointer moving, you will find that the right pointer block increases monotonically according to the order of the Mo team, but the spanning block does not necessarily drop the increment, so you will find that the behavior of spanning block will only appear at most$O(\sqrt n)$times, and every time the worst move$O(n)$step, so the total time complexity is$O(\sqrt n \times n+n) = O(n \sqrt n+n) = O(n \sqrt n)$, so the final time complexity is$O((n+q) \sqrt n)$Of course, during the calculation process, we have saved several constants, so Team Mo's constant is also a bit large.

4. Team Mo board

#include<bits/stdc++.h>
 using namespace std;
 const int N = 5e4+5;// Can be freely variable
 struct node
 {
	 int l;
	 int r;
	 int id;
 }b[N];
 int a[N];
 int len;
 int cmp(node x,node y)
 {
	 int idx = (-1)/len+1,idy = (-1)/len+1;
	 return idx == idy?<:idx<idy;
 }
 int sum;
 void add(int x)
 {
	 //Expand range
 }
 void del(int x)
 {
	 //Shrinking range
 }
 int ans[N];
 signed main()
 {
	 int n,_;
	 scanf("%d %d",&n,&_);
	 len = sqrt(n);
	 for(int i = 1;i<=n;i++)
	 {
		 scanf("%d",&a[i]);
	 }
	 for(int i = 1;i<=_;i++)
	 {
		 scanf("%d %d",&b[i].l,&b[i].r);
		 b[i].id = i;
	 }
	 sort(b+1,b+_+1,cmmp);
	 for(int i = 1,l = 1,r = 0;i<=_;i++)//As for why l = 1,r = 0 is because the teacher said that this can prevent the mistakes of mystery
	 {
		 while(l>b[i].l)//The teacher also said that you must expand first and then shrink, which can prevent the situation of l>r
		 {
			 add(--l);
		 }
		 While(r<b[i].r)
		 {
			 add(++r);
		 }
		 While(l<b[i].l)
		 {
			 del(l++);
		 }
		 While(r>b[i].r)
		 {
			 del(r--);
		 }
		 ans[b[i].id] = sum;
	 }
	 return 0;
 }

Note: This is just a board, and the contents inside can be adaptable.

5. Team Mo's exercise explanation

P3901 Find the difference in sequence

A very basic team, put the board of Mo and fill it in.addanddelJust the function.
Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node
{
	int l;
	int r;
	int id;
}b[N];
int a[N];
int tong[N];
int len;
int cmp(node x,node y)
{
	int idx = (-1)/len+1,idy = (-1)/len+1;
	return idx == idy?<:idx<idy;
}
int sum;
void add(int x)
{
	if(tong[a[x]] == 1)
    {
        sum++;
    }
	tong[a[x]]++;
}
void del(int x)
{
	tong[a[x]]--;
	if(tong[a[x]] == 1)
    {
        sum--;
    }
}
int ans[N];
signed main()
{
	int n,_;
	scanf("%d %d",&n,&_);
	len = sqrt(n);
	for(int i = 1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i = 1;i<=_;i++)
	{
		scanf("%d %d",&b[i].l,&b[i].r);
		b[i].id = i;
	}
	sort(b+1,b+_+1,cmp);
	for(int i = 1,l = 1,r = 0;i<=_;i++)
	{
		while(l>b[i].l)
		{
			add(--l);
		}
		while(r<b[i].r)
		{
			add(++r);
		}
		while(l<b[i].l)
		{
			del(l++);
		}
		while(r>b[i].r)
		{
			del(r--);
		}
		ans[b[i].id] = sum;
	}
	for(int i = 1;i<=_;i++)
	{
		printf("%s\n",ans[i]?"No":"Yes");
	}
	return 0;
}

AT_abc293_g [ABC293G] Triple Index

A little harder than the previous question, let's consider it$num_x$Indicates in the current range$x$How many times have it appeared, then we consider it$num_x$become$num_x+1$What impact will it have on the answer? The impact of discovery is$C_{num_x+1}^3-C_{num_x}^3$，$C_{num_x+1}^3 = \frac{(num_x+1)num_x(num_x-1)}{3!} = \frac{(num_x+1)num_x(num_x-1)}{6}$，$C_{num_x}^3 = \frac{num_x(num_x-1)(num_x-2)}{3!} = \frac{num_x(num_x-1)(num_x-2)}{6}$，$C_{num_x+1}^3-C_{num_x}^3 = \frac{(num_x+1)num_x(num_x-1)}{6}-\frac{num_x(num_x-1)(num_x-2)}{6} = \frac{num_x((num_{x}-1)(num_{x}+1-(num_{x}-2)))}{6} = \frac{num_x((num_{x}-1)(num_{x}+1-num_{x}+2))}{6} = \frac{num_x(3(num_{x}-1))}{6} = \frac{3num_x(num_x-1)}{6} = \frac{num_x(num_x-1)}{2}$, the same method of deletion is used, and then just set up the Mo team board normally.

Ten years of OI is a waste, and long long meets our ancestors!

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 2e5+5;
struct node
{
	int l;
	int r;
	int id;
}b[N];
int a[N];
int tong[N];
int len;
int cmp(node x,node y)
{
	int idx = (-1)/len+1,idy = (-1)/len+1;
	return idx == idy?<:idx<idy;
}
int sum;
void add(int x)
{
    sum+=tong[a[x]]*(tong[a[x]]-1)/2;
	tong[a[x]]++;
}
void del(int x)
{
	tong[a[x]]--;
	sum-=tong[a[x]]*(tong[a[x]]-1)/2;
}
int ans[N];
signed main()
{
	int n,_;
	scanf("%lld %lld",&n,&_);
	len = sqrt(n);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i = 1;i<=_;i++)
	{
		scanf("%lld %lld",&b[i].l,&b[i].r);
		b[i].id = i;
	}
	sort(b+1,b+_+1,cmp);
	for(int i = 1,l = 1,r = 0;i<=_;i++)
	{
		while(l>b[i].l)
		{
			add(--l);
		}
		while(r<b[i].r)
		{
			add(++r);
		}
		while(l<b[i].l)
		{
			del(l++);
		}
		while(r>b[i].r)
		{
			del(r--);
		}
		ans[b[i].id] = sum;
	}
	for(int i = 1;i<=_;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}

P1494 [National Training Team] Little Z's Socks

There seems to be nothing to say about the weakened version of the previous question, that is, the triple was replaced with a double.
Still... Ten years of OI was in vain, long long to see our ancestors!

We want to divide the total number by the number of possible binaries, so if you still use only$ans$The array stores the number of binary groups, so please open one when answering each inquiry.$num$Array, representing the sorted number corresponding to the original query number,~~Otherwise, I will adjust it for an hour like me...~~

Don't forget the title$l = r$The situation! !
Code:

#include<bits/stdc++.h>
 using namespace std;
 #define int long long
 const int N = 5e4+5;
 struct node
 {
	 int l;
	 int r;
	 int id;
 }b[N];
 int a[N];
 int tong[N];
 int len;
 int cmp(node x,node y)
 {
	 int idx = (-1)/len+1,idy = (-1)/len+1;
	 return idx == idy?<:idx<idy;
 }
 int sum;
 void add(int x)
 {
	 sum+=tong[a[x]];
	 tong[a[x]]++;
 }
 void del(int x)
 {
	 tong[a[x]]--;
	 sum-=tong[a[x]];
 }
 int ans[N];
 int num[N];
 signed main()
 {
	 int n,_;
	 scanf("%lld %lld",&n,&_);
	 len = sqrt(n);
	 for(int i = 1;i<=n;i++)
	 {
		 scanf("%lld",&a[i]);
	 }
	 for(int i = 1;i<=_;i++)
	 {
		 scanf("%lld %lld",&b[i].l,&b[i].r);
		 b[i].id = i;
	 }
	 sort(b+1,b+_+1,cmmp);
	 for(int i = 1,l = 1,r = 0;i<=_;i++)
	 {
		 While(l>b[i].l)
		 {
			 add(--l);
		 }
		 While(r<b[i].r)
		 {
			 add(++r);
		 }
		 While(l<b[i].l)
		 {
			 del(l++);
		 }
		 While(r>b[i].r)
		 {
			 del(r--);
		 }
		 ans[b[i].id] = sum;
		 num[b[i].id] = i;
	 }
	 for(int i = 1;i<=_;i++)
	 {
		 if(b[num[i]].l == b[num[i]].r)//Remember it is very important here, otherwise it will be 10 points
		 {
			 printf("0/1\n");
			 continue;
		 }
		 int yue = __gcd(ans[i],(b[num[i]].r-b[num[i]].l+1)*(b[num[i]].r-b[num[i]].l)/2);
		 printf("%lld/%lld\n",ans[i]/yue,(b[num[i]].r-b[num[i]].l+1)*(b[num[i]].r-b[num[i]].l)/2/yue);
	 }
	 return 0;
 }

P2709 Xiao B's inquiry

The routines are almost the same, but still$num_x$Indicates that it is in the current interval$x$How many times have it appeared, we want to see$num_x$become$num_x+1$What impact will it have on the answer? I found that it will add the answer$(num_x+1)^2-num_x^2 = num_x^2+2num_x+1-num_x^2 = 2num_x+1$, and then delete the same method of pushing, and finally put the Mo team board.

Ten years of OI is a waste, and long long meets our ancestors!

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 5e4+5;
struct node
{
	int l;
	int r;
	int id;
}b[N];
int a[N];
int tong[N];
int len;
int cmp(node x,node y)
{
	int idx = (-1)/len+1,idy = (-1)/len+1;
	return idx == idy?<:idx<idy;
}
int sum;
void add(int x)
{
	sum+=2*tong[a[x]]+1;
	tong[a[x]]++;
}
void del(int x)
{
	tong[a[x]]--;
	sum-=2*tong[a[x]]+1;
}
int ans[N];
signed main()
{
	int n,_,__;
	scanf("%lld %lld %lld",&n,&_,&__);
	len = sqrt(n);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i = 1;i<=_;i++)
	{
		scanf("%lld %lld",&b[i].l,&b[i].r);
		b[i].id = i;
	}
	sort(b+1,b+_+1,cmp);
	for(int i = 1,l = 1,r = 0;i<=_;i++)
	{
		while(l>b[i].l)
		{
			add(--l);
		}
		while(r<b[i].r)
		{
			add(++r);
		}
		while(l<b[i].l)
		{
			del(l++);
		}
		while(r>b[i].r)
		{
			del(r--);
		}
		ans[b[i].id] = sum;
	}
	for(int i = 1;i<=_;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}

CF86D Powerful array

You will find that there is no difference from the previous question, so there is an extra $ \times i$, and that's the same.

Ten years of OI is a waste, and long long meets our ancestors!

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 5e4+5;
struct node
{
	int l;
	int r;
	int id;
}b[N];
int a[N];
int tong[N];
int len;
int cmp(node x,node y)
{
	int idx = (-1)/len+1,idy = (-1)/len+1;
	return idx == idy?<:idx<idy;
}
int sum;
void add(int x)
{
	sum+=2*tong[a[x]]+1;
	tong[a[x]]++;
}
void del(int x)
{
	tong[a[x]]--;
	sum-=2*tong[a[x]]+1;
}
int ans[N];
signed main()
{
	int n,_,__;
	scanf("%lld %lld %lld",&n,&_,&__);
	len = sqrt(n);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i = 1;i<=_;i++)
	{
		scanf("%lld %lld",&b[i].l,&b[i].r);
		b[i].id = i;
	}
	sort(b+1,b+_+1,cmp);
	for(int i = 1,l = 1,r = 0;i<=_;i++)
	{
		while(l>b[i].l)
		{
			add(--l);
		}
		while(r<b[i].r)
		{
			add(++r);
		}
		while(l<b[i].l)
		{
			del(l++);
		}
		while(r>b[i].r)
		{
			del(r--);
		}
		ans[b[i].id] = sum;
	}
	for(int i = 1;i<=_;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}

CF617E XOR and Favorite Number

Finally something a little bit harder! First of all, you need to know a basic nature of XOR:$a \oplus b = c$,So$b \oplus c = a$,besides$x \oplus x = 0$. Based on these two properties, we can find that we can find the original array we read in to obtain a prefix XOR, and then set the Mo team normally.

There are a few things to note:

because$\oplus_{i = l}^r a_i = sum_r \oplus sum_{l-1}$, so we need to subtract the left endpoint from the interval we read$1$。
Ten years of OI is a waste, and long long meets our ancestors!
Since it is XOR, we need to initialize it at the beginning$num_0 = 1$Because we have one$sum_0 = 0$。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e6+5;
struct node
{
	int l;
	int r;
	int id;
}b[N];
int a[N];
int tong[N];
int len;
int k;
int cmp(node x,node y)
{
	int idx = (-1)/len+1,idy = (-1)/len+1;
	return idx == idy?<:idx<idy;
}
int sum;
void add(int x)
{
	sum+=tong[a[x]^k];
	tong[a[x]]++;
}
void del(int x)
{
	tong[a[x]]--;
	sum-=tong[a[x]^k];
}
int ans[N];
signed main()
{
	int n,_;
	scanf("%lld %lld %lld",&n,&_,&k);
	len = sqrt(n);
	for(int i = 1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		a[i]^=a[i-1];
	}
	for(int i = 1;i<=_;i++)
	{
		scanf("%lld %lld",&b[i].l,&b[i].r);
		b[i].l--;
		b[i].id = i;
	}
	sort(b+1,b+_+1,cmp);
	tong[0] = 1;
	for(int i = 1,l = 0,r = 0;i<=_;i++)
	{
		while(l>b[i].l)
		{
			add(--l);
		}
		while(r<b[i].r)
		{
			add(++r);
		}
		while(l<b[i].l)
		{
			del(l++);
		}
		while(r>b[i].r)
		{
			del(r--);
		}
		ans[b[i].id] = sum;
	}
	for(int i = 1;i<=_;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}

P5268 [SNOI2017] A simple inquiry

The most difficult question at present is that the first question is given two intervals. We know that Team Mo can only handle one interval, but we can break these two intervals:

\[\sum_{x = 0}^\infty \operatorname{get}(l_1,r_1,x) \times \operatorname{get}(l_2,r_2,x) \]

\[\sum_{x = 0}^\infty (\operatorname{get}(1,r_1,x)-\operatorname{get}(1,l_1-1,x)) \times (\operatorname{get}(1,r_2,x)-\operatorname{get}(1,l_2-1,x)) \]

\[\sum_{x = 0}^\infty \operatorname{get}(1,r_1,x) \times \operatorname{get}(1,r_2,x)-\operatorname{get}(1,r_1,x) \times \operatorname{get}(1,l_2-1,x)-\operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,r_2,x)+\operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,l_2-1,x) \]

Then set:

\[q_1 = \operatorname{get}(1,r_1,x) \times \operatorname{get}(1,r_2,x) \]

\[q_2 = \operatorname{get}(1,r_1,x) \times \operatorname{get}(1,l_2-1,x) \]

\[q_3 = \operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,r_2,x) \]

\[q_4 = \operatorname{get}(1,l_1-1,x) \times \operatorname{get}(1,l_2-1,x) \]

Then the answer is:

\[\sum_{x = 0}^\infty q_1-q_2-q_3+q_4 \]

We only need to force the inquiry into these four types, each of which has only two numbers, so we can team Mo! However, when you are dealing with it, you should pay attention: it seems that you are using it$\operatorname{add}$Function, you need to determine whether you are expanding the left endpoint or expanding the right endpoint. If you are expanding the left endpoint, it is actually equivalent to you doing the deletion operation, otherwise it is normal.$\operatorname{del}$The same is true for functions.

Ten years of OI is a waste, and long long meets our ancestors!

Code:

#include<bits/stdc++.h>
 using namespace std;
 #define int long long
 const int N = 2e5+5;
 struct node
 {
	 int l;
	 int r;
	 int id;//Inquiry number
	 int idd;//The several variables to be processed in this question
 }b[N];
 int a[N];
 int tong1[N];
 int tong2[N];
 int len;
 int cmp(node x,node y)
 {
	 int idx = (-1)/len+1,idy = (-1)/len+1;
	 return idx == idy?<:idx<idy;
 }
 int sum;
 void add(int x,int opt)//opt is used to record whether you are expanding the left endpoint or expanding the right endpoint
 {
	 if(!opt)
	 {
		 sum-=tong2[a[x+1]];
		 tong1[a[x+1]]--;
	 }
	 else
	 {
		 sum+=tong1[a[x]];
		 tong2[a[x]]++;
	 }
 }
 void del(int x,int opt)//opt is used to record whether you are expanding the left endpoint or expanding the right endpoint
 {
	 if(!opt)
	 {
		 sum+=tong2[a[x+1]];
		 tong1[a[x+1]]++;
	 }
	 else
	 {
		 sum-=tong1[a[x]];
		 tong2[a[x]]--;
	 }
 }
 int ans[4][N];
 signed main()
 {
	 int n,_;
	 scanf("%lld",&n);
	 len = sqrt(n);
	 for(int i = 1;i<=n;i++)
	 {
		 scanf("%lld",&a[i]);
	 }
	 scanf("%lld",&_);
	 int cnt = 0;
	 for(int i = 1;i<=_;i++)
	 {
		 int l1,r1,l2,r2;
		 scanf("%lld %lld %lld %lld",&l1,&r1,&l2,&r2);
		 b[++cnt] = {r1,r2,i,0};
		 b[++cnt] = {r1,l2-1,i,1};
		 b[++cnt] = {l1-1,r2,i,2};
		 b[++cnt] = {l1-1,l2-1,i,3};
	 }
	 sort(b+1,b+cnt+1,cmp);
	 for(int i = 1,l = 1,r = 0;i<=cnt;i++)
	 {
		 While(l>b[i].l)
		 {
			 add(--l,0);
		 }
		 While(r<b[i].r)
		 {
			 add(++r,1);
		 }
		 While(l<b[i].l)
		 {
			 del(l++,0);
		 }
		 While(r>b[i].r)
		 {
			 del(r--,1);
		 }
		 ans[b[i].idd][b[i].id] = sum;
	 }
	 for(int i = 1;i<=_;i++)
	 {
		 printf("%lld\n",ans[0][i]-ans[1][i]-ans[2][i]+ans[3][i]);
	 }
	 return 0;
 }