题解 P1198 【[JSOI2008]最大数】

· · 题解

个人觉得，我的这个做法还是很有趣的

看了别人的做法，好像没有跟我一样的

虽说我是用线段树，但是大家会发现，建树是一件特别麻烦的事情（本蒟蒻是这么觉得的），所以，我干了一些神奇的事情：我把每次操作都记录了下来，这样我们就可以知道最后总共会有多少个数，这样我们可以特别愉快的套用模板

看看我的代码吧

#include<bits/stdc++.h>
using namespace std;
#define pushup(o) tree[o]=max(tree[o<<1],tree[o<<1|1])//宏定义回溯 
char c[200001];//记录操作 
int len=0,m,t=0,q[200001],a[200001]/*存储每次操作的值*/,tree[800001]/*树*/,p1=0,p2=0/*这是两个指针，下面解释*/,d;
int query(int o,int l,int r,int x,int y){//(x,y)为 查询区间
    if(x<=l&&r<=y)return tree[o];
    int mid=l+r>>1,ans=INT_MIN;//因为有负数，返回值赋成最小 
    if(x<=mid)ans=query(o<<1,l,mid,x,y);
    if(mid<y)ans=max(ans,query(o<<1|1,mid+1,r,x,y));
    return ans;
}
void update(int o,int l,int r,int x,int y){//x为修改的点，y为要添加的值 
    if(l==r)tree[o]=y;//修改 
    else{
        int mid=l+r>>1;
        if(x<=mid)update(o<<1,l,mid,x,y);//二分思想 
        else update(o<<1|1,mid+1,r,x,y);
        pushup(o);
    }
}
int main(){
    memset(tree,-0x7f,sizeof(tree));//把所有的节点全部赋成极小的值，方便 max 操作 
    scanf("%d%d",&m,&d);
    for(int i=1;i<=m;i++){
        cin>>c[i];//记录下第i次的操作 
        if(c[i]=='Q')scanf("%d",&q[++p1]);//q[++p1]表示第p1次查询输入的L
        else scanf("%d",&a[++p2]);//a[++p2]表示第p2次添加输入的n 
    }
    len=p2;//我们可以知道，有多少次添加，数列中最后就会有多少个数，我们用len来记录最终的数列长度。 
    p1=0,p2=0;//赋成0，为了接下来的查询与更新 
    for(int i=1;i<=m;i++){
        if(c[i]=='Q'){//如果这次操作是查询 
            p1++;//这是第p1次查询 
            t=query(1,1,len,p2-q[p1]+1,p2);//p2为此时共操作过p2次添加，也就是数列中有p2个数，q[p1]表示此次查询末尾q[p1]个数 
            printf("%d\n",t);//t表示这次查询的答案 
        }
        else{//否则此次操作为添加 
            p2++;//这是第p2次添加，即此次更新的是数列中第p2个数 
            update(1,1,len,p2,(a[p2]+t)%d);//a[p2]是这次添加操作的输入值n 
        }
    }
}

蒟蒻把注释都写在里面了呢，我觉得我解释的挺清楚了QwQ

谢谢大佬们阅读