深圳响应式网站建设,域名服务器上存放着,网站制作在哪能看,wordpress 主题 翻译P4062 [Code#1]Yazid 的新生舞会#xff08;线段树做法#xff09;
题意#xff1a;
给你一个序列a[1…n]#xff0c;求存在绝对众数的子区间个数。
绝对众数指#xff1a;区间中出现次数最多的那个数#xff0c;出现次数严格大于区间长度的一半。
题解#xff1a…P4062 [Code#1]Yazid 的新生舞会线段树做法
题意
给你一个序列a[1…n]求存在绝对众数的子区间个数。
绝对众数指区间中出现次数最多的那个数出现次数严格大于区间长度的一半。
题解
这两个博客将的很长清楚明白(尤其是第一个)我在反复看了n遍后终于明白。题目细节很多我再怎么写也没这两个详细干脆直接放上链接。 Zechariah的博客 OMG_wc 的博客 关于题解中提到的三阶前缀和: 三阶前缀和公式转换 图来自lx_tyin博客
代码
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int INF 0x3f3f3f3f;
const LL mod 1e9 7;
const int N 500005;
// 修改差分 来维护前缀和的前缀和
// c1 为差分d c2为d*i c3 为d*i*i
LL c1[N * 2], c2[N * 2], c3[N * 2];
LL sum(int x) {LL res 0;for (int i x; i 0; i - i -i) {res c1[i] * (x 2) * (x 1) - c2[i] * (2 * x 3) c3[i];}return res / 2;
}
void add(int x, LL d, int n) {for (int i x; i n; i i -i) {c1[i] d;c2[i] d * x;c3[i] d * x * x;}
}
int a[N];
vectorint b[N];
int main() {int n;scanf(%d%*d, n);for (int i 1; i n; i) {scanf(%d, a[i]);b[a[i]].push_back(i);}const int wc n 1; // 偏移量把[-n,n] 平移到 [1,2n1]LL ans 0;for (int i 0; i n; i) {b[i].push_back(n 1);int last 0;for (int j 0; j b[i].size(); j) {//j表示i的个数int y 2 * j - last wcint x 2 * j - (b[i][j] - 1) wc;// 查询 sum([1,t-1] 的权值和), 其中t在[x,y]范围内ans sum(y - 1) - (x 3 ? sum(x - 2) : 0);// [x,y] 这些数的权值1add(x, 1, 2 * n 1);add(y 1, -1, 2 * n 1);last b[i][j];}//撤销操作last 0;for (int j 0; j b[i].size(); j) {int y 2 * j - last wc;int x 2 * j - (b[i][j] - 1) wc;add(x, -1, 2 * n 1);add(y 1, 1, 2 * n 1);last b[i][j];}}printf(%lld\n, ans);return 0;
}
