【树状数组】第十八届同济大学程序设计竞赛暨高校网络友谊赛 E、不平衡的字符串
2021-05-25 15:38:00 # ACM

– 原题解

题链

– 对于化简后的式子的理解

$p[i]$ 是下标 $i$ 之前有多少个与当前询问字母相同的字母；

将 $ai-bp[i]$ 记为式子① ，将 $ci-dp[i]$ 记为式子②；

为这两个式子构建两颗权值树状数组一二；

对于每一个新加入的 $p[i]$，用式子②计算权值$val2$插入到第二颗树状数组中，先查找第二颗树状数组中查找 $<= val2$ 的值有多少，即为满足条件②的以 $i$ 为结尾的子段个数；

对于每一个新加入的 $p[i]$，用式子①计算权值$val1$插入到第一颗树状数组中，再查找第一颗树状数组中查找 $<= val1$ 的值有多少，即为不满足条件①的以 $i$ 为结尾的子段个数；

因为满足条件②的一定包含（满足或不满足）条件①的个数，所以两者相减就是 满足①②的 以 $i$ 为结尾的字段数量；

–代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 1000000007
#define MAXN 1e18
#define MS 50009
 
LL n,m;
char s[MS]; 
LL qz[MS];
LL ab[MS];
LL cd[MS];
LL tp[MS],tot;
LL p[3][MS];

LL lowbit(LL x){
	return x&(-x);
}

void add(LL rt,LL pos,LL val){
	for(;pos<=n;pos+=lowbit(pos)){
		p[rt][pos] += val;
	}
}

LL query(LL rt,LL pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)){
		ans += p[rt][pos];
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	cin >> s+1;
	cin >> m;
	LL ans = 0;
	while(m--){
		char vs;
		LL a,b,c,d;
		cin >> vs >> a >> b >> c >> d;
		for(int i=1;i<=n;i++){
			qz[i] = qz[i-1] + (s[i] == vs);
		}
		//-- a*i - b*qz[i] 离散化 
		for(int i=0;i<=n;i++){
			ab[i] = a*i - b*qz[i];
			tp[i] = ab[i];
		}
		sort(tp,tp+n+1);
		tot = 0;
		for(int i=1;i<=n;i++){
			if(tp[i] != tp[i-1]) tp[++tot] = tp[i];
		}
		for(int i=0;i<=n;i++){
			ab[i] = lower_bound(tp,tp+tot+1,ab[i]) - tp + 1;
		}
		//-- c*i - d*qz[i] 离散化
		for(int i=0;i<=n;i++){
			cd[i] = c*i - d*qz[i];
			tp[i] = cd[i];
		}
		sort(tp,tp+n+1);
		tot = 0;
		for(int i=1;i<=n;i++){
			if(tp[i] != tp[i-1]) tp[++tot] = tp[i];
		}
		for(int i=0;i<=n;i++){
			cd[i] = lower_bound(tp,tp+tot+1,cd[i]) - tp + 1;
		}
		//--
		for(int i=0;i<=n;i++) p[1][i] = p[2][i] = 0;
		for(int i=0;i<=n;i++){
			add(1,ab[i],1);
			add(2,cd[i],1);
			LL t2 = query(2,cd[i]);
			LL t1 = query(1,ab[i]);
			ans += t2-t1;
		}
	}
	cout << ans << "\n";
	

	return 0;
}

Prev
2021-05-25 15:38:00 # ACM
Next