我是靠谱客的博主 简单小海豚,这篇文章主要介绍[code+月赛]Yazid的新生舞会,现在分享给大家,希望可以做个参考。

用很有趣的方法做了这道题。

标算非常厉害,并没有想到。。
考虑求众数为x的区间数量,由序列a构造序列b, bx(i)=1+2[a(i)==x] ,作前缀和 sx(i)=sx(i1)+b(i)

ans=x=0n11j<in[sx(i)>sx(j)]

朴素的做法便是 O(n2logn) ,可以用树状数组维护。
然而神奇的是,我们可以每次插入、查询一个等差数列。(这里题解里说的是递减数列,但事实上我觉得递增数列也是一样的)
这样就变成了区间修改、区间查询,可以用线段树来实现。
当然差分一下就可以用树状数组了。

我是这样想的,考虑x后,i能够成为一个合法区间的右端点当且仅当i的最大后缀大于0,所以我们可以用求最大子段和的方式,相当于把那些+1向右推来填-1的坑,i是左端点时同理。此时,合法的区间必然在这一段段被填的坑里,那么我们按这些被填的坑组成的一段段序列来使用上面的朴素做法,便可以得到一个 O(nlogn) 的做法。
这个做法唯一的优点是脑洞比较大常数比较小可以拿来刷bzoj rank1

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h> using namespace std; typedef long long LL; char * cp=(char *)malloc(5000000); inline void in(int &x){ while(*cp<'0'||*cp>'9')++cp; for(x=0;*cp>='0'&&*cp<='9';)x=x*10+*cp++-'0'; } const int N=5e5+5,S=1e6+5; int n; int a[N],b[N]; int head[N],tail[N],nxt[N],lst[N]; bool flag[N]; int bit[S]; int B; inline void add(int x){ for(x+=n+1;x<=B;x+=x&-x)++bit[x]; } inline void del(int x){ for(x+=n+1;x<=B;x+=x&-x)bit[x]=0; } inline int query(int x){ int ans=0; for(x+=n+1;x;x-=x&-x)ans+=bit[x]; return ans; } int main(){ freopen("f.in","r",stdin); // freopen("f.out","w",stdout); fread(cp,1,5000000,stdin); in(n); B=n<<1|1; { int t; in(t); } for(int i=1;i<=n;++i)in(a[i]); for(int i=1;i<=n;++i){ lst[i]=tail[a[i]]; tail[a[i]]=i; } for(int i=n;i;--i){ nxt[i]=head[a[i]]; head[a[i]]=i; } LL ans=0; for(int i=n;i--;){ int x=0; for(int j=head[i];j;){ x=j; b[x]=1; for(int y=1;x<=n&&y>=0;++x,y+=b[x]=a[x]==i?1:-1)flag[x]=1; j=nxt[j]; while(j&&x>j)j=nxt[j]; } x=n; for(int j=tail[i];j;){ x=j; for(int y=1;x&&y>=0;--x,y+=b[x]=a[x]==i?1:-1)flag[x]=1; j=lst[j]; while(j&&x<j)j=lst[j]; } x=0; for(int j=head[i];j;){ x=j; while(x&&flag[x-1])--x; int l=x; add(0); for(int y=0;flag[x];++x){ y+=b[x]; add(y); ans+=query(y-1); } x=l; del(0); for(int y=0;flag[x];++x){ y+=b[x]; del(y); flag[x]=0; } j=nxt[j]; while(j&&j<=x)j=nxt[j]; } } printf("%lldn",ans); }

总结:
①竟然可以有批量查询、批量修改这种操作,看来我真的是老了。
②这道题听说可以分治?不知道怎么做,以后有时间/机会问/想一下吧。

最后

以上就是简单小海豚最近收集整理的关于[code+月赛]Yazid的新生舞会的全部内容,更多相关[code+月赛]Yazid内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(81)

评论列表共有 0 条评论

立即
投稿
返回
顶部