题目链接

开题第一件事看数据范围.这里的范围是二十万,支持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;
}