codeforces 558E A Simple Task 线段树

题目链接

题意较为简单。

思路：

因为只有26个字母，所以用26棵线段树维护就好了，比较容易。

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
#include <algorithm>
#include <stack>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
typedef long long ll;
typedef pair<ll, ll> pii;
const int N = 1e5 + 100;
#define lson (id<<1)
#define rson (id<<1|1)
#define L(x) tree[x].l
#define R(x) tree[x].r
#define Hav(x) tree[x].hav
#define Siz(x) tree[x].siz
#define Lazy(x) tree[x].lazy
struct Tree {
struct Node {
int l, r, siz;//siz表示区间长度
int hav;//hav表示这个区间的和
int lazy;//lazy为2表示清空区间 lazy为1表示把区间都变为1
}tree[N << 2];
void build(int l, int r, int id) {
L(id) = l; R(id) = r; Siz(id) = r - l + 1;
Hav(id) = Lazy(id) = 0;
if (l == r)return;
int mid = (l + r) >> 1;
build(l, mid, lson); build(mid + 1, r, rson);
}
void Down(int id) {
if (Lazy(id) == 1) {
Lazy(id) = 0;
Hav(lson) = Siz(lson); Hav(rson) = Siz(rson);
Lazy(lson) = Lazy(rson) = 1;
}
else if (Lazy(id) == 2) {
Lazy(id) = 0;
Hav(lson) = Hav(rson) = 0;
Lazy(lson) = Lazy(rson) = 2;
}
}
void Up(int id) {
Hav(id) = Hav(lson) + Hav(rson);
}
void updata(int l, int r, int val, int id) {
if (l == L(id) && R(id) == r) {
if (val == 1)
Hav(id) = Siz(id);
else Hav(id) = 0;
Lazy(id) = val;
return;
}
Down(id);
int mid = (L(id) + R(id)) >> 1;
if (r <= mid)updata(l, r, val, lson);
else if (mid < l)updata(l, r, val, rson);
else {
updata(l, mid, val, lson);
updata(mid + 1, r, val, rson);
}
Up(id);
}
int query(int l, int r, int id) {
if (l == L(id) && R(id) == r) {
return Hav(id);
}
Down(id);
int mid = (L(id) + R(id)) >> 1, ans = 0;
if (r <= mid)ans = query(l, r, lson);
else if (mid < l)ans = query(l, r, rson);
else {
ans = query(l, mid, lson) + query(mid + 1, r, rson);
}
Up(id);
return ans;
}
};
Tree alph[26];
int n, q;
char s[N];
int sum[26];
int main() {
rd(n); rd(q);
for (int i = 0; i < 26; i++)alph[i].build(1, n, 1);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
alph[s[i] - 'a'].updata(i, i, 1, 1);
}
while (q--) {
int l, r, in;
rd(l); rd(r); rd(in);
memset(sum, 0, sizeof sum);
for (int i = 0; i < 26; i++)
{
sum[i] += alph[i].query(l, r, 1);
alph[i].updata(l, r, 2, 1);
}
int tim = 26, i;
if (in)i = 0; else i = 25, in = -1;
for (;tim--; i += in) {
if (sum[i] == 0)continue;
alph[i].updata(l, l + sum[i] - 1, 1, 1);
l += sum[i];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 26; j++)
if (alph[j].query(i, i, 1))
{
putchar(j + 'a'); break;
}
}
return 0;
}

最后

以上就是暴躁火龙果为你收集整理的codeforces 558E A Simple Task 线段树的全部内容，希望文章能够帮你解决codeforces 558E A Simple Task 线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。