[code+月赛]Yazid的新生舞会

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

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

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

#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的新生舞会所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。