# [code + 1] Yazid's freshman ball

2021-08-08 00:30:56 mrclr

delivery

I took the original question in the competition , Gu Zige pushed out a very complex line segment tree , I didn't expect it to be a positive solution .

Our enumeration size is $$x$$ Number of numbers , So if in the interval $$[L, R]$$ in ,$$x$$ Meet the requirements of the topic , remember $$num[i]$$ by $$1$$ To $$i$$ in $$x$$ Number of occurrences of , So there are $$\frac{num[R] - num[L - 1]}{R - L + 1} > \frac1{2}$$, Put it in order $$2num[R] - R > 2num[L - 1] - (L - 1)$$
So we make $$b[i] = 2num[i] - i$$, It becomes to count $$b[j] < b[i](j < i)$$ I've got a lot of them .

Use whatever data structure to maintain , For size $$x$$ Statistics of the number of , It's about to reach $$O(n^2logn)$$ Complexity .

But every time from $$1$$ To $$n$$ Of course not , So we thought , Can you just traverse $$x$$ Position of appearance .

remember $$i$$ by $$x$$ The location of this occurrence ,$$nxt[i]$$ by $$x$$ The next place , So we have to find all the... Quickly $$j$$, Satisfy $$b[j] < b[i], j < i, i \in [i, nxt[i] - 1]$$.

about $$(i, nxt[i] - 1]$$ Medium $$b[i]$$, Yes $$b[i] = b[i - 1] - 1$$, So what you want to query is actually a continuous prefix and , namely $$sum[b[i]], sum[b[i]-1], \cdots, sum[b[i] - (nxt[i] - i - 1)]$$.

Because there are still changes , Therefore, we are inspired to use the segment tree to maintain the prefix and , That is, each node maintains the sum of all numbers less than or equal to the right endpoint .

Then the above inquiry is equivalent to the interval $$[b[i] - (nxt[i] - i - 1) - 1, b[i] - 1]$$ The query .

And modify , If you add a number $$t$$, Because it maintains prefixes and , To set the interval $$[t, n]$$ all $$1$$. But now we should put $$[i, nxt[i] - 1]$$ All contributions are added to the segment tree , About to $$[b[i], n],[b[i] - 1, n], \cdots, [b[i] - (nxt[i] - i), n]$$ Add it all $$1$$.

Think about it a little bit , Will find , In fact, it is the interval $$[b[i] - (nxt[i] - i), b[i]]$$ Add a first item as 1 A series of equal proportions , Then put the interval $$[b[i] + 1, n]$$ Add $$nxt[i] - i$$. Therefore, the segment tree should support interval addition and interval addition arithmetic sequence , And sum intervals .

Add equal ratio sequence , Convert to absolute subscript , Maintaining a one-time function .

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
//#define int long long
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5e5 + 5;
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}

int n, a[maxn];

int pos[maxn], nxt[maxn];
struct Tree
{
int l, r;
bool cl;
ll lzi, lzy, sum;
In void Clear()
{
cl = 1;
lzi = lzy = sum = 0;
}
}t[maxn << 3];
In void build(int L, int R, int now)
{
t[now].l = L, t[now].r = R;
if(L == R) return (void)t[now].Clear();
int mid = (L + R) >> 1;
build(L, mid, now << 1), build(mid + 1, R, now << 1 | 1);
}
In void Change(int now, ll d1, ll d2)
{
int len = t[now].r - t[now].l + 1;
t[now].lzi += d1;
t[now].sum += (d1 * (1LL * t[now].l + t[now].r) * len >> 1);
t[now].lzy += d2;
t[now].sum += d2 * len;
}
In void pushdown(int now)
{
if(t[now].cl) t[now << 1].Clear(), t[now << 1 | 1].Clear(), t[now].cl = 0;
if(t[now].lzi || t[now].lzy)
{
Change(now << 1, t[now].lzi, t[now].lzy);
Change(now << 1 | 1, t[now].lzi, t[now].lzy);
t[now].lzi = t[now].lzy = 0;
}
}
In void update(int L, int R, int now, int d1, int d2)
{
if(L > R) return;
if(t[now].l == L && t[now].r == R)
{
Change(now, d1, d2);
return;
}
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(R <= mid) update(L, R, now << 1, d1, d2);
else if(L > mid) update(L, R, now << 1 | 1, d1, d2);
else update(L, mid, now << 1, d1, d2), update(mid + 1, R, now << 1 | 1, d1, d2);
t[now].sum = t[now << 1].sum + t[now << 1 | 1].sum;
}
In ll query(int L, int R, int now)
{
if(t[now].l == L && t[now].r == R) return t[now].sum;
pushdown(now);
int mid = (t[now].l + t[now].r) >> 1;
if(R <= mid) return query(L, R, now << 1);
else if(L > mid) return query(L, R, now << 1 | 1);
else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1) ;
}

In ll solve(int p)
{
nxt = p;
int x = 0, num = 0; ll ret = 0;
while(x <= n)
{
if(x > 0) num++;
int val = (num << 1) - x, tp = nxt[x] - x - 1;
ret += query(val - tp - 1, val - 1, 1);
update(val - tp, val, 1, 1, -(val - tp - 1));
update(val + 1, n, 1, 0, tp + 1);
x = nxt[x];
}
t.Clear();
return ret;
}

int main()
{
for(int i = 1; i <= n; ++i) a[i] = read(), pos[i - 1] = n + 1;
for(int i = n; i; --i) nxt[i] = pos[a[i]], pos[a[i]] = i;
Mem(pos, 0);		// Repeated use
build(-n, n, 1);
ll ans = 0;
for(int i = 1; i <= n; ++i) if(!pos[a[i]]) ans += solve(i), pos[a[i]] = 1;
write(ans), enter;
return 0;
}


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.


https://chowdera.com/2021/08/20210808003020469S.html