CF1415D-Cut and Stick (Round 716 div.2)

大佬教程收集整理的这篇文章主要介绍了CF1415D-Cut and Stick (Round 716 div.2)，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

CF1514D-Cut and Stick

题意

给定一个长度为(n)的序列((n≤10^5))，可以对其进行三种操作： 1.把一段区间片段中所有的数从原来的区间里剪下来 2.把这些数按照在原来序列里的排列顺序重新拼接成序列 3.最后形成一个或者多个片段的序列，使最开始的序列中每一个数都属于某一个片段。 要求：给定(q)个询问((q≤10^5))，每次给出一个区间的左右端点，将这个区间分成若干个片段，使得每个片段内任意元素出现的次数不严格大于(lceilfrac{x}{2}rceil)(x为该片段长度)。求可以分成的最少片段数目。

输入

第一行输入两个整数(n)和(p)。 第二行输入(n)个整数，对应在原序列中的值。 第(3)～(q+2)行，每行输入两个整数，分别表示询问的区间左端点和右端点。

输出

对于每个询问，输出一个整数，表示询问区间分成的最少片段。

本来应该是可以切掉的。。但全把时间放在T3了，，

大概是给一个取值范围[1,n]数列和若干区间询问，求最少分成多少段可以让分成的片段没有绝对众数。

注意这里的分段可以是不相邻的数先分割然后合并，只需要相对顺序不变即可。那么只需要拆出众数里多出来的那一部分，剩下的恰好可以使得不超过(ceil)1/2，若本来没有绝对众数则直接输出1。

那么可以转化为求区间众数（的出现次数）的问题，这可以用主席树解决。主席树维护出现次数总和，每次先考察左右儿子的次数总和哪一个比较大，往大的方向搜索下去即可。

#include <bits/stdc++.h>
using namespace std;
#define mid ((lo+ro)/2)
const int maxn=3e5+10;
int n,q;
int yuan[maxn];
struct node{
    int lo;int ro;int zhi;
}all[maxn*40];
int rt[maxn],tot;
void build(int &now,int lo,int ro){
    now=++tot;
    if(lo==ro) return;
    build(all[now].lo,lo,mid);
    build(all[now].ro,mid+1,ro);
}
void pushup(int now,int lo,int ro){all[now].zhi=all[lo].zhi+all[ro].zhi;}
void upd(int &now1,int now2,int lo,int ro,int pos,int zhi){
    now1=++tot;all[now1]=all[now2];
    if(lo==ro&&ro==pos){all[now1].zhi++;return;}
    if(pos<=mid) upd(all[now1].lo,all[now2].lo,lo,mid,pos,zhi);
    else upd(all[now1].ro,all[now2].ro,mid+1,ro,pos,zhi);
    pushup(now1,all[now1].lo,all[now1].ro);
}
ll req(int now1,int now2,int lo,int ro){
    if(lo==ro){return all[now1].zhi-all[now2].zhi;}
    int lo1=all[all[now1].lo].zhi-all[all[now2].lo].zhi;
    int ro1=all[all[now1].ro].zhi-all[all[now2].ro].zhi;
    ll ans1=0;
    if(lo1>=ro1) ans1=max(ans1,req(all[now1].lo,all[now2].lo,lo,mid));
    if(lo1<=ro1) ans1=max(ans1,req(all[now1].ro,all[now2].ro,mid+1,ro));
    return ans1;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>yuan[i];
    build(rt[0],1,n);
    for(int i=1;i<=n;i++){
        upd(rt[i],rt[i-1],1,n,yuan[i],1);
    }
    while(q--){
        int a1,a2;cin>>a1>>a2;
        int mxcnt=req(rt[a2],rt[a1-1],1,n);
        if(mxcnt<=ceil((a2-a1+1)/2)){Cout<<1<<endl;}
        else{
            int len=a2-a1+1;int ban=len/2;
            cout<<2*mxcnt-len<<endl;
        }
    }
    return 0;
}

大佬总结

以上是大佬教程为你收集整理的CF1415D-Cut and Stick (Round 716 div.2)全部内容，希望文章能够帮你解决CF1415D-Cut and Stick (Round 716 div.2)所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。