Yazid的新生舞会(线段树)

link

题意：问所有满足出现次数严格超过一半的数的区间数。

思路：
算出公式套出线段树，建议歪着头看，参考大佬的思路，计算每个数的贡献，在计算每个贡献的时候，记录前缀数组，匹配了就加一，不匹配就减1，类似leetcode刷到的摩尔投票法，当一段区间>0其中出现次数最多的数一定超过一半。我们发现所有为匹配的位置加起来才n个，也就是-1的个数特别多，然后每一段里面的贡献为0，从前往后推考虑前面对面的影响，然后推柿子就行了，记录权值线段树维护sumi和sum。复杂度O(n*log(n))

// #pragma GCC target("avx")
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
// created by myq 
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef pair<int,int> pii;
const int N = 1000010;
const int mod=998244353;
const int EPS=N/2;
vector<int>v[N];
struct node{
int l;
int r;
int len;
ll sum;
ll sumi;
ll i;
ll lz;
}tr[N<<2];
int a[N];
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
tr[u].sumi=tr[u<<1].sumi+tr[u<<1|1].sumi;
tr[u].i=tr[u<<1].i+tr[u<<1|1].i;
}
void pushdown(int u)
{
if(tr[u].lz)
{
tr[u<<1].lz+=tr[u].lz;
tr[u<<1|1].lz+=tr[u].lz;
tr[u<<1].sum+=tr[u].lz*tr[u<<1].len;
tr[u<<1].sumi+=tr[u].lz*tr[u<<1].i;
tr[u<<1|1].sumi+=tr[u].lz*tr[u<<1|1].i;
tr[u<<1|1].sum+=tr[u].lz*tr[u<<1|1].len;
tr[u].lz=0;
}
}
void build(int u,int l,int r)
{
tr[u]={l,r,r-l+1,0,0};
if(l==r)
{
tr[u].i=l-EPS;
return ;
}
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int d)
{
if(tr[u].l>=l&&tr[u].r<=r)
{
tr[u].sum-=tr[u].len*d;
tr[u].sumi-=tr[u].i*d;
tr[u].lz+=d;
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid)	modify(u<<1,l,r,d);
if(r>mid)	modify(u<<1|1,l,r,d);
pushup(u);
}
ll querysumi(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r)	return tr[u].sumi;
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
ll sumi=0;
if(l<=mid)	sumi+=querysumi(u<<1,l,r);
if(r>mid)	sumi+=querysumi(u<<1|1,l,r);
return sumi;
}
ll	querysum(int u,int l,int r)
{
if(tr[u].l>=l && tr[u].r<=r)	return tr[u].sum;
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
ll sum=0;
if(l<=mid)	sum+=querysum(u<<1,l,r);
if(r>mid)	sum+=querysum(u<<1|1,l,r);
return sum;
}
inline int get(int x)
{
return x+EPS;
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int n,type;
cin>>n>>type;
for(int i=0;i<n;i++)
v[i].push_back(0);
for(int i=1;i<=n;i++)
{
cin>>a[i];
v[a[i]].push_back(i);
}
for(int i=0;i<n;i++)
v[i].push_back(n+1);
//
return 0; 
build(1,0,N-1);
ll res=0;
for(int i=0;i<n;i++)
{
if(v[i].size()==2)	continue;
modify(1,get(0),get(0),1);
int sum = 0;
for(int j=1;j<v[i].size();j++)
{
if(v[i][j]!=v[i][j-1]+1)
{
int l=sum-(v[i][j]-v[i][j-1]-1); int r=sum-1;// 计算数列的贡献
cout<<l<<" "<<r<<endl;
res-=querysumi(1,get(l),get(r-1));
res+=r*querysum(1,get(l),get(r-1));
res+=querysum(1,0,get(l-1))*(r-l+1);
sum=l;
//修改
modify(1,get(l),get(r),-1);
}
if(v[i][j]!=n+1) //计算单点的贡献
{
sum++;
modify(1,get(v[i][j]),get(v[i][j]),1);
}
}
//清空	
modify(1,get(0),get(0),-1);
for(int j=1;j<v[i].size();j++)
{
if(v[i][j]!=v[i][j-1]+1)
{
int l=sum-(v[i][j]-v[i][j-1]-1); int r=sum-1;// 计算数列的贡献
sum=l;
//修改
modify(1,get(l),get(r),1);
}
if(v[i][j]!=n+1) //计算单点的贡献
{
sum++;
modify(1,get(v[i][j]),get(v[i][j]),-1);
}
}
}
cout<<res<<endl;
return 0;
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/

现

最后

以上就是漂亮煎饼为你收集整理的Yazid的新生舞会(线段树)的全部内容，希望文章能够帮你解决Yazid的新生舞会(线段树)所遇到的程序开发问题。

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