School of magic
Title Description:
Yako likes to collect visible characters without spaces (ASCII code is 33 ~ 126). In her eyes, the value of a character is its ASCII code size, such as the value of 'a' is 97.
So far, she has collected n visible characters excluding spaces, and the ith character is Si. But she wanted to maximize the value and of the n characters she collected, so she asked Diana for help.
Diana has m magic, and the i magic can replace a character in the [li,ri] interval with ci. Because of Diana's excellent magic, every kind of magic can be used unlimited times.
What is the maximum value of the n characters collected by Yake after Diana has used magic several times?
Idea 1: difference + greed
For each character, we update the answers of all points it can affect, and finally calculate the sum of the answers of all points
The method is to add the difference prefix and, make a difference group d, + + d[l],--d[r + 1], and then add the prefix and. If sum [i] > 0, it means that this point will be affected by this character. Just update the answer of this point
Complexity is O(94 * n)
It can solve the easy version, but not for the hard version
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m;
int l, r;
char p;
vector<pii>tr[200];
int ans[MAX];
int d[200050];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> p;
ans[i] = (int)p;
}
for(int i = 1; i <= m; ++i){
cin >> l >> r >> p;
tr[(int)p].push_back(m_p(l, r));
}
for(int i = 33; i <= 126; ++i){
mem(d, 0);
for(auto [l, r] : tr[i]){
++d[l];--d[r + 1];
}
for(int j = 1; j <= n; ++j){
d[j] += d[j - 1];
if(d[j])ans[j] = max(ans[j], i);
}
}
ll sum = 0;
for(int i = 1; i <= n; ++i)sum += ans[i];
cout << sum << endl;
}
int main(){
io;
work();
return 0;
}
Idea 2: greedy + segment tree interval coverage
We can divide each character of the string into an interval of [i, i], put it together with the input m intervals, sort them in the order of value from small to large, and then start interval coverage. It is not difficult to find that such greed is obviously correct
Complexity O((n + m)log(n))
You can only pass the easy version, but not the hard version
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
//Do not change the scope, see the ancestors!!!
#define MAX 500000 + 50
int n, m, k, op;
struct ran{
int l, r, val;
bool operator <(const ran &x)const{
return val < x.val;
}
}ar[MAX];
ll sum[MAX];
int la[MAX];
inline void pushup(int p){
sum[p] = sum[ls] + sum[rs];
}
inline void built(int p, int l, int r){
if(l == r){
sum[p] = la[p] = 0;
return;
}
int mid = (l + r) / 2;
built(ls, l, mid);
built(rs, mid + 1, r);
pushup(p);
}
inline void cal_lazy(int p, int len, int x){
la[p] = x;
sum[p] = 1ll * len * x;
}
inline void pushdown(int p, int len){
if(la[p]){
cal_lazy(ls, len - len / 2, la[p]);
cal_lazy(rs, len / 2, la[p]);
la[p] = 0;
}
}
inline void update(int p, int l, int r, int s, int t, int x){
if(l >= s && t >= r){
cal_lazy(p, r - l + 1, x);
return;
}
pushdown(p, r - l + 1);
int mid = (l + r) / 2;
if(mid >= s)update(ls, l, mid, s, t, x);
if(mid < t)update(rs, mid + 1, r, s, t, x);
pushup(p);
}
inline ll getsum(int p, int l, int r, int s, int t){
if(l >= s && t >= r){
return sum[p];
}
pushdown(p, r - l + 1);
ll sum = 0;
int mid = (l + r) / 2;
if(mid >= s)sum += getsum(ls, l, mid, s, t);
if(mid < t)sum += getsum(rs, mid + 1, r, s, t);
return sum;
}
void work(){
cin >> n >> m;
char p;
for(int i = 1; i <= n; ++i){
cin >> p;
ar[i].l = ar[i].r = i;
ar[i].val = (int)p;
}
for(int i = 1; i <= m; ++i){
cin >> ar[i + n].l >> ar[i + n].r;
cin >> p;
ar[i + n].val = (int)p;
}
sort(ar + 1, ar + 1 + m + n);
built(1, 1, n);
for(int i = 1; i <= n + m; ++i){
update(1, 1, n, ar[i].l, ar[i].r, ar[i].val);
}
cout << getsum(1, 1, n, 1, n) << endl;
}
int main(){
work();
return 0;
}
Idea 3: greed + concurrent search
Regardless of the string, directly arrange the m intervals in the order of value from large to small. For the intervals covered by high-value characters, there is no need to traverse the low-value characters, so we can use parallel search to solve it
Finally, use the maximum value of each bit and the corresponding position ratio size of the string to take the maximum and sum
The complexity is: O(max(n, mlogm))
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m;
char p;
char c[MAX];
int fa[MAX];
inline int getfa(int x){
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
struct ran{
int l, r, p;
}tr[MAX];
bool cmp(ran a, ran b){
return a.p > b.p;
}
int ans[MAX];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i)cin >> c[i];
for(int i = 1; i <= m; ++i){
cin >> tr[i].l >> tr[i].r >> p;
tr[i].p = (int)(p);
}
for(int i = 1; i <= n + 1; ++i)fa[i] = i;
sort(tr + 1, tr + 1 + m, cmp);
for(int i = 1; i <= m; ++i){
auto [l, r, z] = tr[i];
l = getfa(l);
while (l <= r) {
ans[l] = max(ans[l], z);
fa[l] = l + 1;
l = getfa(l + 1);
}
}
ll cnt = 0;
for(int i = 1; i <= n; ++i){
cnt += max(ans[i], (int)c[i]);
}
cout << cnt << endl;
}
int main(){
io;
work();
return 0;
}
Idea 4: Kodori tree + "metaphysical optimization"
It is similar to the idea of method 2, but method 2 only uses segment tree to cover the interval, which is a waste of time, and the Kodori tree can deal with the interval coverage problem well
However, it should be noted that each point of the string should not be processed together like the line segment tree of method 2. If they are processed together, it may lead to the initial size of cordolly being n and T. the solution is to facilitate each number of each interval of the set of the cordolly tree and the value of the corresponding position of the string to take a maximum value when making the final statistics of the answer, Just make peace
Complexity is O (passable)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define it set<ran>::iterator
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 20000000 + 50
int n, m;
int l, r;
vector<pii>s[130];
char ss[MAX];
struct ran{
int l, r;
mutable int val;
ran(int L, int R = -1, int Val = 0){
l = L;r = R;val = Val;
};
bool operator <(const ran &x)const{
return l < x.l;
}
};
set<ran>tr;
it split(int pos){
if(pos > n)return tr.end();
it itt = tr.lower_bound(pos);
if(itt != tr.end() && itt->l == pos)return itt;
--itt;
int l = itt->l, r = itt->r, v = itt->val;
tr.erase(itt);
tr.insert(ran(l, pos - 1, v));
return tr.insert(ran(pos, r, v)).first;
}
void emerge(int l, int r, int v){
it itr = split(r + 1), itl = split(l);
tr.erase(itl, itr);
tr.insert(ran(l, r, v));
}
ll getans(){
ll ans = 0;
for(auto [l, r, v] : tr){
for(int i = l; i <= r; ++i){
ans += max(v, (int)ss[i]);
}
}
return ans;
}
void work(){
scanf("%d%d", &n, &m);
scanf("%s", ss + 1);
tr.insert(ran(1, n, 0));
for(int i = 1; i <= m; ++i){
char p[3];
scanf("%d%d", &l, &r);
scanf("%s", p);
s[(int)p[0]].push_back(m_p(l, r));
}
for(int i = 33; i <= 126; ++i){
for(auto [l, r] : s[i]){
emerge(l, r, i);
}
}
printf("%lld\n", getans());
}
int main(){
work();
return 0;
}