手动博客搬家: 本文发表于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;
}