# Yazid's freshman ball (thread tree)

2021-08-08 15:41:34

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

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

https://chowdera.com/2021/08/20210808153459062d.html