登錄—專業IT筆試面試備考平臺_牛客網

using i64 = long long;
using ll = long long;
constexpr ll M = 1e9 + 7;
template<class Info>
struct SegmentTree {int n;std::vector<Info> info;SegmentTree() : n(0) {}SegmentTree(int n_, Info v_ = Info()) {init(n_, v_);}template<class T>SegmentTree(std::vector<T> init_) {init(init_);}void init(int n_, Info v_ = Info()) {init(std::vector<Info>(n_, v_));}template<class T>void init(std::vector<T> init_) {n = init_.size();info.assign(4 << (int)std::log2(n), Info());std::function<void(int, int, int)> build = [&](int p, int l, int r) {if (r - l == 1) {info[p] = init_[l];return;}int m = (l + r) / 2;build(2 * p, l, m);build(2 * p + 1, m, r);pull(p);};build(1, 0, n);}void pull(int p) {info[p] = info[2 * p] + info[2 * p + 1];}void modify(int p, int l, int r, int x, const Info& v) {if (r - l == 1) {info[p] = v;return;}int m = (l + r) / 2;if (x < m) {modify(2 * p, l, m, x, v);}else {modify(2 * p + 1, m, r, x, v);}pull(p);}void modify(int p, const Info& v) {modify(1, 0, n, p, v);}Info rangeQuery(int p, int l, int r, int x, int y) {if (l >= y || r <= x) {return Info();}if (l >= x && r <= y) {return info[p];}int m = (l + r) / 2;return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);}Info rangeQuery(int l, int r) {return rangeQuery(1, 0, n, l, r);}template<class F>int findFirst(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findFirst(2 * p, l, m, x, y, pred);if (res == -1) {res = findFirst(2 * p + 1, m, r, x, y, pred);}return res;}template<class F>int findFirst(int l, int r, F pred) {return findFirst(1, 0, n, l, r, pred);}template<class F>int findLast(int p, int l, int r, int x, int y, F pred) {if (l >= y || r <= x || !pred(info[p])) {return -1;}if (r - l == 1) {return l;}int m = (l + r) / 2;int res = findLast(2 * p + 1, m, r, x, y, pred);if (res == -1) {res = findLast(2 * p, l, m, x, y, pred);}return res;}template<class F>int findLast(int l, int r, F pred) {return findLast(1, 0, n, l, r, pred);}
};struct Info {ll a;//表示黃色磚塊,當前ll b;ll c = 1;ll d;
};Info operator+(const Info& b, const Info& a) {//b.a + a.a * b.c//b.b + a.a * b.d + a.b //a.c * b.c//a.c * b.d + a.d return { (b.a + ((a.a%M) * (b.c%M))%M)%M, (b.b + ((a.a%M) * (b.d%M)) + a.b)%M, ((a.c%M) * (b.c%M))%M, (((a.c%M) * (b.d%M)%M) + a.d)%M };
}Info Y{ 0, 0, 1, 1 };
Info B{ 1, 0, 0, 1 };//箭頭指向下一個位置
Info R{ 0, 0, 2, 1 };//總數量乘以2在加上一個紅色磚塊int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, q;std::cin >> n >> q;std::string s;std::cin >> s;//最底層的n個區間,比如[0,1)表示第一個區間,代表第一塊磚SegmentTree<Info> seg(n);for (int i = 0; i < n; i++) {seg.modify(i, (s[i] == 'Y') ? Y : ((s[i] == 'B') ? B : R));/*for (int j = 0; j < n; j++) {Info t = seg.rangeQuery(j, j + 1);std::cout <<j<<":"<< t.a << ' ' << t.b << ' ' << t.c << ' ' << t.d << '\n';}*/}while (q--) {int o;std::cin >> o;if (o == 1) {int p;char c;std::cin >> p >> c;p--;seg.modify(p, (c == 'Y') ? Y : ((c == 'B') ? B : R));}else {int l, r;std::cin >> l >> r;l--;Info res = seg.rangeQuery(l, r);//b和d的和為總數ll ans = (res.b + res.d) % M;std::cout << ans << "\n";}}return 0;
}

第一點:std::vector<Info> info;存的是按區間字符操作后的效果,有點難理解,舉個例子,如果你查詢[0,1)這個區間相當于查詢按第一個字符進行游戲后的效果,如果第一個字符是Y,那么查詢的結果就是Info Y{ 0, 0, 1, 1 };至于Info為什么要這么定義我們來看看下面的內容.

其中最難理解的就是下面這一部分

struct Info {ll a;//最左邊的柱子的倍數ll b;//所有累計的方塊ll c = 1;//現有倍數ll d;//現有這一列的方塊
};Info operator+(const Info& b, const Info& a) {//b.a + a.a * b.c//b.b + a.a * b.d + a.b//a.c * b.c//a.c * b.d + a.d return { (b.a + ((a.a%M) * (b.c%M))%M)%M, (b.b + ((a.a%M) * (b.d%M)) + a.b)%M, ((a.c%M) * (b.c%M))%M, (((a.c%M) * (b.d%M)%M) + a.d)%M };
}Info Y{ 0, 0, 1, 1 };
Info B{ 1, 0, 0, 1 };//箭頭指向下一個位置
Info R{ 0, 0, 2, 1 };//總數量乘以2在加上一個紅色磚塊

首先a,b,c,d的意思我都標出來了,為什么要這么定義呢,我們這樣想,當中間有很多個操作B出現的時候,那么這個區間是不是有很多個柱子,這樣不清楚,讓我來畫個圖

如果產生了多個柱子是不是說明有操作B,第一個柱子不管是YRRY或是什么其它的操作它都不可能產生第二個柱子.假如我們要合并兩個區間,

每根柱子表示的無非就是YR的組合,可能是YYYY,RRRR又或者是YRRY等等,不存在B所以最后一根和第一根合并的序列一定是一根,那么效果是怎樣的呢,?顯然最后一根總方塊數我們可以設為k,那么合并后可以表示為((k+a1)*2+a2)*2+a3,原先第一根的方塊數為(a1*2+a2)*2+a3,兩者的差值不就是把k提到外面來嗎及(a1*2+a2)*2+a3+4*k(注意,我只是舉了一個只有兩個R情況下的例子,*2的數量要根據R的數量來定),那么+重載為什么這樣運算也很明顯了.

對于第一個算式b.a + a.a * b.c,再使用B之前,第一根的方塊數量和R的數量是不確定的,如果第一個區間有B,那么第一個區間的c變量是0,也就是說兩個區間合并后的第一根倍數就是b.a,如果第一個區間沒有B,說明第二個區間的第一根和第一個區間合并后會變成一根,即b.c不為0而b.a為0,合并后的第一根是a.a乘以b.c.

感覺解釋的不是很清楚(*/ω＼*),換個解釋方法,Info Y{ 0, 0, 1, 1 };第一個1表示當前倍數為自己身的一倍,也就是不翻倍,第二個1表示添加到目前這根柱子里添加一個方塊,Info R{ 0, 0, 2, 1 };翻倍后添加,Info B{ 1, 0, 0, 1 };這涉及到好幾個運算,首先看最簡單的a.c*b.c表示第一根柱子已經固定了,根據之前講的最后一根和第一根合并的運算,我們要把當前倍數轉移到a變量里,及a.a * b.c,因為b是左邊的區間,所以按照這個運算,如果它在之前有過B字符,那么它也不為0,所以要加上b.a.

列舉了兩個,其它的是一樣的,就像是自動機一樣,涉及到有B和沒B的情況,比較難解釋,當涉及B的時候某些變量會自動變為0從而做出變換.

b.a(有B/沒B) + a.a(有B/沒B) * b.c(沒B/有B)
b.b(有B/沒B) + a.a(有B/沒B) * b.d?+ a.b(有B/沒B)? ? ? ? ?有Ba.a會把b.d添加到非當前柱子
a.c * b.c(沒B/有B)
a.c(沒B/有B) * b.d?+ a.d????????沒有B的時候a.c會把b.d添加到當前柱子?

大概就是這樣,盡力了,很難解釋.