Codeforces Round ＃716 (Div. 2) D. Cut and Stick

obviously ：
For an interval, we only need to deal with the element that appears most times
（ We call the remaining elements other elements ）
The optimal strategy is to take two maximum elements and one other element to form a sequence

So the answer to a certain interval is
$max(mostmanyelementplainindividualCount-ItsHeelementplain,1)$

So for a single interval , We just need to find out the number of elements that appear most often .
This is easy to make .
Because each time add a number or delete a number , The number of elements with the highest number of occurrences in the interval will only increase or decrease by one , So we only need one $cnt[i]$ Record $i$ Number of occurrences ,$rnk[i]$ The number of occurrences recorded is $i$ Number of elements of times .
Every maintenance $cnt[i]$ and $rnk[i]$ that will do .（ You can know that the complexity of this is very low , Because of the above " The number of elements with the most occurrences will only increase or decrease by one ")

At the same time, because the inquiry is a continuous interval , So I think of Mo team , The complexity can be controlled within $O(n\sqrt{n})$ within .

    #include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int maxn=3e5+50;
    int n,q;
    int a[maxn],ans[maxn],rnk[maxn],cnt[maxn];
    int nowl=1,nowr=0,nowans=0;
    struct qu
    {
    
        int l,r,num;
    }query[maxn];
     
    bool cmp(qu a,qu b)
    {
    
        int t=sqrt(n);
        if(a.r/t!=b.r/t)return a.r/t<b.r/t;
        return a.l<b.l;
    }
     
    void add(int x)
    {
    
        if(cnt[a[x]]>0)rnk[cnt[a[x]]]--;
        cnt[a[x]]++;
        rnk[cnt[a[x]]]++;
        nowans=max(nowans,cnt[a[x]]);
    }
    void del(int x)
    {
    
        rnk[cnt[a[x]]]--;
        cnt[a[x]]--;
        rnk[cnt[a[x]]]++;
        while(rnk[nowans]==0)nowans--;
    }
     
    int main()
    {
    
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=q;i++)
        {
    
            scanf("%d%d",&query[i].l,&query[i].r);
            query[i].num=i;
        }
        sort(query+1,query+1+q,cmp);
        for(int i=1;i<=q;i++)
        {
    
            while(nowr<query[i].r)
            {
    
                nowr++;
                add(nowr);
            }
            while(nowl>query[i].l)
            {
    
                nowl--;
                add(nowl);
            }
            while(nowr>query[i].r)
            {
    
                del(nowr);
                nowr--;
            }
            while(nowl<query[i].l)
            {
    
                del(nowl);
                nowl++;
            }
    // cout<<nowans<<' '<<"aa"<<endl;
            if(nowans<=(query[i].r-query[i].l+1+1)/2)ans[query[i].num]=1;
            else ans[query[i].num]=max(1,nowans-(query[i].r-query[i].l+1-nowans));
        }
        for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
       	return 0;
    }

But as far as this topic is concerned, we can do many things , There are two kinds of feelings that are very meaningful .
1、 If a number in the interval exceeds $(n+1)/2$ Time , Then it must appear in some sub interval more than $(n+1)/2$ Time （ Otherwise, the contradiction ）, So we only need to use the segment tree to deal with each interval exceeding $(n+1)/2$ The number of times , And then separately $check$ that will do .
2、 If a number in the interval exceeds $(n+1)/2$ Time , Then let's take a random position , The probability of randomly reaching this number is greater than $1/2$, So we randomly $n$ Time ,$check$ Value obtained each time , The probability of finding this number is very high .
notes ：check Just a simple two-point subscript ~

Also learned by the way , For occurrences greater than $(n+1)/2$ We have a Moore voting algorithm that can $O(n)$ Find out …
$bytheway$ We can also review some cold knowledge about the median , For an interval, we can divide it into two numbers , Then count the number of numbers greater than this number and less than this number , Come on $check$, Complexity is $O(nlogn)$.