提升网站开发效率,培训ui设计公司,网站建设中页面,科技公司网站设计风格P4062 [Code#1]Yazid 的新生舞会
题意#xff1a;
给出一个序列#xff0c;求有多少个子区间满足众数的出现次数大于区间长度的一半。 出现次数大于区间长度的一般我们称之为绝对众数
题解#xff1a;
分治做法 对于一个区间[l,r]#xff0c;设mid⌊lr2⌋\lfloor \frac…P4062 [Code#1]Yazid 的新生舞会
题意
给出一个序列求有多少个子区间满足众数的出现次数大于区间长度的一半。 出现次数大于区间长度的一般我们称之为绝对众数
题解
分治做法 对于一个区间[l,r]设mid⌊lr2⌋\lfloor \frac{lr}{2} \rfloor⌊2lr⌋,我们只需要求出所有经过mid的区间内能够成为众数的所有数,不横跨mid位置的子区间总会在一个二分统计中计算
有这样一个性质如果x是区间[l,r]的绝对众数对于lkr,x一定是区间[l,k]或区间(k,r]的众数 利用这个性质我们可以令kmid。
我们只需要求出区间[x,mid] (lxmid)和区间[mid,y] (midyr)的众数就可以得知所有横跨mid 的子区间的众数。这样就可以O(n)从mid出发往左右两边扫求出所有能成为众数的数。
找出来的区间众数个数不会大于log(区间长度)
设当然枚举到的众数为nownum问题就变成有多少横跨mid的子区间中包含一半以上的nownum
这里用到一个高级的转化我们将区间中不是nownum的数变成-1是nownum的变成1这样问题就变成有多少横跨mid的子区间的和大于0 因为子区间横跨mid我们设左端点为x(x一定在[l,mid]中)右端点为y(y一定在[mid1,r]中) 我们求一个前缀和sum如果子区间是符合要求的那一定满足sum[y]-sum[x-1]0,移项后sum[y]sum[x-1]也就是对于每一个sum[y]有多少个sum[x-1]是符合要求的。我们可以开一个桶把所有sum[x-1]存进去然后桶求个前缀和这样就可以O(1)直到有多少个sum[x-1]是小于sum[y]的了 sum[x-1]的前缀和有可能是负数所以加一个偏移量n 递归树中每一层区间长度加起来是n可能的众数个数有log n个每一层的复杂度是O(nlogn).总共有log n层总复杂度是O(nlog2n)O(nlog^2n)O(nlog2n)
代码
// Problem: P4062 [Code#1]Yazid 的新生舞会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4062
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// Data:2021-08-11 14:54:52
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
template typename T inline void read(T x)
{T f 1;x 0;char ch getchar();while (0 isdigit(ch)) {if (ch -)f -1;ch getchar();}while (0 ! isdigit(ch))x (x 1) (x 3) ch - 0, ch getchar();x* f;
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 5e5;
int a[maxn];
ll ans;
int n, m;
int num[maxn], t, tot[maxn];
int isnum[maxn];
int sum[maxn * 2];
void solve(int l, int r)
{if (l r) {ans;return;}int mid (l r) 1;solve(l, mid);solve(mid 1, r);t 0;for (int i mid; i l; i--) {tot[a[i]]; //记录出现次数//如果出现次数大于区间长度的一半并且还没有加入过就加入数组if (tot[a[i]] (mid - i 1) / 2) {if (!isnum[a[i]]) {isnum[a[i]] 1;num[t] a[i];}}}for (int i mid; i l; i--)tot[a[i]] 0;for (int i mid; i r; i) {tot[a[i]];if (tot[a[i]] (i - mid) / 2) {if (!isnum[a[i]]) {isnum[a[i]] 1;num[t] a[i];}}}for (int i l; i r; i)tot[a[i]] 0, isnum[a[i]] 0;int s, nownum;for (int k 1; k t; k) {s 0;nownum num[k]; //枚举现在所有的众数sum[s n];for (int i l; i mid; i) {s (a[i] nownum ? 1 : -1);sum[s n];}s (a[mid] nownum ? 1 : -1);int len r - l 1;for (int i -len; i len; i) {sum[i n] sum[i n - 1];}for (int i mid 1; i r; i) {s (a[i] nownum ? 1 : -1);ans sum[s n - 1];}for (int i -len; i len; i) {sum[i n] 0;}}
}
int main()
{//rd_test();cin n m;for (int i 1; i n; i)cin a[i];solve(1, n);printf(%lld\n, ans);//Time_test();
}
