首页 > 其他分享 >P8313 [COCI2021-2022#4] Izbori

P8313 [COCI2021-2022#4] Izbori

时间:2023-10-11 15:15:25浏览次数:51  
标签:COCI2021 端点 P8313 int SegT fa tag il 2022

\(\text{Links}\)

原题传送门


题意

求给定序列中有多少个子区间满足众数出现次数严格大于区间长度的一半。


题解

题目要求满足条件的子区间,一个很直接的想法是每次固定左(右)端点,求有多少个右(左)可以与其匹配对答案造成贡献。

那么考虑一个暴力做法:每次固定左端点,然后往后面一直扫,枚举每个右端点,中途记录众数出现次数,然后依次判断即可。时间复杂度为 \(O(n^2)\)。

这肯定是过不了的,那么我们再从条件入手,注意到:

  • 严格大于区间长度的一半

于是就说明每个区间对应的这个众数只会有一个!考虑利用一下这个性质。

那么我们可以枚举这个众数。设我们当前枚举的众数为 \(x\),记录一个数组 \(s\),\(s_i\) 表示前 \(i\) 个数中 \(x\) 的出现次数。

沿用上面固定一个端点求另一个合法端点数量的思路,对于一个右端点 \(r\),合法的左端点 \(l\) 显然应该满足:

\[l \le r,s_r-s_{l-1}\gt \frac{r-(l-1)}{2} \]

\(l-1\) 看着有点烦(,把 \(-1\) 去掉,变成:

\[l\lt r ,s_r-s_l\gt \frac{r-l}{2} \]

不等式两边同时 \(\times 2\):

\[l\lt r,2s_r-2s_l\gt r-l \]

移项得:

\[l\lt r,2s_r-r\gt 2s_l-l \]

记 \(s'_i=2s_i-i\),则:

\[l\lt r,s'_r\gt s'_l \]

经典问题,树状数组维护即可。但时间复杂度为 \(O(n^2\log n)\),甚至不如 \(O(n^2)\) 暴力(悲。

那么我们考虑整体观察一下序列 \(s'\),说不定能发现什么(。

显然地,如果满足 \(a_i=x\) 的若干个 \(i\) 的的位置都确定了,那么整个 \(s'\) 序列就可以确定了,所以我们要想办法只用这些 \(i\) 的位置来计算答案,使得每次的时间复杂度都只与 \(m\) 相关,其中 \(m\) 为这些 \(i\) 的数量。再因为 \(\sum m=n\),于是可以大幅降低总时间复杂度。

记 \(d\) 为 \(s'\) 的差分序列,那么如果 \(a_i=x\),则有 \(d_i=1\),否则 \(d_i=-1\),我们把前者中的 \(i\) 视为一个“断点”,那么整个 \(s'\) 序列就是若干个公差为 \(-1\) 的等差数列“首尾衔接”拼在一起。

因为公差为 \(-1\),即单调递减,所以每一个等差数列内部是不会产生任何贡献的,那么我们考虑把每个等差数列视作整体,看它前面的等差数列可以产生多少贡献。

沿用上面树状数组的做法,开一个 \(t\),\(t_i\) 表示 \(s'\) 值为 \(i\) 的位置有多少个,因为每次要查询小于某个值的数量,所以把它记成前缀和的形式,记 \(v\) 为它的前缀和序列。那么对于每个右端点 \(r\),它的答案显然是 \(v_{s'_r-1}\)。我们把每一段等差数列的贡献写下来就是:

\[\sum_{i=fir}^{lst}v_{i-1} \]

然后它又可以写成两个前缀和相减的形式,也就成了 \(t\) 序列的二阶前缀和,那么我们就需要在这个桶上面实现:区间加(插入一个等差数列),维护二阶前缀和。

呵,果然又变成大力 ds 了是吧

线段树和树状数组都可以维护,在我看来各有优势吧,线段树写此题代码的时候比较容易理解,好写一点,但这题树状数组的常数吊打线段树。

这里给出线段树的实现方式:

代码实现中的细节:

1.因为 \(s'\) 序列中可能出现负数,所以要加上一定的偏差值给它强制转成正数。

2.离散化

3.long long

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=2e5+113;
int n,a[N],b[N],ans,dt,vmax;
pii lst[N];
bitset<N>solved;
vector<int>v[N];
struct SegT{
    int ans,sum,tag,l,r;
}L[N<<3];
#define ls (id<<1)
#define rs (id<<1|1)
il void Pushup(SegT &fa,SegT lson,SegT rson){
    fa.sum=lson.sum+rson.sum;
    int l=lson.l,mid=lson.r,r=rson.r;
    fa.ans=lson.ans+rson.ans+lson.sum*(r-mid);
}
il int Get(int x){
    return (x*(x+1))>>1;
}
il void Add(SegT &fa,int x){
    fa.tag+=x,fa.sum+=(fa.r-fa.l+1)*x,fa.ans+=Get(fa.r-fa.l+1)*x;
}
il void Pushdown(SegT &fa,SegT &lson,SegT &rson){
    if(!fa.tag)return;
    Add(lson,fa.tag),Add(rson,fa.tag);
    fa.tag=0;
}
il void Add(int id,int l,int r,int x,int y,int z){
    if(l>=x&&r<=y){
        Add(L[id],z);
        return;
    }
    Pushdown(L[id],L[ls],L[rs]);
    int mid=(l+r)>>1;
    if(x<=mid)Add(ls,l,mid,x,y,z);
    if(y>mid)Add(rs,mid+1,r,x,y,z);
    Pushup(L[id],L[ls],L[rs]);
}
il SegT GetAns(int id,int l,int r,int x,int y){
    if(l>=x&&r<=y)return L[id];
    Pushdown(L[id],L[ls],L[rs]);
    int mid=(l+r)>>1;
    SegT res;
    if(x<=mid&&y>mid){
        SegT Left=GetAns(ls,l,mid,x,y);
        SegT Right=GetAns(rs,mid+1,r,x,y);
        Pushup(res,Left,Right);
    }
    else if(x<=mid)res=GetAns(ls,l,mid,x,y);
    else res=GetAns(rs,mid+1,r,x,y);
    Pushup(L[id],L[ls],L[rs]);
    return res;
}
il void Build(int id,int l,int r){
    L[id]={0,0,0,l,r};
    if(l==r)return;
    int mid=(l+r)>>1;
    Build(ls,l,mid),Build(rs,mid+1,r);
}
il void solve(int x){
    solved[x]=1;
    int siz=v[x].size()-1,mx=dt,mn=dt;
    for(re int i=0;i<=siz;i++)
        b[i]=(i<<1)-v[x][i]+dt,mx=max(mx,b[i]),mn=min(mn,b[i]);
    for(re int i=0;i<=siz;i++){
        int r=b[i],l=(i==siz)?b[i]-(n-v[x][i]):b[i]-(v[x][i+1]-v[x][i]-1);
        ans+=GetAns(1,1,vmax,1,r-1).ans-GetAns(1,1,vmax,1,l-2).ans;
        Add(1,1,vmax,l,r,1);
    }
    for(re int i=0;i<=siz;i++){
        int r=b[i],l=(i==siz)?b[i]-(n-v[x][i]):b[i]-(v[x][i+1]-v[x][i]-1);
        Add(1,1,vmax,l,r,-1);
    }
}
il int read(){
    re int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
signed main(){
    n=read(),a[0]=read();
    dt=n+10,vmax=n+dt;
    for(re int i=1;i<=n;i++){
        a[i]=read();
        if(v[a[i]].empty())v[a[i]].push_back(0);
        v[a[i]].push_back(i);
    }
    Build(1,1,vmax);
    for(re int i=1;i<=n;i++)
        if(!solved[a[i]])solve(a[i]);
    cout<<ans;
    return 0;
}

标签:COCI2021,端点,P8313,int,SegT,fa,tag,il,2022
From: https://www.cnblogs.com/MrcFrst-LRY/p/17757099.html

相关文章

  • 2022-006 在bam中检查指定突变
     转载2022-006在bam中检查指定突变SSSimonYang个人微信公众号SSSimonYang​关注他 2人赞同了该文章需求检查突变在bam文件中存不存在。注意:以下操作均需要bam文件按坐标排序并建立索引。[email protected]_sorted.bam......
  • CSP-J/S 2022 游寄
    省流:J组:\(235\),一等线:\(215\)S组:\(185\),一等线:\(195\)蓝勾?9.18初赛。第一次线上考,鸡冻。上午是J,下午是S。在考试之前啊要弄一大坨什么答题设备的摄像头啊,什么监控设备的摄像头啊,万一停电了又要备摄像头啊……然后我现在家里有\(3\)个手机/摄像头支架,\(2\)台笔记本电脑......
  • 2021-2022 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2021) gym 104670
    原题容易想到最短路DAG求出来,起初我以为要求最小割,但这是错误的,因为可能有多条边联通了一个点的情况,这时候选择最小割不一定是最优的我们猜想一个思路:答案一定是包含\(1\)号节点的连通块全部填\(N\),剩下的填\(S\)。发现在最短路DAG中,\(1\rightarrown\)的所有路径......
  • 微软正式发布 C# 10,支持.NET 6 和 Visual Studio 2022 (附更新内容大全)
    微软正式发布C#10,支持.NET6和VisualStudio2022(附更新内容大全)2022/2/1211:24:36 来源:IT之家 作者:潇公子 责编:潇公子评论:0IT之家 2月12日消息,据微软中国MSDN,宣布C#10作为.NET6和VisualStudio2022的一部分已经发布了。在这篇文章中,微软将介绍C#......
  • P7928 [COCI2021-2022#1] Kamenčići
    P7928[COCI2021-2022#1]Kamenčići[P7928COCI2021-2022#1]Kamenčići-洛谷|计算机科学教育新生态(luogu.com.cn)目录P7928[COCI2021-2022#1]Kamenčići题目大意思路code题目大意Alice和Bob又在玩游戏。在他们面前有\(n\)块石头排成一行,石头有红和蓝两种颜......
  • P9474 [yLOI2022] 长安幻世绘
    题目意思:需要在元素互不相同的数列\(a\)中选出一个长度为\(m\)的元素互不相邻的子列,使得子列的极差最小。做法我们知道,对于一组数列,我们只需知道它的最大值和最小值,就可以得到它的极差。那么我们可以将数字从小到大排序,固定最小值,寻找最优的最大值,当最小值和最大值的位置固......
  • 2022 杭州 ICPC 补题 ACKG
    2022杭州ICPC补题ACKGhttps://codeforces.com/gym/104090笨成sb,啥也不会写完两个签到就坐牢(要补到银首,所以还差一个G题没补)说实话补了三题,感觉就是一些算法的延申,比如这一场的铜牌题其实考到的就是exgcd,Trie,背包dp,但是又不完全是单纯靠这个算法,需要你有一些引......
  • P8813 [CSP-J 2022] 乘方
    题目描述小文同学刚刚接触了信息学竞赛,有一天她遇到了这样一个题:给定正整数\(a\)和\(b\),求\(a^b\)的值是多少。\(a^b\)即\(b\)个\(a\)相乘的值,例如\(2^3\)即为\(3\)个\(2\)相乘,结果为\(2\times2\times2=8\)。“简单!”小文心想,同时很快就写出了一份程序,......
  • 2022 China Collegiate Programming Contest (CCPC) Mianyang Onsite
    2022ChinaCollegiateProgrammingContest(CCPC)MianyangOnsiteC.CatchYouCatchMe解题思路:站在距离出口最近的点等深度深的蝴蝶飞上来即可。时间复杂度:\(O(n)\)代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;voidsolve(){ intn......
  • 猿人学app2022-第一题
    抓包需要hooksslpinning//hook_ssl_pinningfunctionlogger(message){console.log(message);Java.perform(function(){varLog=Java.use("android.util.Log");Log.v("ssl_pinnig_bypass",message);});}Java.perform(functi......