Portal

Meaning:

Here's a long for you n n Array of n a a a. The defined interval is the number of occurrences of each number in this interval ≤ ⌈ n 2 ⌉ \le \left \lceil \frac{n}{2} \right \rceil ≤⌈ 2n ⌉ is defined as dividing several subsequences of this interval into several intervals. have q q q queries, one interval at a time. Ask how many intervals this interval is divided into at least to make each interval a good interval.

Idea:

It should be noted that the divided interval is a subsequence of the original interval, and the divided interval should also be a good interval. After reading the wrong question for more than an hour, it's self closing.
Note the subsequence, so we can consider it separately. Suppose that the most frequent occurrence of the current interval is x x x times, length l e n len len, the limit is l i m i t limit limit, which is discussed in the following situations:
( 1 ) (1) (1) When x ≤ l i m i t x\le limit When x ≤ limit, it can be divided into an interval.
( 2 ) (2) (2) When x > l i m i t x>limit x> In limit, we need to divide the interval and calculate the good number as l e n − x len-x - let's do as much as possible x x x is put together with these good numbers because it has only l e n − x len-x len − x, so we can put it with him at most l e n − x + 1 len-x+1 len − x+1, the rest x − ( l e n − x + 1 ) x-(len-x+1) X − (len − x+1). We found that they can only be a single interval, so the number of intervals required in the end is 1 + x − ( l e n − x + 1 ) = 2 ∗ x − l e n 1+x-(len-x+1)=2*x-len 1+x − (len − x+1)=2 * x − len, the problem is transformed into a solution x x x. There are many methods. You can use Mo team directly for seconds. Here is a chairman tree O ( n l o g n ) O(nlogn) O(nlogn).
First build the chairman tree according to the weight, and each time [ l , r ] [l,r] The interval of [l,r] is taken out, and the information is stored in the number of values. We directly split it in the chairman tree c n t l > l i m i t cnt_l>limit When cntl > limit, recurse to the left, c n t r > l i m i t cnt_r>limit When cntr > limit, it recurses to the right, otherwise it returns 1 1 1 is enough. Finally recursive to l = = r l==r When l==r, the most frequent occurrences are found x x x. Just calculate the answer directly. That's right because he needs x > l i m i t x>limit x> Limit, and l i m i t = ⌈ n 2 ⌉ limit = \left \lceil \frac{n}{2} \right \rceil limit = ⌈ 2n ⌉ so his side must be c n t > l i m i t cnt>limit Cnt > limit, so the correctness is verified.

There seems to be a problem in the solution O ( l o g n ) O(logn) The practice of O(logn) can be seen after class

// Problem: D. Cut and Stick
// Contest: Codeforces - Codeforces Round #716 (Div. 2)
// URL: https://codeforces.com/contest/1514/problem/D
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=300010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,m;
int ans[N],a[N];
int root[N],tot;
struct Node
{
	int l,r,id;
}q[N];
struct Tree
{
    int l,r;
    int cnt;
}tr[N*40];

void insert(int p,int &q,int l,int r,int pos)
{
	q=++tot; tr[q]=tr[p];
	tr[q].cnt++;
	if(l==r) return;
	int mid=l+r>>1;
	if(pos<=mid) insert(tr[p].l,tr[q].l,l,mid,pos);
	else insert(tr[p].r,tr[q].r,mid+1,r,pos);
}

int query(int p,int q,int l,int r,int k)
{
	int limit=k/2+(k%2==1);
	if(l==r)
	{
		int cnt=tr[q].cnt-tr[p].cnt;
		if(cnt<=limit) return 1;
		return 2*cnt-k;
	}
	int mid=l+r>>1;
	int cntl=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
	int cntr=tr[tr[q].r].cnt-tr[tr[p].r].cnt;
	if(cntl<=limit&&cntr<=limit) return 1;
	if(cntl<=limit&&cntr>limit) return query(tr[p].r,tr[q].r,mid+1,r,k);
	if(cntr<=limit&&cntl>limit) return query(tr[p].l,tr[q].l,l,mid,k);
	return max(query(tr[p].l,tr[q].l,l,mid,k),query(tr[p].r,tr[q].r,mid+1,r,k));
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);

	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),insert(root[i-1],root[i],1,300000,a[i]);
	for(int i=1;i<=m;i++)
	{
		int l,r; scanf("%d%d",&l,&r);
		printf("%d\n",query(root[l-1],root[r],1,300000,r-l+1));
	}



	return 0;
}
/*

*/