题目背景
————————————————————————
这个fw佬猪居然连这么简单的线段树都不会写，没办法，只好来亲自拯救他一下
思路分析
————————————————————————
我们写线段树的题目通常分三步走：
①建树（build）
②修改单点/区间并维护线段树（repair）
③解决询问 （solve）
但是这道题的难点在于各个点之间的关系怎么建树？
有句话说的好：
解决问题的最好办法就是把产生问题的部分解决掉
没错，这道题目不需要建树！
我们可以直接对其进行修改和维护
可是，序列之间的数在线段树上又构成怎么样的关系呢？
其实只需要一个计数器cnt，表示当前列表里有cnt个数，那么当前所插入的数在线段树上的编号就是cnt
然后将和标号为cnt有关的线段都做一个最大值的修改就行了
前两个步骤都解决了，怎么解决步骤③（solve）呢？
其实发现cnt在现在就有用了
假设我们要查询后x个数中的最大值，其实是查询区间[cnt-x+1,cnt]内的最大值
用线段树求解即可
CODE
——————————————————————
#include<bits/stdc++.h>
#define int long long
using namespace std;
const long maxn=2e5+10;
int Q,P,cnt,last;
int c[maxn*4];
void write(int res){//只有快写，不知道为啥快读会寄
if(res < 0){
putchar('-');
res = -res;
}
if(res > 9){
write(res/10);
}
putchar((char)(res%10+'0'));
}
void repair(int p,int l,int r,int x,int u){
if(l == r){
c[p] = max(c[p],u);
return ;
}
int mid = l+r >> 1;
if(x <= mid){
repair(p << 1,l,mid,x,u);
}
else{
repair(p << 1|1,mid+1,r,x,u);
}
c[p] = max(c[p<<1],c[p<<1|1]);
}
int solve(int p,int l,int r,int b,int e){
if(l > e || r < b)return 0;
if(b <= l && r <= e) return c[p];
int mid = l+r >> 1;
return max(solve(p<<1,l,mid,b,e),solve(p<<1|1,mid+1,r,b,e));
}
signed main()
{
cin>>Q>>P;
while(Q--){
char z;
int w;
cin>>z;
if(z == 'A'){
scanf("%lld",&w);
w = (w+last)%P;
cnt++;
repair(1,1,200000,cnt,w);
}
else{
scanf("%lld",&w);
last = solve(1,1,200000,cnt-w+1,cnt);//记得记录上一个答案
write(last);
putchar('\n');
}
}
return 0;
}
共 3 条回复
您不会用 吗