当前位置:网站首页>[Code+#1]Yazid 的新生舞会

[Code+#1]Yazid 的新生舞会

2021-08-08 00:30:28 mrclr

 传送


这题比赛的时候考了原题,顾子哥推了出来一个挺复杂的线段树,没想到竟然是正解。


我们枚举大小为\(x\)的数,那么如果在区间\([L, R]\)中,\(x\)符合题目的条件,记\(num[i]\)为\(1\)到\(i\)中\(x\)的出现次数,那么有\(\frac{num[R] - num[L - 1]}{R - L + 1} > \frac1{2}\),整理得$$2num[R] - R > 2num[L - 1] - (L - 1)$$
所以我们令\(b[i] = 2num[i] - i\),就变成了要统计\(b[j] < b[i](j < i)\)的个数了。

随便用什么数据结构维护,对于大小为\(x\)的数的统计,大概能达到\(O(n^2logn)\)的复杂度。


但每次从\(1\)到\(n\)扫一遍当然不行,所以我们想,能不能只遍历\(x\)出现的位置。

记\(i\)为\(x\)这一次出现的位置,\(nxt[i]\)为\(x\)下一次出现的位置,那么我们要快速的找到所有的\(j\),满足\(b[j] < b[i], j < i, i \in [i, nxt[i] - 1]\).

对于\((i, nxt[i] - 1]\)中的\(b[i]\),有\(b[i] = b[i - 1] - 1\),那么要查询的实际是连续的一段前缀和,即\(sum[b[i]], sum[b[i]-1], \cdots, sum[b[i] - (nxt[i] - i - 1)]\).

因为还要有修改,遂启发我们用线段树维护前缀和,即每个节点维护小于等于右端点的所有数的和。

那么上述的询问就相当于对区间\([b[i] - (nxt[i] - i - 1) - 1, b[i] - 1]\)进行查询。

而修改,如果加入一个数\(t\),因为维护的是前缀和,要对区间\([t, n]\)都加\(1\)。但是现在我们应该把\([i, nxt[i] - 1]\)的贡献全部加入线段树中,即将区间\([b[i], n],[b[i] - 1, n], \cdots, [b[i] - (nxt[i] - i), n]\)全部加\(1\)。

稍微想一下,会发现,其实是将区间\([b[i] - (nxt[i] - i), b[i]]\)加一个首项为1的等比数列,再将区间\([b[i] + 1, n]\)加\(nxt[i] - i\).所以线段树要支持区间加和区间加等差数列,以及求区间和。


加等比数列,转换成绝对下标即可,维护一个一次函数而已。

#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;
In ll read()
{
	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[0] = 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[1].Clear();
	return ret;
}

int main()
{
	n = read(); int TYPE = read();
	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);		//重复利用 
	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.
 
 
 
 

版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15234622/3310232

随机推荐