洛谷P1198 [JSOI2008]最大數

- 267通過
- 1.2K提交
題目提供者該用戶不存在
標簽線段樹各省省選
難度提高+/省選-

提交該題?討論?題解?記錄

題目描述

現在請求你維護一個數列，要求提供以下兩種操作：

1、查詢操作。

語法：Q L

功能：查詢當前數列中末尾L個數中的最大的數，并輸出這個數的值。

限制：L不超過當前數列的長度。

2、插入操作。

語法：A n

功能：將n加上t，其中t是最近一次查詢操作的答案（如果還未執行過查詢操作，則t=0)，并將所得結果對一個固定的常數D取模，將所得答案插入到數列的末尾。

限制：n是整數（可能為負數）并且在長整范圍內。

注意：初始時數列是空的，沒有一個數。

輸入輸出格式

輸入格式：

第一行兩個整數，M和D，其中M表示操作的個數(M <= 200,000)，D如上文中所述，滿足(0<D<2,000,000,000)

接下來的M行，每行一個字符串，描述一個具體的操作。語法如上文所述。

輸出格式：

對于每一個查詢操作，你應該按照順序依次輸出結果，每個結果占一行。

輸入輸出樣例

輸入樣例#1：

輸出樣例#1：

96
93
96

說明

[JSOI2008]

分析：這道題有很多種辦法解決,首先可以發現數列中的數是遞增的，每次添加進去的數都比之前的大，那么根據這個原理，模擬一下就能做出來.

這道題可以用來練線段樹，為什么想到要用線段樹呢？注意區間二字！在區間中查找最大值并且完成單點修改（插入），這不就是線段樹的最基本的操作嗎？因為線段樹可以全部賦值為-inf,所以插入操作可以理解為單點修改，套用線段樹的模板即可解決.

變量開成了全局變量，查了一個晚上的錯......

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>#define le l,mid,o * 2
#define re mid + 1,r,o * 2 + 1using namespace std;const int maxn = 200001;int m, d,maxo[maxn << 2],len,t;void build(int l,int r,int o)
{if (l == r){maxo[o] = -2147283647;return;}int mid = (l + r) >> 1;build(le);build(re);
}void charu(int l, int r, int o, int i, int j)
{if (l == r) { maxo[o] = j;return; }int mid = (l + r) >> 1;if (i <= mid)charu(le, i, j);else charu(re, i, j);maxo[o] = max(maxo[o * 2], maxo[o * 2 + 1]);
}int query(int l, int r, int o, int x, int y)
{if (x <= l && r <= y)return maxo[o];int mid = (l + r) >> 1;int temp = -2147483647;if (x <= mid)temp = max(temp,query(le, x, y));if (y > mid)temp = max(temp, query(re, x, y));return temp;
}int main()
{scanf("%d%d", &m, &d);build(1, maxn, 1);for (int b = 1;b <= m;++b){char c;int i;cin >> c;scanf("%d", &i);if (c == 'A') { len++;charu(1, maxn, 1, len, (i + t) % d); }else { t = query(1, maxn, 1, len - i + 1, len);printf("%d\n", t); }}return 0;
}

如果你還不會線段樹，那么可以參考一下下面這段文字(之前寫的可能不是很好，望體諒,可能也有一些不正確的，只能當作參考):

線段樹，這個萬能的樹。

線段，線段，說白了就是一個區間,線段樹主要的操作就是對區間進行修改查詢，效率非常高，線段樹的用途非常廣，單點更新、區間更新、最值詢問、區間詢問，至于它具體能干哪些事取決于樹里所儲存的信息量。

這是一個線段樹的圖，這個圖只是能夠幫我們理解線段樹的大體形狀，并不能告訴我們更多信息，其實線段樹的更多功能都隱藏在每一個節點的信息背后，為了能夠更方便的做題，我們給線段樹的每一個節點標上序號。我們從上到下，從左到右依次標號，如果根節點的序號為k,那么它的左子樹節點的序號則為2k,右子樹節點的序號則為2k + 1,每一個序號都對應著唯一一個節點，所以我們可以用一個數組tree來表示這個節點背后所隱藏的信息。這個數組究竟開多大呢？雖然在平常做題中我們不需要考慮的這么仔細，但在一些內存限制非常緊的題目中這些都是要注意的。如果區間范圍是[0,N-1],那么tree的大小M=2*N + 1,這個很好驗證。

我們先來考慮如何建樹，一般來說，只要到了葉子節點直接輸入就好了，但是我們怎么樣才能夠很快的到達葉子節點呢？遞歸！

int tree[2 * MAX_N + 1];

/*建立以k為根節點[L,H]為操作區間的線段樹*/

void built_tree(int k, int L, int H)

{

??? if (L == H){

??????? scanf("%d", &tree[k]);

??????? return;

??? }

??? built_tree(k << 1, L, (L + H) << 1);

??? built_tree(k << 1 | 1, (L + H) << 1 | 1, H);

}

如果L==H,證明當前區間的長度為1，也就是此節點為葉節點，可以直接賦值。

再來考慮一個經典問題：求一個區間內的最小元素值。

這道題可以用暴力來做，不過復雜度太高，在一些題目中可能會TLE,我們可以看到區間二字，那么這道題80%要用線段樹來做（當然也不是絕對，只是效率高），我們不斷比較當前查詢區間和目標區間，如果當前查詢區間在目標區間內，那么當前深度所表示的節點便可以參與最小值計算，如果不在區間內，則返回無窮大，否則則分別對當前樹的左右子樹進行相同運算（可能術語話太強了）.

int read_tree(int k, int L, int H, int beg, int end)

{

??? if (beg > H || end < L) return -INT_MAX;

??? if (beg <= L && end >= H) return tree[k];

??? return min(read_tree(2 * k, L, (L + H) / 2, beg, end),

??????? read_tree(2 * k + 1, (L + H) / 2 + 1, H, beg, end));

}

有查詢，就一定伴隨著修改的存在，如果是普通的數組，修改很容易，只需要對所需要操作的下標所對應的數據修改即可，但是這是高效率數據結構，修改就意味著要對許多量進行改變，在線段樹中，我們對一個節點進行修改只需要對其及其所有的祖先進行修改即可，其他量不變。

/*在根節點為k，[L,H]為操作區間的線段樹里對id處的值更新為key*/

int update_tree(int k, int L, int H, int id, int key)

{

??? if (L == H){

??????? tree[k] = key;

??????? return;

??? }

??? if (id < (L + H) / 2)

??????? update(k * 2, L, (L + H) / 2, id, key);

??? else

??????? update(K * 2 + 1, (L + H) / 2 + 1, H, id, key);

??? tree[k] = MAX(tree[k * 2], tree[2 * k + 1]);

}

這樣便完成了修改操作.

然后是比較復雜的區間修改，設計一個數據結構，使它支持兩種操作

Add(L,R,v)將AL,AL+1…AR的值全部+V
Query(L,R)計算子序列AL,AL+1…AR的元素和，最小值，最大值。

這里要維護三個查詢值，該怎么維護呢？

首先這里的Add操作是區間修改，并不是單點修改，最糟糕的情況下可能整棵線段樹的結點值都要被修改。我們知道線段樹任意區間都能分解成不超過2h個不相交區間的并，利用這個結論我們可以將每一個Add操作分解成不超過2h個的Add操作，記錄在線段樹的結點中。每次執行完Add操作都要重新計算每個結點的附加信息，遞歸訪問到的結點全部都要重新計算，并且是在遞歸返回后計算！

下面給出計算的代碼：

void weihu(int o,int L,int R)

{

??? int lc = o * 2, rc = o * 2 + 1;

??? sumv[o] = minv[o] = maxv[o] = 0;

??? if (R > L) {

??????? sumv[o] = sumv[lc] + sumv[rc];

??????? minv[o] = min(minv[lc], minv[rc]);

??????? maxv[o] = max(maxv[lc], maxv[rc]);

??? }

??? minv[o] += addv[o];

??? maxv[o] += addv[o];

??? sumv[o] += addv[o] * (R - L + 1);

}

對于下面的代碼來說,修改/查詢的范圍均為[y1,y2].

這里的sumv數組要說一下，為什么要用左右子結點相加得出呢？首先父親結點就包含了左右結點，其次這樣維護的時候就不需要修改全部的sumv數組的元素了。當然這里指的是特殊情況，一般是那種極端數據的。

下面是Add操作的代碼：

void Add(int o, int L, int R)

{

??? int lc = o * 2, rc = o * 2 + 1;

??? if (y1 <= L && y2 >= R)

??????? addv[o] += v;

??? else {

??????? int M = (L + R) >> 1;

??????? if (y1 <= M)

??????????? Add(lc, L, M);

??????? if (y2 > M)

??????????? Add(rc, M + 1, R);

??? }

??? weihu(o, L, R);

}

其中addv數組是累加邊界的add值，因為一棵線段樹的子節點可能不知被修改一次，所以有必要設立這個數組。

然后是查詢操作，話說用線段樹步步都得謹慎，感覺這句話沒錯啊，每次進行操作都要考慮到結點對結點之間有沒有影響，我們查詢一般都是從上往下遞歸查詢，既然一個結點的父結點執行了add操作，而這個節點也被父節點包括在內，所以這個節點的值肯定被改變了，于是我們只能設3個全局變量來維護。

int _min, _max, _sum;

void query(int o, int L, int R, int add)

{

??? if (y1 <= L && y2 >= R) {

??????? _sum += sumv[o] + add * (R - L + 1); \

??????????? _min = min(_min, minv[o] + add);

??????? _max = max(_max, maxv[o] + add);

??? }

??? else {

??????? int M = (L + R) >> 1;

??????? if (y1 <= M)

??????????? query(o * 2, L, M, add + addv[o]);

??????? if (y2 > M)

??????????? query(o * 2 + 1, M + 1, R, add + addv[o]);

??? }

}

看到很多人都弄混了，好吧，其實我也有點暈了。可能會有人問了，為什么我們的weihu函數已經維護了現在還要維護呢？因為weihu函數是從下到上的，也就是從左右子節點維護的，是相對于子節點所發生的變化，而這里的全局變量是因為父節點進行了Add操作，子節點包含在內，所以要另開變量維護。如果還是搞不明白，可以看到weihu函數最后只是修改了當前節點的值，并沒有維護到它的子節點，所以要另開變量維護。

接下來是更加復雜的：

Set(L,R,v)把AL,AL+1...AR的值全部修改為v.

Query(L,R)計算子序列AL,AL+1...AR的三個值（同上題）.

可以看到這里變動的是Set操作，我們說這道題比之前復雜，為什么呢？因為之前的Add操作不管操作次序如何，都可以達到最后的結果，前提是算法是對的，代碼沒寫錯。然而Set操作則不同，好比刷油漆，最后刷的就是最終顏色。怎么辦呢？打標記！這里的打標記則相當于對于被改變的特殊情況而做的變動，是為了最后的求出三個值而打的，那么怎么做呢？如果當前區間完全被包含在我們需要修改/查詢的區間內，則直接修改標記為v,否則則標記下傳。

void pushdown(int o)

{

??? int lc = o * 2, rc = o * 2 + 1;

??? if (setv[o] >= 0)

??? {

??????? setv[lc] = setv[rc] = setv[o];

??????? setv[o] = -1;

??? }

}

這里的setv數組即為標記，注意到這個數組被初始化為-1，這里不要搞錯了，那么問題來了：為什么我們要清除父節點的標記呢？

接下來，Set操作代碼：

void Set(int o, int L, int R)

{

??? int lc = o * 2, rc = o * 2 + 1;

??? if (y1 <= L && y2 >= R)

??? {

??????? setv[o] = v;

??? }

??? else {

??????? pushdown(o);

??????? int M = (L + R) >> 1;

??????? if (y1 <= M)

??????????? Set(lc, L, M);

??????? else

??????????? maintain(lc, L, M);

??????? if (y2 > M)

??????????? Set(rc, M + 1, R);

??????? else

??????????? maintain(rc, M + 1, R);

??? }

??? maintain(o, L, R);

}

注意到3次maintain，最后一次很好理解，因為我們之前講過，每一次遞歸完后都必須要維護一次，那么前兩次又是為何呢？因為標記一旦下傳，則該子樹的附加信息需要改變，當前區間內的子樹在遞歸完后自然會進行維護，不過另一個區間內的子樹則沒有被維護，因此需要加上兩次maintain函數的調用。

接下來是query操作的代碼：

void query(int o, int L, int R)

{

??? if (setv[o] >= 0) {

??????? _sum += setv[o] * (min(R, y2) - max(L, y1) + 1);

??????? _min = min(_min, setv[o]);

??????? _max = max(_max, setv[o]);

??? }

??? else if (y1 <= L && y2 >= R)

??? {

??????? _sum += sumv[o];

??????? _min = min(_min, minv[o]);

??????? _max = max(_max, maxv[o]);

??? }

??? else {

??????? int M = (L + R) >> 1;

??????? if (y1 <= M)

??????????? query(o * 2, L, M);

??????? if (y2 > M)

??????????? query(o * 2 + 1, M + 1, R);

??? }

}

對于有標記的區間，我們要優先處理，首先知道當前區間都被修改為setv[o],既然所有值都是一樣的，自然就是對其進行操作，然后再考慮被所要查詢的區間所完全包圍。回到之前的問題上來，為什么我們要清除父節點的標記呢？我們將標記下傳一般都是傳到被所要查詢的區間所完全包圍的區間，因為子節點的區間內的值就包含了大區間的值，換句話說，所求的結果就是幾個小區間的并，而這幾個小區間則是分解到不能再分解為止，自然，我們將父節點的標記消除因為子節點才是影響到結果的根本，我們求的值最終也在子節點進行，所以要消除.

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

轉載于:https://www.cnblogs.com/zbtrs/p/5851173.html