手动博客搬家: 本文发表于20170821 14:32:05, 原地址https://blog.csdn.net/suncongbo/article/details/77449455

URL: (Luogu) https://www.luogu.org/problem/show?pid=1198, (BZOJ)http://www.lydsy.com/JudgeOnline/problem.php?id=1012

题目大意:
给定一个数列，开始为空。维护两种操作:

(1) Q L表示查询当前数列后L个数的最大值。

(2) A N表示在当前数列末尾添加一个新数，这个新数的值等于上一次Q操作的答案加上给定的参数N. 若之前未进行Q操作，则添加的数为N.

思路分析:
此题牵扯到区间最值，我们可以用线段树进行解决。
但是Q操作由于需要插入元素，所以我们需要将其转化为能够利用线段树解决的问题。
这个序列是动态的，我们不妨将它变成静态的。
模拟添数的过程，对于每次查询，存下每次查询的区间左右端点，对于每次插入，记下插入的数以及它所对应的前一次查询的编号，便于后面找到上一次查询的答案。
然后，对记下的插入的数字先建线段树。
最后，循环枚举每次询问，在询问中继续枚举它所对应的插入，更新每次插入的值，以线段树单点修改的功能来实现。
看似先枚举询问，再枚举插入，是两重循环，但是由于在此循环中枚举插入的j只增不减(详见代码)，因此不会超时。

部分易错点:
注意第0次询问（即前面没有询问）的情况要单列。

代码呈现:
(Luogu: Time: 712 MS; Memory: 12.05 MB; Code: 2.04 KB)
(BZOJ: Time: 1088 MS; Memory: 13324 KB; Code: 2333 B)
注: 由于不同OJ评测方式不尽相同，因此时间空间等结果有所差别，属正常现象

​#include<cstdio>
#include<algorithm>
using namespace std;const int MAXN = 2e5;
int MODN;
struct Node
{int left,right;int maxi;
};
struct SegmentTree
{Node nd[MAXN*4+2];void init(){for(int i=1; i<=MAXN*4; i++){nd[i].left = nd[i].right = nd[i].maxi = 0;}}void build(int lbound,int rbound,int pos,int a[]){nd[pos].left = lbound;nd[pos].right = rbound;if(lbound==rbound){nd[pos].maxi = a[lbound];return;}int mid = (lbound+rbound)/2;build(lbound,mid,2*pos,a);build(mid+1,rbound,2*pos+1,a);nd[pos].maxi = max(nd[2*pos].maxi,nd[2*pos+1].maxi);}void modify(int bound,int val,int pos){int mid = (nd[pos].left+nd[pos].right)/2;if(nd[pos].left==nd[pos].right){nd[pos].maxi = val;return;}if(bound<=mid) modify(bound,val,2*pos);else modify(bound,val,2*pos+1); nd[pos].maxi = max(nd[2*pos].maxi,nd[2*pos+1].maxi);}int query(int lbound,int rbound,int pos){int mid = (nd[pos].left+nd[pos].right)/2;if(lbound==nd[pos].left && rbound==nd[pos].right) return nd[pos].maxi;   int ans;if(rbound<=mid) ans = query(lbound,rbound,2*pos);else if(lbound>mid) ans = query(lbound,rbound,2*pos+1);else ans = max(query(lbound,mid,2*pos),query(mid+1,rbound,2*pos+1));return ans;}
};
SegmentTree st;
int a[MAXN+2];
int p[MAXN+2];
int ql[MAXN+2];
int qr[MAXN+2];
int n,m,q;int main()
{char ch[5];int x;n = q = 0;scanf("%d%d",&m,&MODN);for(int i=1; i<=m; i++){scanf("%s",ch);switch(ch[0]){case 'A':{scanf("%d",&x);a[++n] = x;p[n] = q;break;}case 'Q':{scanf("%d",&x);ql[++q] = n-x+1;qr[q] = n;break;}}}st.init();st.build(1,n,1,a);int j = 1;while(j<=n && !p[j]){j++;}for(int i=1; i<=q; i++){int ans = st.query(ql[i],qr[i],1);printf("%d\n",ans);while(j<=n && p[j]==i){st.modify(j,(int)((long long)a[j]+ans)%MODN,1);j++;}}return 0;
}​