当前位置:网站首页>Yazid's freshman ball (thread tree)

Yazid's freshman ball (thread tree)

2021-08-08 15:41:34 wx60d99ac3e878e

link

The question : Ask all interval numbers that satisfy the number of occurrences strictly more than half .

 Please add a picture description
Ideas :
Calculate the formula and set up the line segment tree , It is suggested to look at it with your head tilted , Refer to the thinking of the boss , Calculate the contribution of each number , When calculating each contribution , Record prefix array , If it matches, add one , Subtract if it doesn't match 1, similar leetcode Brush to the Moore voting method , When an interval >0 The number of occurrences must be more than half . We found that all the matching positions add up to n individual , That is to say -1 There are a lot of , Then the contribution in each paragraph is 0, Push from front to back and consider the impact of the front to the opposite , Then push the persimmon , Record weight segment tree maintenance sumi and sum. Complexity 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;//  Calculate the contribution of the sequence 
				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 
				modify(1,get(l),get(r),-1);
			}
			
			if(v[i][j]!=n+1) // Calculate the contribution of a single point 
			{
				sum++;
				modify(1,get(v[i][j]),get(v[i][j]),1);
			}
			
							
		}
						// Empty  
		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;//  Calculate the contribution of the sequence 
				sum=l;
				// modify 
				modify(1,get(l),get(r),1);
			}
			
			if(v[i][j]!=n+1) // Calculate the contribution of a single point 
			{
				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. **/




      
  • 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.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.
  • 94.
  • 95.
  • 96.
  • 97.
  • 98.
  • 99.
  • 100.
  • 101.
  • 102.
  • 103.
  • 104.
  • 105.
  • 106.
  • 107.
  • 108.
  • 109.
  • 110.
  • 111.
  • 112.
  • 113.
  • 114.
  • 115.
  • 116.
  • 117.
  • 118.
  • 119.
  • 120.
  • 121.
  • 122.
  • 123.
  • 124.
  • 125.
  • 126.
  • 127.
  • 128.
  • 129.
  • 130.
  • 131.
  • 132.
  • 133.
  • 134.
  • 135.
  • 136.
  • 137.
  • 138.
  • 139.
  • 140.
  • 141.
  • 142.
  • 143.
  • 144.
  • 145.
  • 146.
  • 147.
  • 148.
  • 149.
  • 150.
  • 151.
  • 152.
  • 153.
  • 154.
  • 155.
  • 156.
  • 157.
  • 158.
  • 159.
  • 160.
  • 161.
  • 162.
  • 163.
  • 164.
  • 165.
  • 166.
  • 167.
  • 168.
  • 169.
  • 170.
  • 171.
  • 172.
  • 173.
  • 174.
  • 175.
  • 176.
  • 177.
  • 178.
  • 179.
  • 180.
  • 181.
  • 182.
  • 183.
  • 184.
  • 185.
  • 186.
  • 187.
  • 188.
  • 189.
  • 190.
  • 191.
  • 192.

present

 

版权声明
本文为[wx60d99ac3e878e]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210808153459062d.html

随机推荐