Znzryb's Blog
0%

ABC-390-F - Double Sum 3

Posted on Edited on

思路讲解

ABC- 371 - E- I Hate Sigma Problems

【AtCoder 初学者竞赛 390比赛讲解】 【精准空降到 1:05:10】 https://www.bilibili.com/video/BV1NNfkY2Esv/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37&t=3910

正过来求贡献的想法

image

这个左端点选择数和右端点选择数怎么样快速求出？

还是一样的，用类似于邻接表的数据结构二分快速求出

AC代码

AC（这个代码稍微有点啰嗦）

https://atcoder.jp/contests/abc390/submissions/62410948

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
// Problem: F - Double Sum 3
// Contest: AtCoder - AtCoder Beginner Contest 390
// URL: https://atcoder.jp/contests/abc390/tasks/abc390_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,A[MAXN];
// ull diffSum[MAXN];// arithmetic sequence
// ll diff[MAXN],origin[MAXN]; 
vector<ll> g[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	FOR(i, 1, N){
		cin>>A[i];
		g[A[i]].pb(i);
	}
	ull ans=0;
	FOR(i,1,N){	// 二分算贡献
		ll lres=1,rres=N;
		FOR(j,A[i]-1,A[i]-1){
			if(g[j].empty()) continue;
			auto it=upper_bound(all(g[j]),i);
			if(it==g[j].end()) continue;
			rres=min(*it-1,rres);
		}
		
		FOR(j,A[i]-1,A[i]){
			if(j==A[i]){
				auto it=lower_bound(all(g[j]),i);
				if(it==g[j].begin()) continue;	// 找不到就说明无限制
				it--;
				lres=max(lres,*it+1);
			}else{
				if(g[j].empty()) continue;
				auto it=lower_bound(all(g[j]),i);
				if(it==g[j].begin()) continue;	// 找不到就说明无限制
				it--;
				lres=max(lres,*it+1);
			}
			
		}
		cerr<<i<<' '<<lres<<' '<<rres<<'\n';
		ans+=(i-lres+1)*(rres-i+1);
	}
	
	cout<<ans<<'\n';
	
	return 0;
}
/*
AC
https://atcoder.jp/contests/abc390/submissions/62410948
*/

心路历程（WA，TLE，MLE……）

思路排除，不太可能是线段树

ABC-391-E - Hierarchical Majority Vote（三叉线段树） 这种合并比较容易的更适合用线段树解决

image

反过来贡献的想法（有缺陷）

image

1，3，6，10的由来（1，2，3，4代表所有以他们为结尾的区间）

image

像这种问题，考虑区间合并比较麻烦，不如化整为零，计算个体的贡献，对所有位于它贡献位置后面的全部减id（之所以是减下标id是因为所有它后面的位置所代表的区间中有id个含有这个位置的区间）

image

好，现在知道了知道了贡献我们怎么求解这个问题。那么问题来了，我们怎么做到O（n）的求贡献那？

image

我们发现题目贴心的有了这么一个限制条件，我们可以快捷的用二分求出贡献为止，利用类似于邻接表的数据结构。

程序过不了样例2

image

原因是在于以下（3，1已经被考虑没用了，但是4在有3的情况下也没用这点没考虑）

image

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
// Problem: F - Double Sum 3
// Contest: AtCoder - AtCoder Beginner Contest 390
// URL: https://atcoder.jp/contests/abc390/tasks/abc390_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
const ll MAXN=static_cast<ll>(3e5)+10,INF=static_cast<ll>(5e18)+3;

ll N,A[MAXN];
ull diffSum[MAXN];// arithmetic sequence
ll diff[MAXN],origin[MAXN]; 
vector<ll> g[MAXN];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>N;
	FOR(i, 1, N){
		cin>>A[i];
		diffSum[i]=diffSum[i-1]+i;	// 形成的是等差数列1，2，3，。。。的前缀和
		g[A[i]].pb(i);
	}
	FOR(i,1,N){	// 二分算贡献
		ll res=MAXN,reduce=0;
		FOR(j,A[i]-1,A[i]+1){
			if(g[j].empty()) continue;
			auto it=upper_bound(all(g[j]),i);
			if(it==g[j].end()) continue;
			res=min(*it,res);
		}
		if(res==MAXN) continue;
		diff[res]-=i+reduce;
	}
	FOR(i,1,N){
		origin[i]=origin[i-1]+diff[i];
	}
	ull ans=0;
	FOR(i,1,N){
		ans+=diffSum[i]+origin[i];
	}
	cout<<ans<<'\n';
	
	FOR(i,1,N){
		cerr<<origin[i]<<'\n';
	}
	FOR(i,1,N){
		cerr<<diff[i]<<' ';
	}
	cerr<<'\n';
	return 0;
}
/*

*/