題目鏈接

開題第一件事看數據范圍.這里的范圍是二十萬,支持O(nlogn). 這是一個RMQ問題,同時要加點,我們因此考慮ST表或者線段樹.這里用線段樹是核彈打蚊子,沒有意義,我們因此考慮ST表.我們注意到如果加點操作需要改動ST表原來的東西ST表就會炸掉,我們就要考慮更高級的數據結構.不過這里如果我們建反向ST表加點就不會影響原來的數值了.

我們應該如何更新呢?對于一個新的要維護的區間我們可以拆成兩個子區間.我們發現靠前的那個區間原來是維護過的,而包含新點的區間因為倍增也被維護過.這樣我們可以以O(logn)更新新點.

如何查詢最小值?這個更簡單.我們發現任何區間可以被兩個2的倍數長度的區間覆蓋.比如5可以由兩個長度為4的區間覆蓋而成.我們按照同樣的想法查詢答案即可.

代碼:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int q,st[N][18],t,mod,x,n,logn[N],a[N];
char c;
signed main(){cin>>q>>mod;for(int i=2;i<=(2e5);i++){logn[i]=logn[i>>1]+1;}while(q--){cin>>c>>x;if(c=='A'){st[++n][0]=(t+x)%mod;for(int i=1;(1<<i)<=n;i++) st[n][i]=max(st[n][i-1],st[n-(1<<(i-1))][i-1]);}else{int tmp=logn[x];cout<<max(st[n][tmp],st[n-x+(1<<tmp)][tmp])<<'\n';t=max(st[n][tmp],st[n-x+(1<<tmp)][tmp]);}}return 0;
}