递推化简+线段树区间维护,P6477 [NOI Online #2 提高组] 子序列问题

2024-02-04 04:04

本文主要是介绍递推化简+线段树区间维护,P6477 [NOI Online #2 提高组] 子序列问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、题目

1.1题目背景

2s 512M

1.2题目描述

给定一个长度为 n n n 的正整数序列 A 1 A_1 A1, A 2 A_2 A2, ⋯ \cdots , A n A_n An。定义一个函数 f ( l , r ) f(l,r) f(l,r) 表示:序列中下标在 [ l , r ] [l,r] [l,r] 范围内的子区间中,不同的整数个数。换句话说, f ( l , r ) f(l,r) f(l,r) 就是集合 { A l , A l + 1 , ⋯ , A r } \{A_l,A_{l+1},\cdots,A_r\} {Al,Al+1,,Ar} 的大小,这里的集合是不可重集,即集合中的元素互不相等。

现在,请你求出 ∑ l = 1 n ∑ r = l n ( f ( l , r ) ) 2 \sum_{l=1}^n\sum_{r=l}^n (f(l,r))^2 l=1nr=ln(f(l,r))2。由于答案可能很大,请输出答案对 1 0 9 + 7 10^9 +7 109+7 取模的结果。

1.3输入格式

第一行一个正整数 n n n,表示序列的长度。

第二行 n n n 个正整数,相邻两个正整数用空格隔开,表示序列 A 1 A_1 A1, A 2 A_2 A2, ⋯ \cdots , A n A_n An

1.4输出格式

仅一行一个非负整数,表示答案对 1 0 9 + 7 10^9+7 109+7 取模的结果。

1.5样例 #1

样例输入 #1

4
2 1 3 2

样例输出 #1

43

样例 #2

样例输入 #2

3
1 1 1

样例输出 #2

6

1.6提示

对于 10 % 10\% 10% 的数据,满足 1 ≤ n ≤ 10 1 \leq n \leq 10 1n10

对于 30 % 30\% 30% 的数据,满足 1 ≤ n ≤ 100 1 \leq n \leq 100 1n100

对于 50 % 50\% 50% 的数据,满足 1 ≤ n ≤ 1 0 3 1\leq n \leq 10^3 1n103

对于 70 % 70\% 70% 的数据,满足 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1n105

对于 100 % 100\% 100% 的数据,满足 1 ≤ n ≤ 1 0 6 1\leq n\leq 10^6 1n106,集合中每个数的范围是 [ 1 , 1 0 9 ] [1,10^9] [1,109]

1.7原题链接

https://www.luogu.com.cn/problem/P6477


二、解题报告

1、思路分析

1e6数据量,必须想出O(N)或者O(NlogN)的解法,不然肯定过不了

我们发现a[r]对于f(l , r)的影响为:即a[r]上一次出现位置为last[a[r]],那么f(i , r)都+1,i >= last[a[r]] + 1,其它f值都不变

这样我们似乎可以得出某种递推关系,我们令g® = Σf(l , r)^2

那么g® - g(r - 1) = Σf(l , r) ^ 2 - f(l , r - 1) ^ 2,其中last[a[r]] + 1 <= l <= r

进一步化简:g(r ) - g(r - 1) = Σf(l , r) * 2 + r - last[a[r]]

这样一来,我们就把平方和转化为线性和

我们只需要用线段树存储f(l , r),其中l >= 1,即可,然后每求一次g®都对[last[a[r]] + 1 , r]区间+1

每次求g®只需要知道g(r - 1)和线段树对应区间和,这一步是O(logn),枚举右端点是O(n),整体O(nlogn)

2、复杂度

时间复杂度:O(nlogn) 空间复杂度:O(n)

3、代码详解

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define lc p << 1
#define rc p << 1 | 1
#define int long long
const int N = 1e6 + 5, MOD = 1e9 + 7;
int a[N], b[N], last[N], d[N];
struct Node
{int l, r, s, add;
} tr[N << 2];void build(int p, int l, int r)
{tr[p] = {l, r, 0, 0};if (l == r)return;int mid = (l + r) >> 1;build(lc, l, mid), build(rc, mid + 1, r);
}void pushup(int p)
{tr[p].s = tr[lc].s + tr[rc].s;
}void pushdown(int p)
{if (tr[p].add){tr[lc].s += (tr[lc].r - tr[lc].l + 1) * tr[p].add, tr[rc].s += (tr[rc].r - tr[rc].l + 1) * tr[p].add;tr[lc].add += tr[p].add, tr[rc].add += tr[p].add;tr[p].add = 0;}
}void update(int p, int l, int r, int k)
{if (l <= tr[p].l && tr[p].r <= r){tr[p].s += (tr[p].r - tr[p].l + 1) * k;tr[p].add += k;return;}int mid = (tr[p].l + tr[p].r) >> 1;pushdown(p);if (l <= mid)update(lc, l, r, k);if (r > mid)update(rc, l, r, k);pushup(p);
}int query(int p, int l, int r)
{if (l <= tr[p].l && r >= tr[p].r)return tr[p].s;int mid = (tr[p].l + tr[p].r) >> 1, ret = 0;pushdown(p);if (l <= mid)ret += query(lc, l, r);if (r > mid)ret += query(rc, l, r);return ret;
}int read()
{int s = 0, w = 1;char ch = getchar();while (ch < '0' || ch > '9')w *= (ch == '-' ? -1 : 1), ch = getchar();while (ch >= '0' && ch <= '9')s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();return s * w;
}void write(int x)
{if (x < 0)putchar('-');if (x > 9)write(x / 10);putchar((x % 10) ^ 48);
}signed main()
{// freopen("in.txt", "r", stdin);int n = read();for (int i = 1; i <= n; i++)a[i] = read(), b[i] = a[i];sort(b + 1, b + n + 1);int m = unique(b + 1, b + n + 1) - b - 1;for (int i = 1, k; i <= n; i++){k = lower_bound(b + 1, b + m + 1, a[i]) - b;d[i] = last[k];last[k] = i;}int ans = 0;build(1, 1, n);for (int i = 1, cur = 0; i <= n; i++){cur += i - d[i] + (query(1, d[i] + 1, i) << 1);cur %= MOD;ans = (ans + cur) % MOD;update(1, d[i] + 1, i, 1);}write(ans);return 0;
}

这篇关于递推化简+线段树区间维护,P6477 [NOI Online #2 提高组] 子序列问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/676305

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

uva 568 Just the Facts(n!打表递推)

题意是求n!的末尾第一个不为0的数字。 不用大数,特别的处理。 代码: #include <stdio.h>const int maxn = 10000 + 1;int f[maxn];int main(){#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALf[0] = 1;for (int i = 1; i <=

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k