【bzoj1012】最大数

2. 最大数

Descrption

现在请求你维护一个数列，要求提供以下两种操作：
1. 查询操作。
  - 语法：(Q L)
  - 功能：查询当前数列中末尾 (L)个数中的最大的数，并输出这个数的值。
  - 限制：(L)不超过当前数列的长度。
2. 插入操作。
  - 语法：(A n)
  - 功能：将(n)加上(t)，其中(t) 是最近一次查询操作的答案（如果还未执行过查询操作，则(t=0))，并将所得结果对一个固定的常数(D)取模，将所得答案插入到数列的末尾。
  - 限制：(n)是非负整数并且在长整范围内。
注意：初始时数列是空的，没有一个数。

Input

第一行两个整数，(M)和(D)，其中(M)表示操作的个数((M <= 200,000))，(D)如上文中所述，满足((0<D<2,000,000,000))
接下来的(M)行，每行一个字符串，描述一个具体的操作。语法如上文所述。

Output

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

Sample Input

Sample Output

96
93
96

Hint

分析：

方法一：单点修改，区间查询，显然是线段树该干的事嘛，先略。

方法二：单调栈和二分。

因为求的是后 (L) 数的最值，所以当当前添加的数比前面的数大，实际上前面的数就没有必要再存在了。所以我们就可以维护一个单调递减的一个栈。
显然，栈最底部是 ([1,n]) 的最大值，那如何求 ([L,n])的最大值呢？我们以同步用一个数组记录当前在栈里的没有个数对应的(id) ，只需找到 (id) 数组中第一个大于或等于 (n-L+1)的位置，然后单调栈的当前位置的值即为答案，因为(id) 数组是单调递增的，二分查找即可。

Code

#include <bits/stdc++.h>
const int maxn=2e5+5;
int n,tail,head,m,mod;
int q[maxn],id[maxn];

void add(int x){//后加的数比前面的大，前面的就没什么用了
    while(q[tail]<=x&&tail)tail--;
    q[++tail]=x;id[tail]=++n;//q和id是同步的，只是记录的结果不一样
}
int qurey(int x){//查询
    int l=n-x+1;//手动模拟下不太好讲
    int k=std::lower_bound(id+head,id+tail+1,l)-id;
    return q[k];
}
void Solve(){
	scanf("%d%d",&m,&mod);
    int last=0;
    head=1;tail=0;
    while(m--){
        char str[2];
        int a;
        scanf("%s%d",str,&a);
        if(str[0]=='A')
            add((a+last)%mod);
        else
        	printf("%d
",last=qurey(a));
    }
}
int main(){
    Solve();
    return 0;
}

方法三：树状数组

树状数组大家熟悉的是单点修改，区间求和，其实树状数组也可以维护前缀或后缀的最值，前缀最值因为当前修改影响的是当前和后面的结果，所以我们一般用向上更新，向下求值，后缀最值刚好相反，一般是向下更新，向上求值。具体见代码。

Code

#include <bits/stdc++.h>
const int maxn = 2e5+10;
int m,cnt;
int D,last,c[maxn];
int lowbit(int x) {return x&(-x);}
void update(int i,int value){//向下更新
	for(;i;i-=lowbit(i))
		c[i]=std::max(c[i],value);    
}
int query(int i){//向上查询
    int res = 0;
    for(;i<=m;i+=lowbit(i))//m次操作最多有m个数，m之上就不用查询了
    	res=std::max(res,c[i]);   
    return res;
}
void Solve(){
	scanf("%d%d",&m,&D);
    for(int i=1;i<=m;i++){
    	char s[2];int x;
        scanf("%s%d",s,&x);
        if(s[0]=='A'){
            cnt++;
            update(cnt,(x+last)%D);
        }
        else{
            last = query(cnt-x+1);
            printf("%lld
",last);
        }
    }
}
int main(){
    Solve();
    return 0;
}