【BZOJ5110】[CodePlus2017]Yazid 的新生舞会 线段树

时间:2022-08-27 13:12:00

【BZOJ5110】[CodePlus2017]Yazid 的新生舞会

Description

Yazid有一个长度为n的序列A,下标从1至n。显然地,这个序列共有n(n+1)/2个子区间。对于任意一个子区间[l,r],如果该子区间内的众数在该子区间的出现次数严格大于(r?l+1)/2(即该子区间长度的一半),那么Yazid就说这个子区间是"新生舞会的"。所谓众数,即为该子区间内出现次数最多的数。特别地,如果出现次数最多的数有多个,我们规定值最小的数为众数。现在,Yazid想知道,共有多少个子区间是"新生舞会的"

Input

第一行2个用空格隔开的非负整数n,type,表示序列的长度和数据类型。数据类型的作用将在子任务中说明。
第二行n个用空格隔开的非负整数,依次为A1,A2,...,An,描述这个序列。
N<=500000,0<=Type<=3
对于所有数据,保证 0 ≤ Ai ≤ n ? 1。
对于 type = 0 的数据,没有任何特殊约定。
对于 type = 1 的数据,保证 Ai ∈ {0, 1}。
对于 type = 2 的数据,保证序列 A 的众数在整个序列中的出现次数不超过 15。
对于 type = 3 的数据,保证 Ai ≤ 7。

Output

输出一行一个整数,表示答案。

Sample Input

5 0
1 1 2 2 3

Sample Output

10
//"新生舞会的" 子区间有 [1, 1], [1, 2], [1, 3], [2, 2], [2, 4], [3, 3],
[3, 4], [3, 5], [4, 4], [5, 5]共 10 个。

题解:考虑枚举众数,我们用vector维护每种数的所有出现位置,然后我们将这个数的所有位置看成+1,其它位置看成-1,于是答案就变成了求多少区间的和>0。

我们考虑将所有连续的-1合并到一起,这样的话连续-1的个数就不会超过+1的个数+1了,然后枚举右端点。因为区间和可以看成前缀相减,所以我们用s[i]表示前缀和,那么我们要统计的就是左面有多少s[j]<s[i],自然想到用线段树来维护有多少个数的s值等于一个数。那么,对于一个+1,我们可以用简单的线段树区间求和搞定;对于一段-1,这段区间对答案的贡献就是$\sum\limits_{i=1}^{r-l+1}\sum\limits_{j=-\infty}^{s[l-1]-1-i}cnt[j]$(cnt表示有多少个数的s等于j)。发现这个东西可以用线段树维护cnt[i]和i*cnt[i]来实现,于是此题就做完了。

但是由于BZ太慢了,所以搞了若干个卡常小优化才过~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=500010;
typedef long long ll;
ll ans;
int n;
vector<int> p[maxn];
int s1[maxn<<3],z1[maxn<<3];
ll s2[maxn<<3],z2[maxn<<3];
int tag[maxn<<3];
bool clr[maxn<<3];
inline void pushdown(int x)
{
if(clr[x]) clr[lson]=clr[rson]=1,s1[lson]=s1[rson]=s2[lson]=s2[rson]=tag[lson]=tag[rson]=clr[x]=0;
if(tag[x]) s1[lson]+=z1[lson]*tag[x],s1[rson]+=z1[rson]*tag[x],s2[lson]+=z2[lson]*tag[x],s2[rson]+=z2[rson]*tag[x],tag[lson]+=tag[x],tag[rson]+=tag[x],tag[x]=0;
}
void build(int l,int r,int x)
{
if(l==r)
{
z1[x]=1,z2[x]=l;
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
z1[x]=z1[lson]+z1[rson],z2[x]=z2[lson]+z2[rson];
}
void updata(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b)
{
s1[x]+=z1[x],s2[x]+=z2[x],tag[x]++;
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a,b);
if(b>mid) updata(mid+1,r,rson,a,b);
s1[x]=s1[lson]+s1[rson],s2[x]=s2[lson]+s2[rson];
}
int query1(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s1[x];
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query1(l,mid,lson,a,b);
if(a>mid) return query1(mid+1,r,rson,a,b);
return query1(l,mid,lson,a,b)+query1(mid+1,r,rson,a,b);
}
ll query2(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s2[x];
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query2(l,mid,lson,a,b);
if(a>mid) return query2(mid+1,r,rson,a,b);
return query2(l,mid,lson,a,b)+query2(mid+1,r,rson,a,b);
}
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
int ret=0,f=1; char gc=nc();
while(!isdigit(gc)) {if(gc=='-') f=-f; gc=nc();}
while(isdigit(gc)) ret=ret*10+(gc^'0'),gc=nc();
return ret*f;
}
int main()
{
n=rd(),rd();
register int i,j,l,r,sum;
for(i=1;i<=n;i++) j=rd(),p[j].push_back(i);
build(-n,n,1);
for(i=0;i<n;i++) if(p[i].size())
{
s1[1]=s2[1]=tag[1]=sum=0,clr[1]=1;
p[i].push_back(n+1);
updata(-n,n,1,0,0);
for(j=0;j<(int)p[i].size();j++)
{
if((!j&&p[i][j]>1)||(j&&p[i][j]>p[i][j-1]+1))
{
l=(!j)?1:(p[i][j-1]+1),r=p[i][j]-1;
if(j) ans+=query1(-n,n,1,-n,sum-1)*(r-l+1)-query2(-n,n,1,sum-(r-l+1),sum-1)+query1(-n,n,1,sum-(r-l+1),sum-1)*(sum-1-(r-l+1));
updata(-n,n,1,sum-(r-l+1),sum-1);
sum-=(r-l+1);
}
if(j!=(int)p[i].size()-1) sum++,ans+=query1(-n,n,1,-n,sum-1),updata(-n,n,1,sum,sum);
}
}
printf("%lld",ans);
return 0;
}//5 0 1 1 0 1 1

【BZOJ5110】[CodePlus2017]Yazid 的新生舞会 线段树的更多相关文章

  1. BZOJ&period;5110&period;&lbrack;CodePlus2017&rsqb;Yazid 的新生舞会&lpar;线段树&sol;树状数组&sol;分治&rpar;

    LOJ BZOJ 洛谷 又来发良心题解啦 \(Description\) 给定一个序列\(A_i\).求有多少个子区间,满足该区间众数出现次数大于区间长度的一半. \(n\leq5\times10^5 ...

  2. bzoj5110&colon; &lbrack;CodePlus2017&rsqb;Yazid 的新生舞会

    Description Yazid有一个长度为n的序列A,下标从1至n.显然地,这个序列共有n(n+1)/2个子区间.对于任意一个子区间[l,r] ,如果该子区间内的众数在该子区间的出现次数严格大于( ...

  3. 「CodePlus 2017 11 月赛」Yazid 的新生舞会(树状数组&sol;线段树)

    学习了新姿势..(一直看不懂大爷的代码卡了好久T T 首先数字范围那么小可以考虑枚举众数来计算答案,设当前枚举到$x$,$s_i$为前$i$个数中$x$的出现次数,则满足$2*s_r-r > 2 ...

  4. 【bzoj5110】Yazid的新生舞会

    这里是 $THUWC$ 选拔时间 模拟赛的时候犯 $SB$ 了,写了所有的部分分,然后直接跑过了 $4$ 个大样例(一个大样例是一个特殊情况)…… 我还以为我非常叼,部分分都写对了,于是就不管了…… ...

  5. 【BZOJ5110】&lbrack;CodePlus2017&rsqb;Yazid 的新生舞会

    题解: 没笔的时候我想了一下 发现如果不是出现一半次数而是k次,并不太会做 然后我用前缀和写了一下发现就是维护一个不等式: 于是就可以随便维护了

  6. 【bzoj5110】&lbrack;CodePlus2017&rsqb;Yazid 的新生舞会 Treap

    题目描述 求一个序列所有的子区间,满足区间众数的出现次数大于区间长度的一半. 输入 第一行2个用空格隔开的非负整数n,type,表示序列的长度和数据类型.数据类型的作用将在子任务中说明. 第二行n个用 ...

  7. luogu P4062 &lbrack;Code&plus;&num;1&rsqb;Yazid 的新生舞会(线段树&plus;套路)

    今天原来是平安夜啊 感觉这题是道好题. 一个套路枚举权值\(x\),把权值等于\(x\)的设为1,不等于的设为-1,然后问题转化为多少个区间权值和大于. 发现并不是很好做,还有一个套路,用前缀和查分来 ...

  8. 【线段树】【P4062】 &lbrack;Code&plus;&num;1&rsqb;Yazid 的新生舞会

    Description 给定一个长度为 \(n\) 的序列,求有多少子区间满足区间众数严格大于区间长度的一半.如果区间有多个出现次数最多且不同的数则取较小的数为众数. Limitation 对于全部的 ...

  9. 洛谷 P4062 - &lbrack;Code&plus;&num;1&rsqb;Yazid 的新生舞会(权值线段树)

    题面传送门 题意: 给出一个序列 \(a\),求 \(a\) 有多少个子区间 \([l,r]\),满足这个区间中出现次数最多的数出现次数 \(>\dfrac{r-l+1}{2}\) \(1 \l ...

随机推荐

  1. Codeforces 734E&period; Anton and Tree 搜索

    E. Anton and Tree time limit per test: 3 seconds memory limit per test :256 megabytes input:standard ...

  2. 右下角弹出&quot&semi;Windows-延缓写入失败&quot&semi;或者&quot&semi;xxx-损坏文件 请运行Chkdsk工具&quot&semi;

    知识点分析: 任务栏右下角弹出“Windows-延缓写入失败”或者“xxx-损坏文件 请运行Chkdsk工具”. 操作步骤: 方法一:Chkdsk工具 在开始---运行中输入cmd,然后输入chkds ...

  3. cocos2dx 2&period;14使用UUID

    1首先要清楚objective-c 与c/ c++混编的规则 关于c/c++/obj-c的混合使用 1)obj-c的编译器处理后缀为m的文件时,可以识别obj-c和c的代码,处理mm文件可以识别obj ...

  4. rsyslog 收集系统日志

    <pre name="code" class="html">nginx 服务器配置: jrhwpt01:/root# cat /etc/rsyslo ...

  5. BZOJ 3155&colon; Preprefix sum&lpar; 线段树 &rpar;

    刷刷水题... 前缀和的前缀和...显然树状数组可以写...然而我不会, 只能写线段树了 把改变成加, 然后线段树维护前缀和, 某点p加, 会影响前缀和pre(x)(p≤x≤n), 对[p, n]这段 ...

  6. linq any&lpar;&rpar; all&lpar;&rpar; 返回true 或者false

    一.any()只要有一个符合条件就返回true static void Main(string[] args) { //any 有符合条件的就返回true ,,,,,,,,,}; ); Console ...

  7. Python package install血泪史

    [前言][絮絮叨叨篇]:说实话,不是第一次安装Python库了,但是貌似没有特别顺利的时候,可能还是遇到的困难不够多咯.配置环境真是个糟心的事儿,不过作为菜鸟,还是得磨练磨练,毕竟某人云:" ...

  8. Linux常见命令(五)——rmdir

      前  言 JRedu 今天我们来介绍第五个命令:rmdir . 命令英文原意:remove empty directories 命令用途: rmdir:删除空目录,非空的目录不能删除 本章内容将详 ...

  9. Python&plus;Requests接口测试教程(2):

    开讲前,告诉大家requests有他自己的官方文档:http://cn.python-requests.org/zh_CN/latest/ 2.1 发get请求 前言requests模块,也就是老污龟 ...

  10. PhiloGL学习(3)——程序员的法宝—键盘、鼠标

    前言 上一篇文章中介绍了如何让对象动起来,本文介绍如何让场景响应我们的鼠标和键盘以控制场景的缩放及对象的转动和移动等. 一. 原理分析 有了上一篇文章的基础,我们已经知道了如何让场景和对象动起来.本文 ...