题解 P1198 【[JSOI2008]最大数】

这题就是一个 裸的线段树，但 线段树 每个节点存 一段区间中的最大值， 这样就可以保证每次询问都不用再扫一遍数据，否则除了 TLE 就是 30%AC 。。。 话说 线段树 除了常数大了之外好像没有什么缺点。。。（因为我只会写线段树，吃枣药丸） **不要复制代码！不要复制代码！！不要复制代码！！！重要的事情说3遍！** 附代码（缩进不喜勿喷）： ```cpp #include<iostream> #include<algorithm> #include<stdio.h> #define LSON rt<<1 #define RSON rt<<1|1//方便实用的宏。。。 #define max(a,b) a>b?a:b//STL的函数比手写的慢，所以为了减小被卡常数的几率，手写。。。 #define MAXN 200005 using namespace std; int m,d; long long t=0,a[MAXN<<2];//线段树 的空间是 原数据 的 4 倍，这是一定的 inline long long read(){//弱弱的读入优化，但好像没有什么用。。。防止被卡常吧 long long date=0,w=1;char c=0; while(c!='-'&&(c<'0'||c>'9'))c=getchar(); if(c=='-'){w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } void pushup(int rt){ a[rt]=max(a[LSON],a[RSON]);//每个节点存 区间最大值 } void update(int l,int r,int rt,int x,long long y){//针对题目的输入，建树与插入的合体。。。 int mid; if(l==r){ a[rt]=y;//叶子结点时赋 区间最大值 return; } mid=l+r>>1;//位运算，经验靠诉我们 >>1 比 /2 快很多。。。 if(x<=mid)update(l,mid,LSON,x,y); else update(mid+1,r,RSON,x,y);//分 左子树 与 右子树 建立 pushup(rt);//一定不要忘记这句话！！！很重要！！！ } long long query(int l,int r,int rt,int x,int y){ int mid; long long ans=-2147483647;//注意，千万不要设成 0 ，当初我提交3次，2次被卡 if(x<=l&&y>=r)//出了范围就返回区间最大值 return a[rt]; mid=l+r>>1; if(x<=mid)ans=max(ans,query(l,mid,LSON,x,y)); if(mid<y)ans=max(ans,query(mid+1,r,RSON,x,y));//还是 左子树 与 右子树 处理 return ans;//不同上！！！一定要返回答案！！！ } int main(){ int x,s=0; char c[2]; m=read();d=read(); for(int i=1;i<=m;i++){ scanf("%s",c);//每行首字为 字符，为避免读入 回车符 ‘\n’ 或者 "\r\n"，用 %s ，这是一个很实用的东东。。。 if(c[0]=='A'){//分情况处理。。。 x=read(); s++; x=(x+t)%d; update(1,m,1,s,x);//询问范围是 1 到 m } if(c[0]=='Q'){ x=read(); t=query(1,m,1,s-x+1,s);//这里只是为了 t 能在下一次询问时使用 printf("%lld\n",t);//注意，t 为 long long，不然会炸。。。 } } return 0;//收尾。。。 } ```