[数据结构与算法]牛客练习赛91 C（贪心+并查集 D（前缀和+树状数组

魔法学院(hard version)
思路：
题解
注意是一次操作是替换区间内某一个字符
经典的并查集应用
从高价值字符枚举到低价值字符，那么对于高价值字符覆盖过的区间，低价值字符就没有必要去遍历了。遍历时，用并查集对之前覆盖过的区间进行跳跃即可，因此每个字符至多被遍历一次
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int s[maxn], f[maxn];
struct node{
	int l, r, c;
	bool operator<(const node &B){
		return c > B.c;
	}
}d[maxn];
int find(int x){
	return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y){
	x = find(x); y = find(y);
	if(x != y){
		f[x] = y;
	}
}
void work()
{
	cin >> n >> m;
	for(int i = 1; i <= n + 1; ++i) f[i] = i;// 注意开到n+1
	for(int i = 1; i <= n; ++i){
		char x;cin >> x;s[i] = (int)x;
	}
	for(int i = 1; i <= m; ++i){
		char c;
		cin >> d[i].l >> d[i].r >> c;
		d[i].c = int(c);
	}
	sort(d + 1, d + 1 + m);
	for(int i = 1; i <= m; ++i){
		int now = find(d[i].l);
		if(now > d[i].r) continue;
		while((now = find(now)) <= d[i].r){
			merge(now, d[i].r + 1);
			s[now] = max(s[now], d[i].c);
			++now;
		}	
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++i) ans += s[i];
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

监狱逃亡
题意：
给定一个 $3\times n$ 的矩阵，起点为 $(1,1)$，终点为 $(3,n)$，每个位置有一个价值 $a_{ij}$，每次可以向右或者向下移动一格，求走到终点路径权值和 $>=0$ 的方案数，答案对 $10^9+7$ 取模
思路：
矩阵只有 $3$ 行，从第一行走到第三行，必然会有两次移动向下，设在第 $i$ 列第一次向下，第 $j$ 列第二次向下（$i<=j$）
考虑维护三行的前缀和，终点价值即为 $sum1[i]+(sum2[j]?sum2[i?1]+(sum3[n]?sum3[j?1])$
满足不等式 $sum1[i]+(sum2[j]?sum2[i?1]+(sum3[n]?sum3[j?1])>=0$
分离 $i,j$
不等式变形为 $sum2[i?1]?sum1[i]?sum3[n]<=sum2[j]?sum3[j?1](i<=j)$
不等式变形这步最好写成上边的式子，如果变为 $sum3[j?1]?sum2[j]?sum3[n]<=sum1[i]?sum2[i?1](i<=j)$， 这样类似于逆序对，不方便求解
将不等式两边的值离散化，用树状数组即可求解
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e6 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int c[maxn];
void update(int i, int k){
	while(i <= n * 2) c[i] += k, i += i & (-i);
}
int qry(int i){
	int ans = 0;while(i) ans += c[i], i -= i & (-i);return ans;
}
ll sum[4][maxn];

void work()
{
	cin >> n;
	for(int i = 1; i <= 3; ++i)
		for(int j = 1; j <= n; ++j)
		{
			cin >> sum[i][j];sum[i][j] += sum[i][j-1];
		}
	vector <ll> v;
	for(int i = 1; i <= n; ++i){
		v.push_back(sum[2][i] - sum[3][i-1]);
		v.push_back(sum[2][i-1] - sum[1][i] - sum[3][n]);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	ll ans = 0;
	for(int i = 1; i <= n; ++i){
		int pos1 = lower_bound(all(v), sum[2][i-1] - sum[1][i] - sum[3][n]) - v.begin() + 1;
		update(pos1, 1);
		int pos2 = lower_bound(all(v), sum[2][i] - sum[3][i-1]) - v.begin() + 1;
		(ans += qry(pos2)) %= mod;
	}
	cout << ans;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}