广西网络公司网站建设,深圳网站建设加盟,大学生做的广告短视频网站,最有效的app推广方式有哪些链接 传送门 分析 这道题想法其实很简单#xff0c;样例的计算方法一定要看懂。以样例1为例#xff0c;根据他的操作方法可以得到两个新的数组#xff0c;和一个原来的数组#xff0c;总共三个数组。 1 2 3 4 2 3 4 5 3 他们两两配对去重#xff0c;求出总的value。由于每…链接 传送门 分析 这道题想法其实很简单样例的计算方法一定要看懂。以样例1为例根据他的操作方法可以得到两个新的数组和一个原来的数组总共三个数组。 1 2 3 4 2 3 4 5 3 他们两两配对去重求出总的value。由于每个数组内的各个数各不相同也就是对于某个数字在一个数组内最多出现一次只需要统计一下这个数出现的次数就可以知道这个数在多少个数组内假设我们已经统计到了这个数的出现次数记作m数组总数记作n那么在所有的配对中这个数字的贡献是多少 包含这个数字的配对有两种一种是两个都是这个数一种是只有一个这个数例如4的贡献一种是4-4, 另一种是4-1,4-1。其他的配对不含4没有4的贡献。 取一个数的贡献是这个数个数乘以其他数的个数即m(n−m)取一个数的贡献是这个数个数乘以其他数的个数即m(n-m)取一个数的贡献是这个数个数乘以其他数的个数即m(n−m) 取两个相同的个数的数是Cm2取两个相同的个数的数是C^2_m取两个相同的个数的数是Cm2 故总贡献是Cm2m(n−m)故总贡献是C^2_mm(n-m)故总贡献是Cm2m(n−m) 如何着手统计。 我们发现每次更新都会另起一段这些出现的次数都是一段一段的所以我们开一个数组记录上一次更新的位置每次另一起一段的时候更新位置并把旧的一段统计如数组即可。注意最后残余的要清理干净。 实现
#include bits/stdc.h
#define ll long long
#define ls (u 1)
#define rs (u 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pairint, int PII;
const int N 4e5 5;
int cnt[N], st[N], a[N];
void solve() {int n, m;cin n m;for (int i 1; i n m; i) cnt[i] 0, st[i] 0;for (int i 1; i n; i) {int c;cin c;a[i] c;}for (int i 1; i m; i) {int p, v;cin p v;if (v ! a[p]) cnt[a[p]] i - st[p], st[p] i;//一定要不等于a[p] v;}for (int i 1; i n; i) {//残余部分cnt[a[i]] m - st[i] 1;//坐标相减要加1}ll ans 0;for (int i 1; i n m; i) {ans 1ll * cnt[i] * (m 1 - cnt[i]);ans 1ll * cnt[i] * (cnt[i] - 1) / 2;}cout ans \n;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T 1;cin T;while (T--) solve();return 0;
}
