关键字：线段树基础。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
Input Format
第一行两个整数，M和D，其中M表示操作的个数，D如上文中所述。
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
Output Format
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
Sample Input #1
5 100
A 96
Q 1
A 97
Q 1
Q 2
Sample Output #1
96
93
96
Hint
对于100%的数据，M ≤ 200,000，0 < D < 2,000,000,000.
线段树裸题，没啥好说的- -但是本题洛谷上的数据似乎有问题。推荐在BZOJ上提交。
#include <stdio.h>
int n,m;
int ql,qr,tot = 0;
int an,last = 0,maxo[800010];
int max(int a,int b)
{
return a>b?a:b;
}
void add(int pos,int l,int r)
{
int mid = (l+r)>>1,nxt = pos<<1;
if(l>r) return;
if(l == r) maxo[pos] = an;
else
{
if(tot<=mid) add(nxt,l,mid);
else add(nxt+1,mid+1,r);
maxo[pos] = max(maxo[nxt],maxo[nxt+1]);
}
}
int query(int pos,int l,int r)
{
int mid = (l+r)>>1,nxt = pos<<1;
if(l>r) return maxo[0];
if(ql<=l&&r<=qr) return maxo[pos];
else if(qr<=mid) return query(nxt,l,mid);
else if(ql>mid) return query(nxt+1,mid+1,r);
else return max(query(nxt,l,mid), query(nxt+1,mid+1,r));
}
int main()
{
char opt;
scanf("%d %d\n",&n,&m);
while(n--)
{
scanf("%c ",&opt);
if(opt == 'Q')
{
scanf("%d\n",&ql);
ql = tot-ql+1; qr = tot;
printf("%d\n",last = query(1,1,200000));
}
else
{
scanf("%d\n",&an); an = (an+last)%m; tot++;
add(1,1,200000);
}
}
return 0;
}
评论 (0)
